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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

О курсе

Курс читается для студентов 3-го курса ПМИ ФКН ВШЭ в 4 модуле.

Лектор: Игнат Колесниченко

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

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

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

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

Семинары

Группа Преподаватель Связь Страница
- Колесниченко Игнат 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 в задаче о рюкзаке.

Семинары

Семинар 1

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

Семинар 2

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

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

Пересдача

Комиссия

Полезные материалы

Рекомендуемая литература

 * "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] - интересные рассуждения по поводу того, как генерировать сложные тесты для задачи о рюкзаке.
 * ["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] - справочник с описанием эвристических алгоритмов оптимизации.

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

 * [Визуализатор маршрута коммивояжёра] (вершины подаются в 0-индексации)
 * Курс по дискретной оптимизации на [Coursera]. Содержит хорошие видео-лекции по Constraint Programming и Local Search.

Библиотеки для решения задач оптимизации

 *  [Google Optimization Tools] (C++, Python, Java, C#) - фреймворк для решения задач дискретной оптимизаций. Позволяет программировать в парадигме Constraint Programming. Содержит инструменты для решения задач линейного программирования. ([Более полная документация])
 * [Numberjack] (Python)
 * [Choco] (Java)
 * [Gecode] (C++)
 * [MiniZinc] (MiniZinc) - Довольно выразительный язык для CP. Есть ((http://www.hakank.org/minizinc/ много примеров)).