О курсе
Организован для стyдентов 3 кyрса потоков ФУПМ.
Цель курса — познакомить студентов с основными задачами дискретной оптимизации, их свойствами, приложениями, способами формализации, сложностью, аппроксимациями, алгоритмами решения и количественными оценками точности этих алгоритмов. Много внимания будет уделено смешанно-целочисленному линейному программированию как универсальному методу решения задач с дискретными ограничениями. Насколько это нужно, вводятся определения разных классов задач выпуклой оптимизации, которые используются в качестве релаксаций задач дискретной оптимизации.
Проблема оптимизации относится к классу задач дискретной оптимизации в широком смысле, если в процессе поиска её решения возникает комбинаторная компонента, в частности, если её допустимое множество состоит из большого числа компонент связности. В отличие от задач выпуклой оптимизации большинство задач дискретной оптимизации являются сложными. Хотя упор сделан на дискретные аспекты, полностью отделиться от непрерывной, в частности, выпуклой оптимизации не удаётся, так как часто метод решения дискретной проблемы состоит в её аппроксимации одной или многими непрерывными задачами (релаксациями), в частности, линейными или полуопределёнными программами.
Лекции сопровождаются семинарами, на которых будут представлены разные универсальные эвристики для решения дискретных задач. Студенты смогут апробировать эти алгоритмы на конкретных задачах, в частности, задаче коммивояжёра.
Ведущие курса
Роланд Хильдебранд
Материалы курса
Экзаменационная программа
Программа лекций
Лекция 1: Введение. Задача о покрытии множествами.
Лекция 2: Задача об упаковке в контейнеры.
Лекция 3: Задача о рюкзаке.
Лекция 4: Хордальные и совершенные графы.
Лекция 5: Раскраска графов I.
Лекция 6: Раскраска графов II.
Лекция 7: Задача о клике I.
Лекция 8: Смешанно-целочисленное линейное программирование -- предобработка, поиск целочисленного решения.
Лекция 9: Отсечения I.
Лекция 10: Отсечения II.
Лекция 11: Полуопределённые релаксации.
Лекция 12: Задача о клике II.
Лекция 13: Задача о максимальном разрезе.
Лекция 14: Квадратичная задача безусловной бинарной оптимизации.
Лекция 15: Программирование в ограничениях.