Просмотр кода страницы Методы оптимизации (весна 2017)

== Аннотация ==
Вики-страница посвящена второй части курса методов оптимизации, посвящённой дискретной (комбинаторной) оптимизации.
== Персоналии ==
* Лектор: Максим Бабенко
* Семинаристы: Максим Ахмедов, Александр Дайняк, Алексей Лахно, Руслан Савченко

== Лекции ==
=== Лекция 04.04 ===
* Постановка задачи о паросочетании наибольшей мощности/веса
* Постановка задачи линейного программирования (LP).
* Целочисленная линейная программа, кодирующая задачу о паросочетании. Линейная релаксация.
* Пример того, что для $K_3$ у решений соответствующей линейной релаксации нет комбинаторного смысла. [Почему оптимум такой? Заход в двойственность.]
* Понятие препятствия и сертификата. Пример: s-t-барьер как сертификат несуществования (комбинаторное препятствие для существования) s-t-пути в неориентированном графе. В ориентированных графах s-t-разрезы.
* Теорема Холла о совершенных паросочетаниях. Построение препятствия.
* Формула Татта-Бержа (в формате критерия существования совершенного паросочетания в произвольном графе) в сторону "критерий не выполнен => совершенного паросочетания не существует".

=== Лекция 11.04 ===
* Формы задач ЛП, их эквивалентность
* Элиминация переменных
* Полиэдры, политопы, вершины
* Критерий вершины
* Тотально унимодулярные матрицы, целочисленность полиэдра
* Тотальная унимодулярность в задаче о двудольном паросочетании
=== Лекция 18.04 ===
* Слабая двойственность для задачи ЛП
* Сильная двойственность (формулировка)
* Построение двойственной ЛП для задачи в общей форме 
* Прямая и двойственная ЛП для задачи о двудольном паросочатении, целочисленность двойственных решений, теорема Кёнига—Эгервари
* Конусы: конечнопорожденные и полиэдральные
* Отделимость от конусов, лемма Фаркаша
=== Лекция 25.04 ===
* Доказательство теоремы о сильной двойственности
* Дополняющая нежесткость
* Задача о кратчайших путях, формулировка в терминах линейного программирования
* Потенциалы и приведенные длины

=== Лекция 16.05 ===
* Критерий консервативности длин в терминах наличия допустимых потенциалов
* Primal-dual алгоритм для случая неотрицательных длин
* Сведение случая длин общего вида к последовательности подзадач для неотрицательных длин
* Задача о покрытии множества, формулировка в виде ЛП
* Детерминированное округление решений: d-приближение для покрытия максимальной толщины d
* Рандомизированное округление решений: O(log n)-приближение для общего случая

== Домашние задания ==
* [https://drive.google.com/file/d/0B5XaFkH0dkxeUm8zM3B5SFY2UkE/view?usp=sharing Первое задание (теоретическое)]
* [https://drive.google.com/file/d/0B5XaFkH0dkxeUkxrRDVjUWhUajg/view?usp=sharing Второе задание (практическое)]
* Третье задание (теоретическое)


==Правила вычисления итоговой оценки за курс==

"Итоговая_оценка" = 0.8 * "Накопленная_итоговая" + 0.2 "Экзамен"

"Накопленная_итоговая " = 0.625 * "Накопленная_непрерывная" + 0.375 * "Накопленная_дискретная"

"Накопленная_непрерывная" выставляется по итогам 3-го модуля преподавателями курса по непрерывной оптимизации.

За 4-й модуль выставляется отдельная оценка "Накопленная_дискретная" и проводится экзамен.
На экзамене будет спрашиваться только материал 4-го модуля (дискретная оптимизация).

"Итоговая_оценка" округляется ближайшему целому (.5 округляется к единице).

В 4-м модуле в курсе есть три домашних задания, которые оцениваются от 0 до 10.

"Накопленная_дискретная"" = 0.35 * ("дом_1" + "дом_2" + "дом_3").

"Накопленная_дискретная" округляется до [0,10] в большую сторону.
Если до округления "Накопленная_дискретная" >= 10, то она округляется до 10.