Методы оптимизации (весна 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] Конспекты похожего курса на мехмате МГУ
Список вопросов к экзамену
- Двудольные паросочетания. Увеличивающие пути. Теорема Холла о совершенных паросочетаниях.
- Формы задач ЛП, их эквивалентность. Элиминация переменных.
- Полиэдры, политопы, вершины. Критерий вершины.
- Тотально унимодулярные матрицы, целочисленность полиэдра. Тотальная унимодулярность в задаче о двудольном паросочетании.
- Слабая двойственность для задачи ЛП. Сильная двойственность (формулировка). Построение двойственной ЛП для задачи в общей форме.
- Прямая и двойственная ЛП для задачи о двудольном паросочатении, целочисленность двойственных решений. Теорема Кёнига—Эгервари.
- Конусы: конечнопорожденные и полиэдральные. Отделимость от конусов, лемма Фаркаша.
- Доказательство теоремы о сильной двойственности. Дополняющая нежесткость.
- Primal-dual алгоритм в задаче о кратчайших путях для случая неотрицательных длин. Сведение случая длин общего вида к последовательности подзадач для неотрицательных длин.
- Рандомизированное $d$-приближение для задачи о покрытии множествами ($d$~--- толщина покрытия).
- Рандомизированное $O(log n)$-приближение для задачи о покрытии множествами.
- Primal-dual алгоритм для задачи о совершенном двудольном паросочетании минимального веса.
- Максимальные паросочетания в недвудольных графах, поиск увеличивающих путей с помощью алгоритма Эдмондса. Теорема Татта-Бержа, алгоритмическое доказательство.
- Задача об упаковке вершинно-непересекающихся $T$-путей, формулировка теоремы Галлаи. Сведение к задаче о недвудольном паросочетании.
- Рандомизированное 2-приближение для задачи о максимальном разрезе.
- SDP. Рандомизированное 0.87-приближение для задачи о максимальном разрезе.
Порядок проведения экзамена
Экзамен состоит из двух частей.
Вначале каждый сдающий экзамен вначале вытягивает случайный билет, в котором содержатся два вопроса по теории из списка, приведенного выше. Во время подготовки к ответу разрешается пользоваться любыми записями, конспектами, учебной литературой (в печатном и электронном виде). При подготовке студент на отдельном листе делает записи, необходимые ему для ответа.
После того, как подготовка завершена, пользоваться любыми записями (кроме тех, что были сделаны во время подготовки) не разрешается. Во время ответа необходимо продемонстрировать знание соответствующего раздела теории. Наличие разумного конспекта ответа, сделанного в процессе подготовки, крайне приветствуется.
В процессе сдачи первой части экзамена могут быть заданы дополнительные теоретические вопросы, связанные с темами билета. Ответы на них предполагаются простыми и краткими, как правило следующими из определений или изученных во время курса теорем.
По завершении первой части начинается вторая, во время которой необходимо продемонстировать умение решать задачи с учетом имеющегося теоретического багажа. Каждый сдающий получает одну или более задач (несколько простых или одну сложную). Список задач заранее не разглашается, однако среди них могут (и будут) присутствовать задачи, аналогичные тем, что предлагались в домашних заданиях в течение семестра, а также разбирались на семинарах.
Во время сдачи второй части курса пользоваться литературой, конспектами и прочими материалами не разрешается.
