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

В данный момент курс ведётся на потоке ПМИ школы ПМИ МФТИ альтернативным к курсу функционального программирования. В разных версиях курс читался в МФТИ с 2011 года в качестве спецкурса и основного курса.

Важные новости курса

• Прошлогодний (2017) открытый список вопросов для сдающих курс по coding track.

Логистика курса

• Студенты, которые сдают только курс ДО, могут сдать его по одной из двух «дорожек»
  • theory track: пишут тесты по теории на семинарах и зачётную работу по теории,
  • coding track: пишут программы на Python 3, а в конце семестра сдают письменно тест на определения и формулировки с заранее известным перечнем возможных вопросов

Задания

• Файл с задачами семинаров и домашних заданий theory track размещён по ссылке.

Лекции

• Слайды некоторых лекций прошлого года можно найти по ссылке.
• Лекция Renato Werneck по задаче о кратчайшем пути, слайды 20—36.

План лекций

• Отличительные особенности задач дискретной оптимизации. Обзор постановок классических задач дискретной оптимизации: покрытие множествами, вершинное покрытие, кратчайший путь, минимальное остовное дерево, задачи о паросочетании, задача о назначениях, задачи теории расписаний, задачи упаковки (bin packing, рюкзак), задачи о потоках (поток наибольшей величины, поток наименьшей стоимости, мультипродуктовые потоки), транспортная задача (задача Хичкока), задача коммивояжёра.
• Локальный поиск как широкий общий подход к решению задач дискретной оптимизации. Системы окрестностей. Пример системы окрестностей в задаче TSP: компромисс между силой окрестности и размером. Пример, в котором 2-окрестность не позволяет достичь глобального оптимума. Эвристика Кернигана—Лина: локальный поиск переменной глубины. Надстройки над локальным поиском: имитация отжига и табу-поиск.
• Несуществование полиномиально обозримой точной системы окрестностей в задаче TSP (в предположении \(\mathrm{P}\neq \mathrm{NP}\)). Локальные жадные эвристики в задаче TSP, не укладывающиеся явно в парадигму локального поиска (не переходящие от цикла к циклу, а строящие цикл с нуля). Показатели качества работы эвристических (приближённых) алгоритмов: appproximation ratio и domination number. Алгоритм ближайшего соседа (nearest neighbor): идея, теорема о том, что approximation ratio оценивается сверху \(O(\log \text{#вершин})\).
• Дискретная линейная задача о подмножестве (DLS problem). Задачи TSP и MST как частные случаи DLS-задач минимизации; переход к максимизации. Наследственные системы. Базы и циклы. Ранг и нижний ранг множества, ранговый разброс. Матроиды: эквивалентные определения, примеры. Оценка качества работы жадного алгоритма на наследственной системе через её ранговый разброс. Следствие о корректности жадного алгоритма построения кратчайшего остовного дерева. Оценка рангового разброса через ограничение на число циклов. Субмодулярность ранговой функции матроида. Пересечение матроидов. Оценка числа циклов для наследственной системы через число матроидов в пересечении. Вероятность единственности решения задачи DLS при случайном выборе весов: лемма об изолировании и два её доказательства (Дж. Спенсера и Н. Та-Шмы).
• Алгоритмы Прима и Борувки для решения задачи MST: примеры, реализация (без использования куч). Алгоритм Прима с использованием фибоначчиевых куч.
• Задачи о распределении дискретного однородного ресурса: задача дискретного максимина, максимизация суммы вогнутых функций. Критерии оптимальности (принцип уравнивания Гермейера, критерий Гросса). Два алгоритма решения задачи дискретного максимина. Оптимизация произведения при фиксированной сумме.
• Напоминание основных понятий из линейного программирования. Задача в стандартной и канонической формах. Переход от неравенств к равенствам и обратно. Геометрия задачи: симплекс-алгоритм как локальный поиск по вершинам многогранника.
• Пример многогранника, на котором при некоторых условиях симплекс-алгоритму может потребоваться экспоненциально много шагов: теорема Кли—Минти. Верхняя оценка на число шагов «везучего симплекс-метода»: теорема Калаи—Клейтмана о диаметре графа многогранника.
• Понятие о сглаженном анализе алгоритмов (smoothed analysis): среднее между анализом на случайных входах и анализом худшего случая. Теорема Спилмана—Тенга о симплекс-методе.
• Двойственность в линейном программировании: решение двойственной задачи как сертификат оптимальности решения прямой задачи. Исключение Фурье—Моцкина. Лемма Фаркаша: существование сертификата неразрешимости системы линейных неравенств. Вывод теоремы о сильной двойственности из леммы Фаркаша. Экономическая интерпретация двойственности в задаче торга.
• Постановки задачи TSP в терминах ЦЛП. Условия Миллера—Таккера—Землина (полиномиальное количество неравенств в задаче TSP). Замечание «о некатастрофичности экспоненциального числа ограничений в задачах ЛП».
• Простой «комбинаторный» алгоритм для задачи о вершинном покрытии (ВП) с approximation ratio = 2. Постановка задачи о взвешенном вершинном покрытии (ВВП) в терминах целочисленного линейного программирования. Алгоритм решения задачи ВВП вида «решаем задачу ЛП → округляем»; утверждение о том, что достигается approximation ratio = 2. Формулировка двойственной задачи к задаче ВВП: потенциалы на рёбрах. «Комбинаторный» (без использования ЛП) алгоритм решения задачи ВВП на основе двойственности; доказательство того, что для этого алгоритма approximation ratio = 2.
• Общая задача о покрытии (эквивалентная задаче о покрытии множеств). Формулировка в терминах матриц. Постановка в виде ЦЛП, формулировка двойственной задачи. Теорема о том, что размер/вес жадного покрытия не больше, чем в \(\ln k\) раз, превышает размер/вес оптимального (где \(k\) — максимальное число единиц в строке). Достижимость (по порядку) этой оценки. Оценка веса жадного покрытия через вес оптимального при ограниченных весах отдельных строк.
• Задача построения паросочетания максимальной мощности в произвольном графе. Увеличивающие пути (утверждение о том, что паросочетание немаксимально ⇔ есть увеличивающий путь). Проблема с поиском увеличивающих путей при отсутствии двудольности: цветки. Утверждения о сжатии цветков. Алгоритм Эдмондса.
• Модификации алгоритма Дейкстры для быстрого практического решения задачи о кратчайшем пути: «двухсторонний» алгоритм Дейкстры, использование landmarks (в случае неравенства треугольника).
• Алгоритм Флойда—Уоршелла поиска кратчайших путей и циклов отрицательного веса.
• Задача о потоке минимальной стоимости (и заданной величины). Два алгоритма: постепенная минимизация стоимости потока при неизменной величине; приращение величины за счёт минимально возможного приращения стоимости.
• «Биологические» метаэвристики: генетические алгоритмы, алгоритмы муравьиных колоний. Иллюстрация на задачах shortest path и TSP.
• Метод ветвей и границ.
• Задачи исчерпывающего перебора сложных дискретных объектов. Подход Рида: упорядоченное перечисление. Метод Ависа—Фукуды: обращение локального поиска.
• Онлайн-оптимизация. Задача «покупать/арендовать». «Задача секретаря». Анализ алгоритма кеширования LRU (Least Recently Used). Эвристические алгоритмы в задаче Bin Packing.
• О понятии реоптимизации. NP-трудность точного решения задачи реоптимизации в метрической задаче коммивояжёра при увеличении веса одного ребра. Приближённые алгоритмы реоптимизации с показателем аппроксимации, лучшим, чем у алгоритма Кристофидеса, при увеличении веса одного ребра и при добавлении одной вершины в граф.

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

• Claire Mathieu’s courses on approximation algorithms on Coursera: Part 1 and Part 2
• Pascal Van Hentenryck’s course Discrete Optimization on Coursera.
• James Stuckey’s course Modeling Discrete Optimization on Coursera.
• Friedrich Eisenbrand’s course Linear and Discrete Optimization on Coursera.
• Ant Colony Optimization and Evolutionary Multiobjective Optimization demos on Wolfram Demonstrations Project.
• Graphical Linear Programming for Two Variables, Graphical Linear Programming for Three Variables, The Fundamental Theorem of Linear Programming and Graph of Inequalities demos on Wolfram Demonstrations Project.
• Бесплатный пакет для решения задач линейной оптимизации LPSolve. Для многих языков программирования существуют библиотеки, позволяющие пользоваться функциями LPSolve. Пример скрипта для LPSolve.
• Мощная программная среда для решения оптимизационных задач IBM ILOG CPLEX с собственным языком программирования OPL. Можно бесплатно скачать и пользоваться в течение 90 дней.
• Каталог прикладных задач, в которых применяется задача о паросочетании
• Сайт, целиком посвящённый TSP, включающий каталог прикладных задач
• TSP Software — каталог солверов для задачи TSP
• Слайды Дэвида Джонсона по задаче коммивояжёра
• Каталог статей по smoothed analysis

Литература

• С. Дасгупта, Х. Пападимитриу, В. Вазирани. Алгоритмы. М.: МЦНМО, 2014.
• А. А. Корбут, Ю. Ю. Финкельштейн. Дискретное программирование. М.: Наука, 1969.
• Х. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. (Ch. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.)
• Т. Саати. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. М.: Мир, 1973. (T. L. Saati. Optimization in Integers and Related Extremal Problems. McGraw-Hill, 1970.)
• И. Х. Сигал, А. П. Иванова. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Физматлит, 2003.
• D. Avis, K. Fukuda. Reverse search for enumeration // Discrete Appl. Math. 65. 1996. pp. 21–46.
• W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver. Combinatorial Optimization. Wiley, 1997.
• C. P. Gomes, H. Kautz, A. Sabharwal, B. Selman. Satisfiability Solvers // Handbook of Knowledge Representation. Elsevier, 2008.
• H. J. Greenberg. Myths and Counterexamples in Mathematical Programming
• S. Jukna. Extremal Combinatorics (2nd edition). Springer, 2011.
• B. Korte, J. Vygen. Combinatorial Optimization: Theory and Algorithms (5th edition). Springer-Verlag, 2014. Имеется перевод на русский язык: Б. Корте, Й. Фиген. Комбинаторная оптимизация. Теория и алгоритмы. М.: Изд-во МЦНМО, 2015.
• J. Matoušek, B. Gärtner. Approximation Algorithms and Semidefinite Programming. Springer, 2012.
• J. Matoušek, B. Gärtner. Understanding and Using Linear Programming. Springer, 2007.
• R. C. Read. Every One a Winner or How to Avoid Isomorphism Search When Cataloguing Combinatorial Configurations // Annals of Discrete Math. 2. 1978. pp. 107–120.
• A. Schrijver. A Course in Combinatorial Optimization. 2013.
• L. Trevisan. Combinatorial Optimization: Exact and Approximate Algorithms. 2011.
• V. V. Vazirani. Approximation Algorithms. Springer, 2002.
• V. V. Vazirani. A proof of the MV matching algorithm. 2014.

  К лекции по реоптимизации:

• H.-J. Böckenhauer, J. Hromkovič, T. Mömke, P. Widmayer. On the Hardness of Reoptimization // SOFSEM 2008: Theory and Practice of Computer Science. Lecture Notes in Computer Science, Volume 4910, 2008. P. 50-65.
• N. Guttmann-Beck,. R. Hassin,. S. Khuller, B. Raghavachari. Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem // Algorithmica, 2000, Vol. 28. Pp. 422-437.
• G. Ausiello, B. Escoffier, J. Monnot, V. Paschos. Reoptimization of minimum and maximum traveling salesman’s tours // Journal of Discrete Algorithms 7 (2009). 453–463.