Дискретная оптимизация
В данный момент курс ведётся на потоке ПМИ школы ПМИ МФТИ альтернативным к курсу функционального программирования. В разных версиях курс читался в МФТИ с 2011 года в качестве спецкурса и основного курса.
Важные новости курса
Логистика курса
- Студенты, которые сдают только курс ДО, могут сдать его по одной из двух «дорожек»
- theory track: пишут тесты по теории на семинарах и зачётную работу по теории,
- coding track: пишут программы на Python 3, а в конце семестра сдают письменно тест на определения и формулировки с заранее известным перечнем возможных вопросов
Задания
- Файл с задачами семинаров и домашних заданий theory track размещён по ссылке.
Лекции
План лекций
- Отличительные особенности задач дискретной оптимизации. Обзор постановок классических задач дискретной оптимизации: покрытие множествами, вершинное покрытие, кратчайший путь, минимальное остовное дерево, задачи о паросочетании, задача о назначениях, задачи теории расписаний, задачи упаковки (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-трудность точного решения задачи реоптимизации в метрической задаче коммивояжёра при увеличении веса одного ребра. Приближённые алгоритмы реоптимизации с показателем аппроксимации, лучшим, чем у алгоритма Кристофидеса, при увеличении веса одного ребра и при добавлении одной вершины в граф.
Полезные ссылки
Литература
- С. Дасгупта, Х. Пападимитриу, В. Вазирани. Алгоритмы. М.: МЦНМО, 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.