Master
2024/2025
Discrete optimization and operations research
Type:
Compulsory course (Data Mining)
Area of studies:
Applied Mathematics and Informatics
Delivered by:
Department of Applied Mathematics and Informatics
When:
1 year, 1, 2 module
Mode of studies:
offline
Open to:
students of all HSE University campuses
Instructors:
Ekaterina K. Batsyna
Master’s programme:
Интеллектуальный анализ данных
Language:
English
ECTS credits:
6
Course Syllabus
Abstract
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
Learning Objectives
- Целями освоения дисциплины является знакомство с современными классическими и прикладными задачами оптимизации, моделями математического программирования, точными алгоритмами ветвей и границ, ветвей и отсечений, ветвей и отсечений и цен и другими современными методами. Изучение данной дисциплины базируется на следующих дисциплинах: • Исследование операций • Разработка программного обеспечения Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: • Задачи математического программирования, алгоритмы решения классических задач исследования операций Основные положения дисциплины могут быть использованы при написании курсовой и дипломной работы.
Expected Learning Outcomes
- По модели математического программирования для задачи студент получает оценку на целевую функцию с помощью Лагранжевой релаксации.
- Студент разрабатывает модель с большим (обычно экспоненциально большим) числом ограничений для задачи, программирует алгоритм ветвей и отсечений для решения задачи и решает задачу с помощью реализованной программы.
- Студент разрабатывает модель с большим (экспоненциально большим) числом переменных, программирует алгоритм ветвей и цен для решения задачи с такой моделью и решает задачу с помощью разработанной программы.
- Студент разрабатывает эвристику для решения задачи, программирует ее и решает задачу с помощью этой программы.
- Студент строит линейную модель по описанию задачи и решает задачу
- Студент строит модель целочисленного программирования по описанию задачи, программирует алгоритм ветвей и границ для решения задачи и решает задачу с помощью написанной программы.
Course Contents
- Linear problems
- Integer problems. Branch-and-bound method.
- Local search
- Branch-and-cut approach
- Branch-and-price approach.
- Lagrangian relaxation
Interim Assessment
- 2024/2025 2nd module0.4 * Домашние работы (программная реализация алгоритма) + 0.6 * Устный экзамен
Bibliography
Recommended Core Bibliography
- 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
Recommended Additional Bibliography
- 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