Wiki - Факультет компьютерных наук - Вклад [ru]

Дискретная оптимизация 2019

2019-05-28T14:48:45Z

Savrus:

== О курсе ==

Курс читается для студентов 3-го курса [https://cs.hse.ru/ami ПМИ ФКН ВШЭ] в 4 модуле.

'''Лектор:''' [http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ignat Игнат Колесниченко]

Лекции проходят по вторникам, 13:40 - 15:00, ауд. 622, семинары проходят сразу после лекции во вторник.

=== Полезные ссылки ===

Канал в телеграм для объявлений: https://t.me/joinchat/AAAAAFSFHLfHTjeBd2Ueqg

Таблица с оценками: TODO

== Семинары ==

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница
|-
| - || Колесниченко Игнат || ignat1990@gmail.com || http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ignat
|-
| МОП 161 || Савченко Руслан || telegram: @savrus || ?
|-
| МОП 162 + РС 166-2 || Лахтанов Иван || telegram: @ivan_lakhtanov || ?
|-
| АДИС 163 + АПР 167 + РС 166-1 || Смирнов Иван || telegram: @ifsmirnov || ?
|-
| АДИС 164 || Саакян Вильям || telegram: @wilwell || ?
|-
| РС 165 || Ахмедов Максим || telegram: @max_akhmedov || ?
|-
|}

=== Консультации ===

Консультации с преподавателями и учебными ассистентами (если иное не оговорено на странице семинаров конкретной группы) по курсу проводятся по предварительной договорённости ввиду невостребованности регулярных консультаций.

=== Правила выставления оценок ===

В курсе предусмотрено следующий набор контрольных мероприятий:

1) Контрольная работа с теоретическими задачами и теоретически мини-ДЗ. Точные критерии оценивания будут определены в ходе курса. Вклад данной части в общую оценку – 2 из 10.

2) Контест с решением практических задач, проводимые во время лекции и семинара (то есть на 3 часа). Вклад данной части в общую оценку – 2 из 10.

3) Практические домашние задания (в виде Я.Контестов с длительностью несколько недель). Вклад данной части в общую оценку – 3 из 10.

4) Устный теоретический экзамен. Вклад данной части в общую оценку – 3 из 10.

За каждую из частей будет выставлена оценка от 0 до 10 (с шагом в 0.5 балла). Итоговая оценка вычисляется по формуле:

Oитоговая = round(0.2 * O1 + 0.2 * О2 + 0.3 * О3 + 0.3 * Oэкз), где round – это функция арифметического округления.

Так как формальные правила требует округлений отдельных оценок и округления оценки за работу в семестре – фактические оценки в ведомости будут выставлены таким образом, чтобы соответствовать той оценке, которые получается по указанной выше формуле.

=== Правила сдачи заданий ===

Дедлайны по всем домашним заданиям являются жёсткими, то есть после срока работы не принимаются.

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

При наличии уважительной причины дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.

== Лекции ==

===Лекция 1===
Примеры комбинаторных задача: Maximum Matching, Set Cover, TSP. Представление задачи Maximum Matching в виде ILP, релаксация ILP до LP. Напоминание про LP – понятие полиэдров и политопов, формы задания, понятие вершины. Теорема о том, что оптимум достигается в вершине. Базисные допустимые решения и их связь с вершинами.

===Лекция 2===
Явное построение двойственной задаче для задачи о паросочетаниях. Теорема о сильной двойственности, условия дополняющей нежесткости. Метод ветвей и границ (Branch and Bound) для решения комбинаторных задач. Применение B&B для решения ILP. Задача о рюкзаке, решение LP в задаче о рюкзаке.

===Лекция 3===
Алгоритм 2-приближения для задачи о рюкзаке. Динамика по стоимостям и по весам для задачи о рюкзаке. Динамика по весам с использованием O(W) памяти. Построение схем приближения для задачи о рюкзаке: PTAS c временем O(n^(1 + 1/eps)) (без доказательства), FPTAS с временем O(n^2/eps), алгоритм Ibara-Kim с временем O(n/eps^2).

===Лекция 4===
Задача о кратчайших путях, построение решения с помощью техники Primal-Dual.

===Лекция 5===
Задача о взвешенном паросочетании в двудольном графе, построение решения с помощью техники Primal-Dual. Существование совершенного паросочетания в регулярном двудольном графе.

===Лекция 6===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

== Семинары ==

===Семинар 1===
Приведение линейных программ к разным формам. Правила построение двойственных программ для программы в общей форме. Утверждение о целочисленности вершины в задаче о совершенном паросочетании в двудольном графе. Тотальная унимодулярность, и теорема о целочисленности полиэдра.

===Семинар 2===
Теорема о дополняющем пути. Алгоритм Куна поиска паросочетания в двудольном графе. Условия дополняющей нежесткости для пары задач Maximum Matching, Vertex Cover. Поиск вершинного покрытия из максимального паросочетания в двудольном графе.

===Семинар 3===
Построение прямой и двойственной задачи для задачи о потоки в графе. Построение линейное программы для задачи о поиске максимальной клики в графе и для задачи Car Sequencing.

===Семинар 4===
Задача Set-Cover, построение линейной и двойственной программ. Округление решения линейной программы, дающее f-приближение. Primal-Dual алгоритм для эффективного поиска f-приближения в данной задачи.

===Семинар 5===
Контрольная работа.

===Семинар 6===
Задача коммивояжера (TSP). 2-приближенные алгоритм для метрической задачи. 1-5 приближенный алгоритм Кристофидеса. Локальные поиск – 2-OPT шаги, эвристика Lin-Kernighan.

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

===Задание 1 (задача о рюкзаке)===
'''Дедлайн: 23.59 28 апреля. Не опаздывайте, после дедлайна решения не принимаются.'''

В задании предлагается решать задачу о рюкзаке. Архив с заданием доступен [https://yadi.sk/d/K7W0GqAjo8RGmQ здесь]. Обратите внимание, что ваше решение должно состоять из успешная посылка в Я.Контесте и написанный отчет, которые вы должны прислать по почту. При этом успешность посылки не означает, что ваше решение близко к оптимуму и наберем хоть какие-то баллы за задачу.

Для задачи о рюкзаке имеется [http://akhmedov.me:50022/knapsack/ грейдер] - в него можно сдавать решения публичных тестов и сравниваться с другими участниками. Имя необходимо указывать в формате "фамилия транслитом маленькими буквами + подчеркивание + имя транслитом маленькими буквами", например: kolesnichenko_ignat.

Контест для сдачи задач доступен по [https://contest.yandex.ru/contest/12610 ссылке].

Задание и вопросы по нему следует отправлять на почту %%discret.opt.hse@gmail.com%%. В заголовке письма указывайте "ФИО Практика1"

==Экзамен==

[https://yadi.sk/i/GP7lXeyKyKfF3Q Предварительная программа экзамена]

== Пересдача ==

== Комиссия ==

== Полезные материалы ==
===Рекомендуемая литература ===

* "B.Korte, J.Vygen – Combinatorial optimization" – подробная книга по теории комбинаторной оптимизации (http://www.or.uni-bonn.de/~vygen/co.html).
* "V. Vazirani – Approximation Algorithms" – одна из лучших книг по приближенным алгоритмам.
* "H. Papadimitriou – Combinatorial Optimization: Algorithms and Complexity" – классический учебник по комбинаторной оптимизации.
* "Where are the hard knapsack problems?" [David Pisinger] - интересные рассуждения по поводу того, как генерировать сложные тесты для задачи о рюкзаке.
* [[https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf "Heuristics for the Traveling Salesman Problem" [Christian Nilsson]]] - краткое но насыщенное описание эвристик для задачи о коммивояжёре.
* "Handbook of Constraint Programming" [F. Rossi, P. van Beek and T. Walsh] - справочник по программированию в ограничениях.
* "Handbook of Metaheuristics" [Michel Gendreau, Jean-Yves Potvin] - справочник с описанием эвристических алгоритмов оптимизации.
* "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic" [Keld Helsgaun] - описание эвристики Лина-Кернигана для задачи комивояжёра.
* "The car sequencing problem: overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem" - описание эвристик, в том числе локального поиска, для задачи car sequencing.

===Полезные ссылки ===

* [[http://dopt.s3-website-us-east-1.amazonaws.com/003/viz/tsp/ Визуализатор маршрута коммивояжёра]] (вершины подаются в 0-индексации)
* Курс по дискретной оптимизации на [[https://www.coursera.org/course/optimization Coursera]]. Содержит хорошие видео-лекции по Constraint Programming и Local Search.

===Библиотеки для решения задач оптимизации===
* [[https://developers.google.com/optimization/ Google Optimization Tools]] (C++, Python, Java, C#) - фреймворк для решения задач дискретной оптимизаций. Позволяет программировать в парадигме Constraint Programming. Содержит инструменты для решения задач линейного программирования. ([[http://www.lia.disi.unibo.it/Staff/MicheleLombardi/or-tools-doc/documentation_hub.html Более полная документация]])
* [[http://numberjack.ucc.ie/ Numberjack]] (Python)
* [[http://choco-solver.org/ Choco]] (Java)
* [[http://www.gecode.org/index.html Gecode]] (C++)
* [[http://www.minizinc.org/ MiniZinc]] (MiniZinc) - Довольно выразительный язык для CP. Есть ((http://www.hakank.org/minizinc/ много примеров)).

Дискретная оптимизация 2019

2019-05-14T15:05:41Z

Savrus: Добавлена ссылка на описание Lin-Kernigan эвристики для TSP

== О курсе ==

Курс читается для студентов 3-го курса [https://cs.hse.ru/ami ПМИ ФКН ВШЭ] в 4 модуле.

'''Лектор:''' [http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ignat Игнат Колесниченко]

Лекции проходят по вторникам, 13:40 - 15:00, ауд. 622, семинары проходят сразу после лекции во вторник.

=== Полезные ссылки ===

Канал в телеграм для объявлений: https://t.me/joinchat/AAAAAFSFHLfHTjeBd2Ueqg

Таблица с оценками: TODO

== Семинары ==

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница
|-
| - || Колесниченко Игнат || ignat1990@gmail.com || http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ignat
|-
| МОП 161 || Савченко Руслан || telegram: @savrus || ?
|-
| МОП 162 + РС 166-2 || Лахтанов Иван || telegram: @ivan_lakhtanov || ?
|-
| АДИС 163 + АПР 167 + РС 166-1 || Смирнов Иван || telegram: @ifsmirnov || ?
|-
| АДИС 164 || Саакян Вильям || telegram: @wilwell || ?
|-
| РС 165 || Ахмедов Максим || telegram: @max_akhmedov || ?
|-
|}

=== Консультации ===

Консультации с преподавателями и учебными ассистентами (если иное не оговорено на странице семинаров конкретной группы) по курсу проводятся по предварительной договорённости ввиду невостребованности регулярных консультаций.

=== Правила выставления оценок ===

В курсе предусмотрено следующий набор контрольных мероприятий:

1) Контрольная работа с теоретическими задачами и теоретически мини-ДЗ. Точные критерии оценивания будут определены в ходе курса. Вклад данной части в общую оценку – 2 из 10.

2) Контест с решением практических задач, проводимые во время лекции и семинара (то есть на 3 часа). Вклад данной части в общую оценку – 2 из 10.

3) Практические домашние задания (в виде Я.Контестов с длительностью несколько недель). Вклад данной части в общую оценку – 3 из 10.

4) Устный теоретический экзамен. Вклад данной части в общую оценку – 3 из 10.

За каждую из частей будет выставлена оценка от 0 до 10 (с шагом в 0.5 балла). Итоговая оценка вычисляется по формуле:

Oитоговая = round(0.2 * O1 + 0.2 * О2 + 0.3 * О3 + 0.3 * Oэкз), где round – это функция арифметического округления.

Так как формальные правила требует округлений отдельных оценок и округления оценки за работу в семестре – фактические оценки в ведомости будут выставлены таким образом, чтобы соответствовать той оценке, которые получается по указанной выше формуле.

=== Правила сдачи заданий ===

Дедлайны по всем домашним заданиям являются жёсткими, то есть после срока работы не принимаются.

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

При наличии уважительной причины дедлайн по домашнему заданию может быть перенесён. Дедлайн по домашнему заданию переносится на количество дней, равное продолжительности уважительной причины. Решение о том, является ли причина уважительной, принимает исключительно учебный офис.

== Лекции ==

===Лекция 1===
Примеры комбинаторных задача: Maximum Matching, Set Cover, TSP. Представление задачи Maximum Matching в виде ILP, релаксация ILP до LP. Напоминание про LP – понятие полиэдров и политопов, формы задания, понятие вершины. Теорема о том, что оптимум достигается в вершине. Базисные допустимые решения и их связь с вершинами.

===Лекция 2===
Явное построение двойственной задаче для задачи о паросочетаниях. Теорема о сильной двойственности, условия дополняющей нежесткости. Метод ветвей и границ (Branch and Bound) для решения комбинаторных задач. Применение B&B для решения ILP. Задача о рюкзаке, решение LP в задаче о рюкзаке.

===Лекция 3===
Алгоритм 2-приближения для задачи о рюкзаке. Динамика по стоимостям и по весам для задачи о рюкзаке. Динамика по весам с использованием O(W) памяти. Построение схем приближения для задачи о рюкзаке: PTAS c временем O(n^(1 + 1/eps)) (без доказательства), FPTAS с временем O(n^2/eps), алгоритм Ibara-Kim с временем O(n/eps^2).

===Лекция 4===
Задача о кратчайших путях, построение решения с помощью техники Primal-Dual.

== Семинары ==

===Семинар 1===
Приведение линейных программ к разным формам. Правила построение двойственных программ для программы в общей форме. Утверждение о целочисленности вершины в задаче о совершенном паросочетании в двудольном графе. Тотальная унимодулярность, и теорема о целочисленности полиэдра.

===Семинар 2===
Теорема о дополняющем пути. Алгоритм Куна поиска паросочетания в двудольном графе. Условия дополняющей нежесткости для пары задач Maximum Matching, Vertex Cover. Поиск вершинного покрытия из максимального паросочетания в двудольном графе.

===Семинар 3===
Построение прямой и двойственной задачи для задачи о потоки в графе. Построение линейное программы для задачи о поиске максимальной клики в графе и для задачи Car Sequencing.

===Семинар 4===
Задача Set-Cover, построение линейной и двойственной программ. Округление решения линейной программы, дающее f-приближение. Primal-Dual алгоритм для эффективного поиска f-приближения в данной задачи.

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

===Задание 1 (задача о рюкзаке)===
'''Дедлайн: 23.59 28 апреля. Не опаздывайте, после дедлайна решения не принимаются.'''

В задании предлагается решать задачу о рюкзаке. Архив с заданием доступен [https://yadi.sk/d/K7W0GqAjo8RGmQ здесь]. Обратите внимание, что ваше решение должно состоять из успешная посылка в Я.Контесте и написанный отчет, которые вы должны прислать по почту. При этом успешность посылки не означает, что ваше решение близко к оптимуму и наберем хоть какие-то баллы за задачу.

Для задачи о рюкзаке имеется [http://akhmedov.me:50022/knapsack/ грейдер] - в него можно сдавать решения публичных тестов и сравниваться с другими участниками. Имя необходимо указывать в формате "фамилия транслитом маленькими буквами + подчеркивание + имя транслитом маленькими буквами", например: kolesnichenko_ignat.

Контест для сдачи задач доступен по [https://contest.yandex.ru/contest/12610 ссылке].

Задание и вопросы по нему следует отправлять на почту %%discret.opt.hse@gmail.com%%. В заголовке письма указывайте "ФИО Практика1"

== Пересдача ==

== Комиссия ==

== Полезные материалы ==
===Рекомендуемая литература ===

* "B.Korte, J.Vygen – Combinatorial optimization" – подробная книга по теории комбинаторной оптимизации (http://www.or.uni-bonn.de/~vygen/co.html).
* "V. Vazirani – Approximation Algorithms" – одна из лучших книг по приближенным алгоритмам.
* "H. Papadimitriou – Combinatorial Optimization: Algorithms and Complexity" – классический учебник по комбинаторной оптимизации.
* "Where are the hard knapsack problems?" [David Pisinger] - интересные рассуждения по поводу того, как генерировать сложные тесты для задачи о рюкзаке.
* [[https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf "Heuristics for the Traveling Salesman Problem" [Christian Nilsson]]] - краткое но насыщенное описание эвристик для задачи о коммивояжёре.
* "Handbook of Constraint Programming" [F. Rossi, P. van Beek and T. Walsh] - справочник по программированию в ограничениях.
* "Handbook of Metaheuristics" [Michel Gendreau, Jean-Yves Potvin] - справочник с описанием эвристических алгоритмов оптимизации.
* "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic" [Keld Helsgaun] - описание эвристики Лина-Кернигана для задачи комивояжёра.

===Полезные ссылки ===

* [[http://dopt.s3-website-us-east-1.amazonaws.com/003/viz/tsp/ Визуализатор маршрута коммивояжёра]] (вершины подаются в 0-индексации)
* Курс по дискретной оптимизации на [[https://www.coursera.org/course/optimization Coursera]]. Содержит хорошие видео-лекции по Constraint Programming и Local Search.

===Библиотеки для решения задач оптимизации===
* [[https://developers.google.com/optimization/ Google Optimization Tools]] (C++, Python, Java, C#) - фреймворк для решения задач дискретной оптимизаций. Позволяет программировать в парадигме Constraint Programming. Содержит инструменты для решения задач линейного программирования. ([[http://www.lia.disi.unibo.it/Staff/MicheleLombardi/or-tools-doc/documentation_hub.html Более полная документация]])
* [[http://numberjack.ucc.ie/ Numberjack]] (Python)
* [[http://choco-solver.org/ Choco]] (Java)
* [[http://www.gecode.org/index.html Gecode]] (C++)
* [[http://www.minizinc.org/ MiniZinc]] (MiniZinc) - Довольно выразительный язык для CP. Есть ((http://www.hakank.org/minizinc/ много примеров)).

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

2017-06-06T13:37:57Z

Savrus:

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

== Лекции ==
=== Лекция 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-приближение для задачи о максимальном разрезе

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

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

"Итоговая_оценка" = 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.

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

==Литература==
* [https://drive.google.com/file/d/0B3Hea5EPX4S0Tk1pbUxPZDQ5WlU/view?usp=sharing Vijay V. Vazirani - Approximation Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0NzQteFJVenJfckk/view?usp=sharing Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0U0NCQlZ2OXc3Tk0/view?usp=sharing A. Schrijver - Combinatorial Optimization: Polyhedra and Efficiency]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0b09JY2ZzeWM5N0U/view?usp=sharing Andras Frank - On Kuhn’s Hungarian Method]
* [http://logic.pdmi.ras.ru/csclub/courses/linearprogramming лекции Максима Бабенко по линейному программированию в Computer Science клубе]
* [https://drive.google.com/open?id=0B-mmvUp64CSgVmFyMkpXZ1U0N0k] Конспекты похожего курса на мехмате МГУ

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

2017-05-30T08:22:22Z

Savrus:

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

== Лекции ==
=== Лекция 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 (план) ===
* Задача о многостороннем минимальном разрезе, (2-2/k)-приближение
* Рандомизированное 3/2-приближение для задачи о многостороннем разрезе

===Лекция 13.06 (план) ===
* Оракулы отделения, метод эллипсоидов
* Задача о максимальном разрезе, рандомизированное 2-приближение
* SDP, рандомизированное 0.87-приближение для задачи о максимальном разрезе

== Домашние задания ==
* [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-го модуля преподавателями курса по непрерывной оптимизации и представляет собой целое число на отрезке [0,10].

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

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

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

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

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

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

==Литература==
* [https://drive.google.com/file/d/0B3Hea5EPX4S0Tk1pbUxPZDQ5WlU/view?usp=sharing Vijay V. Vazirani - Approximation Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0NzQteFJVenJfckk/view?usp=sharing Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0U0NCQlZ2OXc3Tk0/view?usp=sharing A. Schrijver - Combinatorial Optimization: Polyhedra and Efficiency]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0b09JY2ZzeWM5N0U/view?usp=sharing Andras Frank - On Kuhn’s Hungarian Method]
* [http://logic.pdmi.ras.ru/csclub/courses/linearprogramming лекции Максима Бабенко по линейному программированию в Computer Science клубе]

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

2017-05-29T15:36:21Z

Savrus:

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

== Лекции ==
=== Лекция 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 (план) ===
* Теорема Татта-Бержа
* Задача о ветвлении минимального веса, primal-dual алгоритм

===Лекция 6.06 (план) ===
* Задача о многостороннем минимальном разрезе, (2-2/k)-приближение
* Рандомизированное 3/2-приближение для задачи о многостороннем разрезе

===Лекция 13.06 (план) ===
* Оракулы отделения, метод эллипсоидов
* Задача о максимальном разрезе, рандомизированное 2-приближение
* SDP, рандомизированное 0.87-приближение для задачи о максимальном разрезе

== Домашние задания ==
* [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-го модуля преподавателями курса по непрерывной оптимизации и представляет собой целое число на отрезке [0,10].

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

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

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

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

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

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

==Литература==
* [https://drive.google.com/file/d/0B3Hea5EPX4S0Tk1pbUxPZDQ5WlU/view?usp=sharing Vijay V. Vazirani - Approximation Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0NzQteFJVenJfckk/view?usp=sharing Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0U0NCQlZ2OXc3Tk0/view?usp=sharing A. Schrijver - Combinatorial Optimization: Polyhedra and Efficiency]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0b09JY2ZzeWM5N0U/view?usp=sharing Andras Frank - On Kuhn’s Hungarian Method]

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

2017-05-23T12:44:44Z

Savrus:

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

== Лекции ==
=== Лекция 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-го модуля преподавателями курса по непрерывной оптимизации и представляет собой целое число на отрезке [0,10].

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

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

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

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

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

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

==Литература==
* [https://drive.google.com/file/d/0B3Hea5EPX4S0Tk1pbUxPZDQ5WlU/view?usp=sharing Vijay V. Vazirani - Approximation Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0NzQteFJVenJfckk/view?usp=sharing Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms]
* [https://drive.google.com/file/d/0B3Hea5EPX4S0U0NCQlZ2OXc3Tk0/view?usp=sharing A. Schrijver - Combinatorial Optimization: Polyhedra and Efficiency]

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

2017-05-23T12:44:19Z

Savrus:

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

== Лекции ==
=== Лекция 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-го модуля преподавателями курса по непрерывной оптимизации и представляет собой целое число на отрезке [0,10].

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

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

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

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

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

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

==Литература==
[https://drive.google.com/file/d/0B3Hea5EPX4S0Tk1pbUxPZDQ5WlU/view?usp=sharing Vijay V. Vazirani - Approximation Algorithms]
[https://drive.google.com/file/d/0B3Hea5EPX4S0NzQteFJVenJfckk/view?usp=sharing Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms]
[https://drive.google.com/file/d/0B3Hea5EPX4S0U0NCQlZ2OXc3Tk0/view?usp=sharing A. Schrijver - Combinatorial Optimization: Polyhedra and Efficiency]