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

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

Лекция 23.05

• Primal-dual алгоритм для задачи о совершенном двудольном паросочетании минимального веса
• Максимальные паросочетания в недвудольных графах, поиск увеличивающих путей с помощью алгоритма Эдмондса

Лекция 30.05

• Теорема Татта-Бержа, алгоритмическое доказательство
• Задача об упаковке вершинно-непересекающихся T-путей, формулировка теоремы Галлаи

Лекция 6.06

• Cведение задачи упаковки T-путей к задаче о максимальном паросочетании
• Введение в метод эллипсиодов

Лекция 13.06 (план)

• Задача о максимальном разрезе, рандомизированное 2-приближение
• SDP, рандомизированное 0.87-приближение для задачи о максимальном разрезе

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

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

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

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

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

"Накопленная_непрерывная" выставляется по итогам 3-го модуля преподавателями курса по непрерывной оптимизации и представляет собой целое число на отрезке [0,10].

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

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

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

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

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

Помимо явно указанных выше, никаких других округлений оценок в промежуточных вычислениях не производится.

Литература

• Vijay V. Vazirani - Approximation Algorithms
• Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms
• A. Schrijver - Combinatorial Optimization: Polyhedra and Efficiency
• Andras Frank - On Kuhn’s Hungarian Method
• лекции Максима Бабенко по линейному программированию в Computer Science клубе
• [1] Конспекты похожего курса на мехмате МГУ

Список вопросов к экзамену

1. Двудольные паросочетания. Увеличивающие пути. Теорема Холла о совершенных паросочетаниях.
2. Формы задач ЛП, их эквивалентность. Элиминация переменных.
3. Полиэдры, политопы, вершины. Критерий вершины.
4. Тотально унимодулярные матрицы, целочисленность полиэдра. Тотальная унимодулярность в задаче о двудольном паросочетании.
5. Слабая двойственность для задачи ЛП. Сильная двойственность (формулировка). Построение двойственной ЛП для задачи в общей форме.
6. Прямая и двойственная ЛП для задачи о двудольном паросочатении, целочисленность двойственных решений. Теорема Кёнига—Эгервари.
7. Конусы: конечнопорожденные и полиэдральные. Отделимость от конусов, лемма Фаркаша.
8. Доказательство теоремы о сильной двойственности. Дополняющая нежесткость.
9. Primal-dual алгоритм в задаче о кратчайших путях для случая неотрицательных длин. Сведение случая длин общего вида к последовательности подзадач для неотрицательных длин.
10. Рандомизированное $d$-приближение для задачи о покрытии множествами ($d$~--- толщина покрытия).
11. Рандомизированное $O(log n)$-приближение для задачи о покрытии множествами.
12. Primal-dual алгоритм для задачи о совершенном двудольном паросочетании минимального веса.
13. Максимальные паросочетания в недвудольных графах, поиск увеличивающих путей с помощью алгоритма Эдмондса. Теорема Татта-Бержа, алгоритмическое доказательство.
14. Задача об упаковке вершинно-непересекающихся $T$-путей, формулировка теоремы Галлаи. Сведение к задаче о недвудольном паросочетании.
15. Рандомизированное 2-приближение для задачи о максимальном разрезе.
16. SDP. Рандомизированное 0.87-приближение для задачи о максимальном разрезе.