Александр дайняк
Дискретная оптимизация
О курсе
Мы рассмотрим в курсе общие подходы к решению задач дискретной оптимизации, и по окончании курса его слушатели будут уверенно себя чувствовать, когда столкнуться с практически любой поставленной на естественном языке задачей оптимизации: все этапы — от построения сбалансированной математической модели до написания эффективных алгоритмов её обсчёта — мы рассмотрим.
Команда курса
Александр Дайняк
Лектор
Артем Курносов
Семинарист
Программа курса
Постановка задач дискретной оптимизации.
Отличия от задач непрерывной/гладкой/выпуклой оптимизации.
Напоминание определений из сложности алгоритмов.
Задачи с бинарным ответом. Сводимость, полиномиальная сводимость (по Тьюрингу, по Карпу, другие виды). Переход между задачами распознавания, оценивания и поиска. Сложностные классы P, NP, NP-hard. Начальные све́дения о сложностном статусе основных задач дискретной оптимизации.



Поиск в ширину/глубину. Branch-and-bound.
Beam-поиск на примере задачи о рюкзаке.
A*-поиск.
Пример применения A* к задаче о кратчайшем пути на графе дорожной сети.
Варианты A*-поиска: IDA* (iterative deepening A*) и другие.
Основные понятия локального поиска.
Свойства систем окрестностей. Локальный поиск переменной глубины: подход Кернигана—Лина.
Надстройки над локальным поиском.
Моделирование отжига, эволюционные подходы, табу-поиск.
Программирование в ограничениях (constraint programming) как альтернативная парадигма программирования.
Сходства и различия с императивным и функциональным программированием. Целочисленное линейное программирование как основной математический инструмент для программирования в ограничениях.
Основы языка MiniZinc.
Типы данных, циклы, логические выражения, вывод. Разделение модели и данных. Глобальные vs. локальные ограничения. Развёртка ("компиляция") программы в язык FlatZinc. Основные солверы, поддерживающие FlatZinc: Gecode, Chuffed, COIN-BC.
Архитектура типичного constraint propagation солвера.
Реализация некоторых глобальных ограничений.
Стратегии перезапуска.
Перезапуск с использованием статистики предыдущих запусков. Последовательность Луби.
Введение избыточных переменных и ограничений. Покрывающие ограничения.
Избавление от симметрий в задачах оптимизации.
Существующие глобальные ограничения.
Мультипредставление структур данных в программах и их связывание.
Мультипредставление структур данных в программах и их связывание.
Large neighborhood search.
Задание дискретных ограничений на языке ЦЛП.
Двойственность в ЛП. Двойственность как сертифицируемость.
Прямо-двойственные алгоритмы.