Комбинаторная оптимизация

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Базовая кафедра Яндекс (Департамент больших данных и информационного поиска)

Статус:

Курс по выбору

Когда читается:

3-й курс, 3, 4 модуль

Преподаватель

Ферник Тома Клеман

Программа дисциплины

Аннотация

Этот курс представляет собой общий обзор основ комбинаторной оптимизации с регулярной практикой на компьютерах на семинарах. Основная цель - узнать, что делать, когда сталкиваешься с трудной NP-задачей.

Цель освоения дисциплины

• Моделирование задачи целочисленного линейного программирования
• Использование решателей SAT, CSP и MILP
• Определение возможности упростить или параметризировать задачу до полиномиальной сложности
• Умение написания алгоритмов аппроксимации, в частности, используя метод "первый-второй"

Планируемые результаты обучения

• Знать основные семейства эвристик.
• использование линейной релаксации для получения нижних границ
• использование метода ветвления и разрезания для сведения релаксации к исходному MILP

Содержание учебной дисциплины

• Генеральная стратегия для решения NP-трудных задач.
• Формализм MILP
• Алгоритм с фиксированным параметром и кернелизация
• Аппроксимация
• Локальный поиск (градиентный спуск, имитация отжига, генетические алгоритмы)
• LP-релаксация, LP-раундинг, LP-алгоритмы
• LP-дуальность
• Примально-дуальный алгоритм
• Ветвление и отсечение
• проект 1: Задача коммивояжёра
• проект 2: задача минимизации одностороннего пересечения

Элементы контроля

• Проект 1
• Проект 2
• Экзамен

Промежуточная аттестация

• 2023/2024 учебный год 4 модуль
  Итог = Округление((П1 + П2 + Э)/3), где Э — оценка за экзамен, П — оценка за проект

Список литературы

Рекомендуемая основная литература

• Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.

Рекомендуемая дополнительная литература

• Panos M. Pardalos, Ding-Zhu Du, Ronald L. Graham. Handbook of Combinatorial Optimization. Springer Science+Business Media, New York, 2013.