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

Бакалавриат 2023/2024

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Базовая кафедра Яндекс

Где читается: Факультет компьютерных наук

Когда читается: 3-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Ферник Тома Клеман

Язык: русский

Кредиты: 6

Контактные часы: 80

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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