Дискретная оптимизация

2020/2021

Учебный год

RUS

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

6

Кредиты

Кто читает:

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

Статус:

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

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

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

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

Колесниченко Игнатий Игоревич

Лахтанов Иван Андреевич

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

Аннотация

В рамках курса будут изучены различные задачи дискретной оптимизации (например, задача о рюкзаке, поиск паросочетаний в двудольных графах, в том числе взвешенных и пр.), также будут изучены основные техники решения NP-трудных комбинаторных задач, такие как метод ветвей и границ, метод программирования с ограничениями, методы локального поиска. Кроме того, будет изучены понятия линейных и целочисленных программ и вытекающие отсюда способы решения задач дискретной оптимизации

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

• Целями освоения дисциплины является получение студента основ дискретной оптимизации, освоение методов формулирования задач в виде задачи дискретной оптимизации, а также освоение базовых методов и инструментов для эффективного решения таких задач

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

• Уметь формулировать оптимизационные задачи в виде задач дискретной оптимизации.
• Строить линейные программа и двойственные к ним.
• Применять прямо-двойственный метод.
• Знать приемы, применяемые для решения следующих задач: задача о рюкзаке, поиск взвешенных паросочетаний в двудольном графе, задача покрытия множества, цикруляции минимальной стоимости в графах.
• Знать и уметь применять методы решения линейных программ.
• Формулировать задачи в виде задач программирования с ограничениями и уметь применять инструменты для решения таких задач.
• Применять различные инструменты для решения задач дискретной оптимизации.

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

• Метод ветвей и границ для решения задач комбинарторной оптимизации.
  Напоминание о линейных и целочисленных программах. Применение метода ветвей и границ на примере задачи о рюкзаке
• Задача о рюкзаке
  2-приближение, различные методы построения eps приближений.
• Программирование с ограничения
  общая схема метода, его внутреннее устройство. Методы построения ограничений
• Линейное программирование
  Еще раз напоминаем базовые факты. Напоминаем про условия дополняющей нежесткости
• Поиск кратчайших путей с помощью прямо-двойственного метода
• Задача о взвешенных паросочетаниях в двудольных графах. Её решение с помощью прямо-двойственного метода.
• Метод эллипсоидов для решения задач линейного программирования. Метод отсекающих плоскостей.
• Локальный поиск, примеры его использования в разных задачах. Различные стратегии поиска (метод отжига и пр.).
• Задача о цикле минимальной средней стоимости. Алгоритм Карпа
• Циркуляции минимальной стоимости. Остаточные сети. Проталкивание вдоль циклов минимальной средней стоимости. Сильно полиномиальный алгоритм.

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

• Накопленая оценка
• Экзамен
  Оценка выставляется по накопленной, экзамен не проводится

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

• Промежуточная аттестация (4 модуль)
  0.67 * Накопленая оценка + 0.33 * Экзамен

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

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

• Седжвик Р. - Алгоритмы на С++ - Национальный Открытый Университет "ИНТУИТ" - 2016 - 1772с. - ISBN: - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100565

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

• Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач: Учебное пособие / Струченков В.И. - М.:СОЛОН-Пр., 2016. - 192 с.: ISBN 978-5-91359-181-4