Методы оптимизации (весна 2017) — различия между версиями

Версия 16:23, 17 мая 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)-приближение для общего случая

Домашние задания

• Первое (теоретическое) задание
• Второе (практическое) задание
• Второе (теоретическое) задание