Бакалавриат
2025/2026
Комбинаторная оптимизация
Статус:
Курс по выбору (Прикладная математика и информатика)
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 3, 4 модуль
Охват аудитории:
для своего кампуса
Преподаватели:
Ферник Тома Клеман
Язык:
английский
Кредиты:
5
Контактные часы:
80
Course Syllabus
Abstract
Этот курс представляет собой общий обзор основ комбинаторной оптимизации с регулярной практикой на компьютерах на семинарах. Основная цель - узнать, что делать, когда сталкиваешься с трудной NP-задачей.
Learning Objectives
- Моделирование задачи целочисленного линейного программирования
- Использование решателей SAT, CSP и MILP
- Определение возможности упростить или параметризировать задачу до полиномиальной сложности
- Умение написания алгоритмов аппроксимации, в частности, используя метод "первый-второй"
Expected Learning Outcomes
- Знать основные семейства эвристик.
- использование линейной релаксации для получения нижних границ
- использование метода ветвления и разрезания для сведения релаксации к исходному MILP
Course Contents
- Генеральная стратегия для решения NP-трудных задач.
- Формализм MILP
- Алгоритм с фиксированным параметром и кернелизация
- Аппроксимация
- Локальный поиск (градиентный спуск, имитация отжига, генетические алгоритмы)
- LP-релаксация, LP-раундинг, LP-алгоритмы
- LP-дуальность
- Примально-дуальный алгоритм
- Ветвление и отсечение
- проект 1: Задача коммивояжёра
- проект 2: задача минимизации одностороннего пересечения
Interim Assessment
- 2025/2026 4th moduleИтог = Округление((П1 + П2 + Э)/3), где Э — оценка за экзамен, П — оценка за проект
Bibliography
Recommended Core Bibliography
- Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.
Recommended Additional Bibliography
- Panos M. Pardalos, Ding-Zhu Du, Ronald L. Graham. Handbook of Combinatorial Optimization. Springer Science+Business Media, New York, 2013.