2024/2025
Дискретная оптимизация и исследование операций (преподается на английском языке)
Статус:
Маго-лего
Когда читается:
1, 2 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Бацына Екатерина Константиновна
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
The course covers modern exact methods for solving combinatorial optimization problems, including methods of branches and bounds, branches and clippings, branches and prices. All algorithms are analyzed on the example of well-known optimization problems, such as the maximum clique problem, the traveling salesman problem, transport routing problems, and so on
Цель освоения дисциплины
- Целями освоения дисциплины является знакомство с современными классическими и прикладными задачами оптимизации, моделями математического программирования, точными алгоритмами ветвей и границ, ветвей и отсечений, ветвей и отсечений и цен и другими современными методами. Изучение данной дисциплины базируется на следующих дисциплинах: • Исследование операций • Разработка программного обеспечения Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: • Задачи математического программирования, алгоритмы решения классических задач исследования операций Основные положения дисциплины могут быть использованы при написании курсовой и дипломной работы.
Планируемые результаты обучения
- По модели математического программирования для задачи студент получает оценку на целевую функцию с помощью Лагранжевой релаксации.
- Студент разрабатывает модель с большим (обычно экспоненциально большим) числом ограничений для задачи, программирует алгоритм ветвей и отсечений для решения задачи и решает задачу с помощью реализованной программы.
- Студент разрабатывает модель с большим (экспоненциально большим) числом переменных, программирует алгоритм ветвей и цен для решения задачи с такой моделью и решает задачу с помощью разработанной программы.
- Студент разрабатывает эвристику для решения задачи, программирует ее и решает задачу с помощью этой программы.
- Студент строит линейную модель по описанию задачи и решает задачу
- Студент строит модель целочисленного программирования по описанию задачи, программирует алгоритм ветвей и границ для решения задачи и решает задачу с помощью написанной программы.
Содержание учебной дисциплины
- Linear problems
- Integer problems. Branch-and-bound method.
- Local search
- Branch-and-cut approach
- Branch-and-price approach.
- Lagrangian relaxation
Промежуточная аттестация
- 2024/2025 2nd module0.4 * Домашние работы (программная реализация алгоритма) + 0.6 * Устный экзамен
Список литературы
Рекомендуемая основная литература
- Andreas S. Schulz, Martin Skutella, Sebastian Stiller, Dorothea Wagner. Gems of Combinatorial Optimization and Graph Algorithms. Springer International Publishing, Switzerland, 2015.
- Du, D., & Pardalos, P. M. (2005). Handbook of Combinatorial Optimization : Supplement Volume B. [Berlin]: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=133080
- Panos M. Pardalos, Ding-Zhu Du, Ronald L. Graham. Handbook of Combinatorial Optimization. Springer Science+Business Media, New York, 2013.
- Pardalos, P. M., Du, D. Z., Graham, R. L. (ed.). Handbook of combinatorial optimization. – Springer, 2013. – 3409 pp.
- Schulz, A. S., Skutella, M., Stiller, S., & Wagner, D. (2015). Gems of Combinatorial Optimization and Graph Algorithms. Cham: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1164017
Рекомендуемая дополнительная литература
- Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.
- Ming-Yang Kao. Encyclopedia of Algorithms. Springer, New York, NY, 2016
- Taha H.A. Operations Research: An Introduction, 10-th Edition, Pearson Education Limited, 2017. – 849 p. – ISBN: 9781292165561
- Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E80A9B59