Алгоритмы дискретной оптимизации (ЕНС)

Адрианов Н.М., Иванов А.Б.

(весенний семестр)

В весеннем семестре 2022 г. занятия по спецкурсу начнутся 12 февраля.

Когда: суббота, 16:50

Где: занятия по спецкурсу проходят дистанционно через Zoom.

Ссылка на конференцию ZOOM: https://us02web.zoom.us/j/5099893290?pwd=WUlPQnp1ZWhpRkdjMjQrVWFQcy9jQT09 пароль 1728

Канал в telegram для организационных вопросов: https://t.me/joinchat/FvIUuTJwM0g2YzYy

Темы спецкурса

1. Линейное программирование. Двойственность в линейном программировании. Симплекс-метод.

2. Целочисленное линейное программирование. Метод ветвей и границ. Метод Гомори. Применение ILP-солверов для решения комбинаторных задач.

3. NP-задачи - задачи поиска и задачи оптимизации. Сведение и NP-полные задачи. NP-полнота задачи SAT.

4. Алгоритмы SAT-солверов (DPLL, CDCL). Применение SAT-солверов для решения промышленных и математических задач.

5. Доказательство NP-полноты разных задач (клика, вершинное покрытие, раскраска графа, 3-дольное сочетание, ILP, рюкзак, коммивояжер, …).

6. Приближенные методы решения NP-полных задач. Сведение к ILP, релаксация и округление. Рандомизированное округление. Результаты о границах приближенных алгоритмов для разных задач.

7. Эвристические алгоритмы: локальный поиск и генетические алгоритмы.

8. Компьютер играет в шахматы, го, … AlphaZero: Monte-Carlo Tree Search и обучение с подкреплением. Применение идей AlphaZero в задаче раскраски графа.

Задания по темам спецкурса

Первоапрельская статья М.Гарднера, png с картой и файл с описанием графа

Статья Карпа про 21 NP-полную задачу