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

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

2019-06-18T16:56:53Z

Ignat: TSP criterias

== О курсе ==

Курс читается для студентов 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.

Оценка за эту часть выставляется как минимум из 10 и {суммы оценок за три мини-ДЗ + оценка за контрольную работу}

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

Оценка за эту часть выставляется как количество баллов набранных за решение задача контеста. Решенная задача во время самого контеста стоит 2.5 балла, после контеста 1.25 балла.

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

Оценка за эту часть выставляется как {минимум из 15 и {сумма баллов за два практических домашних задания}} / 1.5. Число 15 может быть еще скорректировано в нижнюю сторону.

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

За экзамен выставляется оценка от 0 до 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решения лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

Грейдер для задачи Коммивояжера http://akhmedov.me:50028/tsp/ – в него можно сдавать решения публичных тестов и сравниваться с другими участниками. Имя необходимо указывать в формате "фамилия транслитом маленькими буквами + подчеркивание + имя транслитом маленькими буквами", например: kolesnichenko_ignat

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

'''Критерии оценивания качества решения в задаче коммивояжера.'''
Оценивание производилось следующим образом – было взято три базовых решения:
1) 2-приближение через MST, его оценка бралась за точку отсчета в 0 баллов за тест.
2) качественно написанный 2-OPT (с разными политиками выбора того, какие ребра и как переключать), величина этого решения соответствует оценки в 0.6 балла за тест.
3) решение близкое к оптимальному (лучшее решение с одного из публичных источников по задаче), величина этого решения полагалась равной максимуму в 1 балл за тест.

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

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

==Экзамен==

[https://yadi.sk/i/GP7lXeyKyKfF3Q Программа экзамена]

[https://yadi.sk/d/CWb9JstME0Rntw Здесь будут выкладываться разные статьи, полезные для подготовки]

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

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

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

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

* "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-06-10T08:18:54Z

Ignat:

== О курсе ==

Курс читается для студентов 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.

Оценка за эту часть выставляется как минимум из 10 и {суммы оценок за три мини-ДЗ + оценка за контрольную работу}

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

Оценка за эту часть выставляется как количество баллов набранных за решение задача контеста. Решенная задача во время самого контеста стоит 2.5 балла, после контеста 1.25 балла.

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

Оценка за эту часть выставляется как {минимум из 15 и {сумма баллов за два практических домашних задания}} / 1.5. Число 15 может быть еще скорректировано в нижнюю сторону.

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

За экзамен выставляется оценка от 0 до 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решения лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

Грейдер для задачи Коммивояжера http://akhmedov.me:50028/tsp/ – в него можно сдавать решения публичных тестов и сравниваться с другими участниками. Имя необходимо указывать в формате "фамилия транслитом маленькими буквами + подчеркивание + имя транслитом маленькими буквами", например: kolesnichenko_ignat

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

==Экзамен==

[https://yadi.sk/i/GP7lXeyKyKfF3Q Программа экзамена]

[https://yadi.sk/d/CWb9JstME0Rntw Здесь будут выкладываться разные статьи, полезные для подготовки]

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

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

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

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

* "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-06-09T17:27:22Z

Ignat:

== О курсе ==

Курс читается для студентов 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.

Оценка за эту часть выставляется как минимум из 10 и {суммы оценок за три мини-ДЗ + оценка за контрольную работу}

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

Оценка за эту часть выставляется как количество баллов набранных за решение задача контеста. Решенная задача во время самого контеста стоит 2.5 балла, после контеста 1.25 балла.

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

Оценка за эту часть выставляется как {минимум из 15 и {сумма баллов за два практических домашних задания}} / 1.5. Число 15 может быть еще скорректировано в нижнюю сторону.

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

За экзамен выставляется оценка от 0 до 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решения лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

Грейдер для задачи Коммивояжера http://akhmedov.me:50028/tsp/ – в него можно сдавать решения публичных тестов и сравниваться с другими участниками. Имя необходимо указывать в формате "фамилия транслитом маленькими буквами + подчеркивание + имя транслитом маленькими буквами", например: kolesnichenko_ignat

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

==Экзамен==

[https://yadi.sk/i/GP7lXeyKyKfF3Q Программа экзамена]

[https://yadi.sk/d/CWb9JstME0Rntw Здесь будут выкладываться разные статьи, полезные для подготовки]

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

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

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

* "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-06-06T18:06:54Z

Ignat:

== О курсе ==

Курс читается для студентов 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.

Оценка за эту часть выставляется как минимум из 10 и {суммы оценок за три мини-ДЗ + оценка за контрольную работу}

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

Оценка за эту часть выставляется как количество баллов набранных за решение задача контеста. Решенная задача во время самого контеста стоит 2.5 балла, после контеста 1.25 балла.

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

Оценка за эту часть выставляется как {минимум из 15 и {сумма баллов за два практических домашних задания}} / 1.5. Число 15 может быть еще скорректировано в нижнюю сторону.

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

За экзамен выставляется оценка от 0 до 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решения лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

Грейдер для задачи Коммивояжера http://akhmedov.me:50028/tsp/ – в него можно сдавать решения публичных тестов и сравниваться с другими участниками. Имя необходимо указывать в формате "фамилия транслитом маленькими буквами + подчеркивание + имя транслитом маленькими буквами", например: kolesnichenko_ignat

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

==Экзамен==

[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-06-06T17:40:38Z

Ignat:

== О курсе ==

Курс читается для студентов 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.

Оценка за эту часть выставляется как минимум из 10 и {суммы оценок за три мини-ДЗ + оценка за контрольную работу}

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

Оценка за эту часть выставляется как количество баллов набранных за решение задача контеста. Решенная задача во время самого контеста стоит 2.5 балла, после контеста 1.25 балла.

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

Оценка за эту часть выставляется как {минимум из 15 и {сумма баллов за два практических домашних задания}} / 1.5. Число 15 может быть еще скорректировано в нижнюю сторону.

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

За экзамен выставляется оценка от 0 до 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решения лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

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

==Экзамен==

[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-06-05T21:27:41Z

Ignat:

== О курсе ==

Курс читается для студентов 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решения лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

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

==Экзамен==

[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-06-05T21:26:52Z

Ignat:

== О курсе ==

Курс читается для студентов 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

'''Критерии оценивания качества решения.'''
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решение лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

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

==Экзамен==

[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-06-05T21:26:28Z

Ignat:

== О курсе ==

Курс читается для студентов 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

==== Критерии оценивания качества решения
Для каждого закрытого теста в качестве baseline был выбран ответ жадного алгоритма, за него полагается 0.1 балла. За достижение оптимального ответа в тесте полагается 0.5 балла. Для остальных значений оценка вычисляется линейно исходя из двух указанных точек (например, если значение вашего решение лежит ровно посередине между оптимальным и жадным, то за него полагается 0.3 балла).

Оценки за все 10 закрытых тестов суммируются и округляются вниз до ближайшего полуцелого числа. Таким образом финальная оценка лежит в диапазоне от 0 до 5 баллов. Причем 5 баллов получает только решение нашедшее оптимумы на всех закрытых тестах.

Все тесты к задаче, а также ответы жадного и оптимального алгоритмов для закрытых тестов доступны по ссылке https://yadi.sk/d/2gZG00VoYoSeDA

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

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

==Экзамен==

[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-06-05T20:50:53Z

Ignat:

== О курсе ==

Курс читается для студентов 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===
Метод локального поиска. Его применения к задаче о расстановке ферзей и к задаче о раскраске графа. Метапоиски – метод отжига.

===Лекция 7===
Формулировка задачи TSP в виде линейной программы с экспоненциальным числом условий. Граница Хелда-Карпа. Применение симплекс-метода для рещения TSP на практике.
Метод Branch&Cut решения ILP, метод секущих плоскостей. Секущие плоскости Гомори-Хватала.

===Лекция 8===
Метод эллипсоидов и его применение к построению слабополиномиального решения задачи линейного программирования.
Задача о максимальном разрезе, жадное решение.
Сведение задачи о максимальном разрезе к задаче полуопределенного программирование и построение вероятностного 0.878-приближения.

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

===Семинар 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.

===Семинар 7===
Инструменты для решения задач дискретной оптимизации: GLPK, Gurobi, or-tools. Методика Contraint Programming и её применение к задаче Car-Sequencing. Задача об открытии складов, её формулировка в виде ILP.

===Семинар 8===
Симплекс-метод, построение секущей плоскости из решения найденного симплекс-методом.

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

===Задание 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"

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

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

==Экзамен==

[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-06-05T20:44:40Z

Ignat:

== О курсе ==

Курс читается для студентов 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"

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач https://contest.yandex.ru/contest/12924.

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

==Экзамен==

[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-06-05T15:47:38Z

Ignat:

== О курсе ==

Курс читается для студентов 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"

===Задание 2 (задача коммивояжера, задача об открытии складов, задача о сборке автомобилей)===

'''Дедлайн: 23.59 16 июня. Не опаздывайте, после дедлайна решения не принимаются.'''

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

Контест для сдачи задач появится в ближайшие часы.

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

==Экзамен==

[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-24T09:42:30Z

Ignat:

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

2019-05-18T20:34:17Z

Ignat:

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

2019-04-23T15:01:39Z

Ignat:

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

2019-04-17T11:52:21Z

Ignat:

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

2019-04-17T11:34:55Z

Ignat:

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

2019-04-10T21:31:36Z

Ignat:

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

2019-04-06T16:43:10Z

Ignat:

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

2019-04-02T20:26:12Z

Ignat:

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

2019-03-30T16:05:37Z

Ignat:

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

2019-03-30T16:05:06Z

Ignat:

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

2019-03-30T16:04:16Z

Ignat:

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

2019-03-30T16:03:53Z

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

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

2019-03-30T15:45:59Z

Ignat: Ignat переименовал страницу Дискретная оптимизация в Дискретная оптимизация 2018

#перенаправление [[Дискретная оптимизация 2018]]

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

2019-03-30T15:45:59Z

Ignat: Ignat переименовал страницу Дискретная оптимизация в Дискретная оптимизация 2018

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

Пересдачи будут проходить 4-го и 7-го сентября.
4-го сентября пересдача будет в аудитории Кэмбридж в ШАДе в 10.00 (с 09.55 до 10.05 мы будем ждать вас у проходной).
7-го сентября пересдача будет в аудитории 435 на Кончовском в 10.00.

Правила проведения пересдачи и программа экзамена поступны тут: https://yadi.sk/d/P2NVdCGy3Zrkh9

'''Практика'''. Условие задачи и открытые тесты доступно по следующей ссылке: https://yadi.sk/d/E_h4glrb3acMWJ

Контест доступен по следующей ссылке: https://contest.yandex.ru/contest/8801/problems/

Решения принимаются до 23:59:59 2 сентября вне зависимости от даты пересдачи, на которую приходит студент. Несданное к дедлайну решение практическое части оценивается в 0 баллов.

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

Состоится 27 сентября в 10.00 в аудитории ауд.322. Формат аналогичен теоретической части на пересдаче.

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-09-07T13:01:11Z

Ignat:

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

Пересдачи будут проходить 4-го и 7-го сентября.
4-го сентября пересдача будет в аудитории Кэмбридж в ШАДе в 10.00 (с 09.55 до 10.05 мы будем ждать вас у проходной).
7-го сентября пересдача будет в аудитории 435 на Кончовском в 10.00.

Правила проведения пересдачи и программа экзамена поступны тут: https://yadi.sk/d/P2NVdCGy3Zrkh9

'''Практика'''. Условие задачи и открытые тесты доступно по следующей ссылке: https://yadi.sk/d/E_h4glrb3acMWJ

Контест доступен по следующей ссылке: https://contest.yandex.ru/contest/8801/problems/

Решения принимаются до 23:59:59 2 сентября вне зависимости от даты пересдачи, на которую приходит студент. Несданное к дедлайну решение практическое части оценивается в 0 баллов.

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

Состоится 27 сентября в 10.00 в аудитории ауд.322. Формат аналогичен теоретической части на пересдаче.

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-09-03T12:01:30Z

Ignat:

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

Пересдачи будут проходить 4-го и 7-го сентября.
4-го сентября пересдача будет в аудитории Кэмбридж в ШАДе в 10.00 (с 09.55 до 10.05 мы будем ждать вас у проходной).
7-го сентября пересдача будет в аудитории 435 на Кончовском в 10.00.

Правила проведения пересдачи и программа экзамена поступны тут: https://yadi.sk/d/P2NVdCGy3Zrkh9

'''Практика'''. Условие задачи и открытые тесты доступно по следующей ссылке: https://yadi.sk/d/E_h4glrb3acMWJ

Контест доступен по следующей ссылке: https://contest.yandex.ru/contest/8801/problems/

Решения принимаются до 23:59:59 2 сентября вне зависимости от даты пересдачи, на которую приходит студент. Несданное к дедлайну решение практическое части оценивается в 0 баллов.

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-09-03T07:25:24Z

Ignat: /* Пересдача */

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

Пересдачи будут проходить 4-го и 7-го сентября в аудиториях ШАДа в 10.00 (аудитория Кэмбридж, с 09.55 до 10.05 мы будем ждать вас у проходной).

Правила проведения пересдачи и программа экзамена поступны тут: https://yadi.sk/d/P2NVdCGy3Zrkh9

'''Практика'''. Условие задачи и открытые тесты доступно по следующей ссылке: https://yadi.sk/d/E_h4glrb3acMWJ

Контест доступен по следующей ссылке: https://contest.yandex.ru/contest/8801/problems/

Решения принимаются до 23:59:59 2 сентября вне зависимости от даты пересдачи, на которую приходит студент. Несданное к дедлайну решение практическое части оценивается в 0 баллов.

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-08-03T08:56:05Z

Ignat:

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

Пересдачи будут проходить 4-го и 7-го сентября в аудиториях ШАДа в 10.00.

Правила проведения пересдачи и программа экзамена поступны тут: https://yadi.sk/d/P2NVdCGy3Zrkh9

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-06-28T11:35:17Z

Ignat:

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-06-28T11:29:10Z

Ignat:

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале (при этом балл может быть произвольной дробности), правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = round(0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3), где round – это функция арифметического округления.

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-06-11T08:23:34Z

Ignat:

== О курсе ==

Курс читается для студентов 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/AAAAAFD1-ZdchZS1FoOduA

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

Оставить отзыв на курс: TODO

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

{| class="wikitable"
|-
! Группа !! Преподаватель !! Связь !! Страница !! Расписание
|-
| МОП 151 || Лахтанов Иван || telegram: @ivan_lakhtanov || ? || Пятница 15:10 - 16:30
|-
| МОП 152 || Колесниченко Игнат || 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 || Вторник 15.10-16.30
|-
| АПР 153 || Суханов Николай || - || ? || ?
|-
| АДИС 154 || Савченко Руслан || - || ? || ?
|-
| РС 155 || Ахмедов Максим || telegram: @max_akhmedov, http://t.me/discrete_opt_155 || ? || ?
|-
| ТИ 156 || Саакян Вильям || telegram: @wilwell || ? || Вторник 10:30 - 11:50
|-
|}

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

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

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

В курсе предусмотрено 3 домашних задания – 2 практических и 1 теоретическое. За каждое домашнее задание выставляется оценка по 10-бальной шкале, правила получения оценки будут оговариваться при публикации домашнего задания.

Итоговая оценка вычисляется исходя из оценок за домашние задания

Oитоговая = 0.33 * OДЗ1 + 0.33 * ОДЗ2 + 0.34 * ОДЗ3

Также на семинарах иногда будут выдаваться небольшие домашние задания. Их решение будет засчитываться как доп. баллы в домашних заданиях (доп. баллы к исходной оценке в ДЗ, а не к результирующей).

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

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

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

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

== Лекции ==

'''Лекция 1''' (3 апреля). Метод Branch&Bound решения оптимизационных задач. Задача о рюкзаке: 2-приближение, динамическое программирование по весам и по стоимостям.

'''Лекция 2''' (10 апреля). Задача о рюкзаке: PTAS с временем работы (n^(1+1/eps)), FPTAS с временем работы O(n^3 * 1 /eps). Напоминание об переменных нежесткости и условиях дополняющей нежесткости.

'''Лекция 3''' (17 апреля). Методика Primal-Dual построения решений для комбинаторных задач. Применение Primal-Dual к задаче о поиске кратчайших путей.

'''Лекция 4''' (24 апреля). Задача о взвешенном паросочетании в двудольном графе, применение Primal-Dual для её решения.

'''Лекция 5''' (15 мая). Поиск паросочетаний в недвудольных графах. Алгоритм Эдмонса. Минимаксная формула для размера паросочетания в произвольном графе (формула Татта-Бержа).

'''Лекция 6''' (22 мая). Симплекс-метод, геометрическая интерпретация, базисные перменные и эффективная реализация (табличный симплекс-метод).

'''Лекция 7''' (29 мая). Метод эллипсоидов, решение выпуклых задач оптимизации с помощью метода отделяющей плоскости. Задача о разрезе максимального веса, 0.5-приближение с помощью дерандомизации. Построение 0.878-приближения с помощью сведения к задаче полуопределенного программирования.

'''Лекция 8''' (5 июня). Метод локального поиска. Применение его к задаче о ферзях. Применение к задаче о раскраске графа. Алгоритм sqrt(n) раскраски 3-раскрашиваемого графа.

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

'''Семинар 1''' (2-6 апреля). Напоминание о линейном и целочисленном программирование. Построение двойственных программ. Задача о поиске максимального паросочетания в двудольном графе.

'''Семинар 2''' (9-13 апреля).

'''Семинар 3''' (16-20 апреля).

'''Семинар 4''' (23-24 апреля). Задача Set-Cover. Решение с помощью округления ЛП. Примерение Primal-Dual для построение f-приближения. Вероятностный способ округления для построения log(n)-приближения.

'''Семинар 5''' (14-18 мая). Разложение Эдмонса-Галлаи, его полученеи из алгоритмы Эдмонса и его свойства. Задача о существовании совершенного паросочения в 3-регулярном графе без мостов.

'''Семинар 6''' (21-25 мая). Задача о поиске упаковки вершинно-непересекающихся T-путей, минимаксная формула Галлаи. Связь с задачей о паросочетаниях.

'''Семинар 7''' (28 мая - 1 июня). Программирование в ограничениях (CP), базовая концепция. Примеры решения задач с помощью CP: задача о ферзях, задача о магической последовательности, задача о сборке автомобилей.

'''Семинар 8''' (4-8 июня). Задача коммивояжера. Алгоритмы для 2 и 1.5 приближений. Алгоритмы локального поиска в данной задаче: 2-OPT, 3-OPT, эвристика Ли-Кернигана.

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

=== Домашнее задание 1 (практика)===

'''Дедлайн: 14 мая 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/t9yrhBy-3UiVgA

Контест для сдачи задач: https://contest.yandex.ru/contest/8104/

Грейдер для задачи о рюкзаке: http://akhmedov.me:50010/knapsack

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

==== Критерий оценки задачи о рюкзаке ====
Оценивание производилось на закрытых тестах. Оценка ставится в зависимости от отличия вашего решения и оптимального решения. Также в случае отсутствия отчета или плохо написанного отчета семинарист вправе снять еще до 1 балла.

Суммарная ошибка 0 – 6 баллов.

Суммарная ошибка <200 – 5 баллов.

Суммарная ошибка <1500 – 4 балла.

Суммарная ошибка <5000 – 3 балла.

Суммарная ошибка <15000 – 2 балла.

Суммарная ошибка <21000 – 1 балл.

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

Приватные тесты: https://yadi.sk/d/1n9vMPTi3XLFiM

=== Домашнее задание 2 (теория)===

'''Дедлайн: 2 июня 23:59'''

В домашнем задании требуется решить 5 теоретических задач, условия: https://yadi.sk/i/o4gtEhpA3VywLM

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

Решения настоятельно рекомендуется записывать в latex-е.

Оценка будет выставлять по формуле min(10, баллы за решение + баллы за семинар 1 + баллы за семинар 2)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 2".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

=== Домашнее задание 3 (практика)===

'''Дедлайн: 25 июня 23:59'''

В домашнем задании требуется решить три практических задачи, архив с условием: https://yadi.sk/d/7fEE0CuN3Xk5bJ

Контест для сдачи задач: https://contest.yandex.ru/contest/8422

Оценка будет выставлять по формуле min(10, баллы за решение)

Задание следует отправлять на почту discret.opt.hse@gmail.com.
В заголовке письма с решением указывайте "[Название группы] ФИО Домашнее задание 3".
В случае вопроса добавляйте в заголовок письма слово "вопрос".

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

* "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] - справочник с описанием эвристических алгоритмов оптимизации.

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

* [[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/ много примеров)).

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

2018-06-07T10:46:09Z

Ignat: Лекции и семинары

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

2018-06-04T22:52:24Z

Ignat:

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

2018-06-04T22:48:36Z

Ignat: Критерии для рюкзака

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

2018-05-16T08:43:25Z

Ignat:

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

2018-05-16T08:41:13Z

Ignat:

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

2018-05-16T08:40:45Z

Ignat:

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

2018-04-24T10:46:17Z

Ignat:

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

2018-04-24T10:45:58Z

Ignat:

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

2018-04-24T10:45:31Z

Ignat:

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

2018-04-24T10:44:40Z

Ignat:

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

2018-04-24T10:27:44Z

Ignat:

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

2018-04-04T14:21:39Z

Ignat:

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

2018-04-04T12:28:25Z

Ignat:

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

2018-04-04T12:27:19Z

Ignat:

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

2018-04-04T12:26:26Z

Ignat:

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

2018-04-04T12:26:11Z

Ignat:

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

2018-04-04T12:25:09Z

Ignat: Правки

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

2018-04-04T12:23:55Z

Ignat: