Optimization: Advanced Level

2020/2021

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

2 year, 1, 2 module

Instructor

Gribanov, Dmitry

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

Аннотация

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

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

• Владеет навыками решения математических задач, возникающих в некоторых прикладных областях
• Знает основные методы дискретной оптимизации
• Знает основные методы линейного и целочисленного программирования
• Знает основные понятия и теоремы. Умеет решать задачи
• Умеет применять на практике методы дискретной оптимизации

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

• Знает основные понятия и теоремы. Умеет решать задачи

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

• Введение в теорию линейной оптимизации.
  Понятие линейной программы. Виды линейных программ: стандартная, каноническая, общая. Симплекс метод, метод искусственного базиса. Зацикливание, виды защиты от зацикливания: лексикографический метод, правило Бленда. Жадная стратегия. Матричное представление симплекс метода. Теория двойственности. Теорема двойственности, теорема дополняющий нежесткости. Метод эллипсоидов.
• Введение в теорию полиэдров.
  Понятие многогранного конуса. Способы зданий многогранных конусов: конечно порожденный конус, конечно определенный конус. Понятие аффинной оболочки и размерности. Теорема Минковского-Фаркаша-Вейля об эквивалентности представлений. Алгоритм построения двойственного описания. Понятие полиэдра. Понятия вершины, фасеты, грани размерности k. Оптимизация линейной функции на полиэдре. Связь с симплекс методом.
• Эвристические алгоритмы комбинаторной оптимизации
  Метод отсечений Гомори. Теорема Шрайвера и ранг Хватала. Метод brunch and bound. Метод brunch and cut, отсечения для задачи TSP. Метод k-OPT для задачи TCP. Локальный поиск. Метод лагранжевой релаксации. Получение нижних и верхних оценок. Применение этих методов на примерах задач TCP и KNAPSACK.
• Базовые алгоритмы для работы с графами.
  Алгоритмы BFS и DFS. Задачи, решаемые BFS: связные компоненты, реберные кратчайшие пути. Задачи решаемые DFS: сильные компоненты связности, Эйлеров обход дерева, эйлеров цикл, поиск мостов, поиск циклов, поиск точек сочленения, топологическая сортировка. Рандомизированный алгоритм поиска мостов и 2-мостов. Задача построения остова минимального веса, упоминание матроидов. Задача о кратчайшем пути. Алгоритмы Форда-Беллмана, Дейкстры, Флойда, Джонсона. Приложение: 3/2-приближенный алгоритм Кристофидеса для решения метрической задачи TSP.
• Использование средства непрерывной оптимизации для решения задач комбинаторной оптимизации.
  Понятие TDI системы. Теорема Эдмондса-Джаилса. Теорема о том, что любая система линеных неравенств может быть преобразована в TDI систему. Критерий целочисленности полиэдра, заданного системой неравенств. Доказательства свойства TDI для полиэдров цепей и антицепей. Свойство TDI для полиэдра задачи о максимальном паросочетании. Полуопределенное программирование. Получение приближенного алгоритма для задачи MAX-SAT на основе полуопределенной релаксации, решаемой методом эллипсоидов.
• Primal-dual подход для решения задач комбинаторной оптимизации.
  Взгляд на задачи комбинаторной оптимизации со стороны теории линейного программирования. Понятие тотальной унимодулярности. Критерий и достаточное условие тотальной унимодулярности. Примеры тотально унимодулярных матриц: матрица инцидентности двудольного графа, матрица инцидентсноти орграфа. Задачи о максимальном двудольном паросочетании и минимальном двудольном совершенном паросочетании. Полиэдры этих задач, доказательство целочисленноссти полиэдров. Понятие primal-dual алгоритма. Получение полиномиального primal-dual алгоритма для данных задач. Задача о максимальном паросочетании (невзвешенном) в графе общего вида. Формула Татта-Бержа. Алгоритм построения максимального паросочетания. Разработка primal-dual алгоритма для задачи построения минимального совершенного паросочетания в взвешенном графе общего вида. Эквивалентность данной задачи задаче о максимальном взвешенном паросочетании.
• Введение в теорию сложности.
  Понятия машины Тьюринга, многоленточной машины Тьюринга, машины RAM. Полиномиальная эквивалентность этих моделей. Тезис Черча. Понятия сводимостей по Карпу и по Тьюрингу. Определение классов P, NP, PSPACE, EXP, примеры задач. Теорема о иерархии. Определение классов NP-hard и NP-complete. Доказательства NP-completeness основных задач комбинаторной оптимизации: SAT, CIRCUIT-SAT, 3-CNF, IS, CLIQUE, VC, ISOMORPHISM, HAMILTONIAN CIRCUIT, TSP, 3-COLORING и др. Классы NP-SEARCH, NP-OPT и их полиномиальная эквивалентность классу NP.
• Матроиды, полиматроиды, субмодулярные функции
  Понятие матроида и жадного алгоритма. Примеры матроидов: равномерный матроид, линейный матроид, циклический матроид и др. Доказательство свойства TDI для полиэдра матроида и полиэдра пересечения двух матроидов. Примеры задач, представляемых в виде пересечения двух матроидов. Алгоритм оптимизации на пересечении двух матроидов. NP-трудность задачи оптимизации на пересечении 3-х матроидов. Полиматроиды и субмодулярные функции. Алгоритм оптимизации субмодулярных функций.

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

• Домашнее задание
• Домашнее задание
• Устный экзамен
• Домашнее задание
• Домашнее задание
• Устный экзамен

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

• Промежуточная аттестация (2 модуль)
  0.3 * Домашнее задание + 0.3 * Домашнее задание + 0.4 * Устный экзамен

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

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

• Верещагин Н.К., Успенский В.А., Шень А. - Колмогоровская сложность и алгоритмическая случайность - Московский центр непрерывного математического образования - 2013 - 575с. - ISBN: 978-5-4439-2012-2 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/56395
• Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012
• Долбилин Н.П. - Жемчужины теории многогранников - Московский центр непрерывного математического образования - 2000 - 40с. - ISBN: 5-900916-48-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9333
• Крупский В. Н. - ТЕОРИЯ АЛГОРИТМОВ. ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ 2-е изд., испр. и доп. Учебное пособие для бакалавриата и магистратуры - М.:Издательство Юрайт - 2019 - 117с. - ISBN: 978-5-534-04817-9 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-algoritmov-vvedenie-v-slozhnost-vychisleniy-444131
• Линейное программирование. Практикум : учеб. пособие / А.С. Шевченко. — М. : ИНФРА-М, 2018. — 297 с. - Режим доступа: http://znanium.com/catalog/product/1007387
• Линейное программирование. Транспортная задача: Учебное пособие / Литвин Д.Б., Мелешко С.В., Мамаев И.И. - Ставрополь:Сервисшкола, 2017. - 84 с.: ISBN - Режим доступа: http://znanium.com/catalog/product/976430
• Трухан А.А., Ковтуненко В.Г. - Линейная алгебра и линейное программирование: учебное пособие - Издательство "Лань" - 2018 - 316с. - ISBN: 978-5-8114-2744-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/99214

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

• Бирюкова Л. Г., Сагитов Р. В. ; Под общ. ред. Татарникова О.В. - ЛИНЕЙНАЯ АЛГЕБРА И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ПРАКТИКУМ. Учебное пособие для СПО - М.:Издательство Юрайт - 2019 - 53с. - ISBN: 978-5-9916-9981-5 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/lineynaya-algebra-i-lineynoe-programmirovanie-praktikum-437932
• Брандин В.Н. - Размерностная сложность. Интеллект - Издательство "Физматлит" - 2008 - 168с. - ISBN: 978-5-9221-0954-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/59512
• Палий И. А. - ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 175с. - ISBN: 978-5-534-04716-5 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/lineynoe-programmirovanie-438834
• Разборов А.А. - Алгебраическая сложность - Московский центр непрерывного математического образования - 2016 - 31с. - ISBN: 978-5-4439-3032-9 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/80160