Master
2019/2020
Discrete optimization and operations research
Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'
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
Instructors:
Mikhail Vladimirovich Batsyn
Master’s programme:
Интеллектуальный анализ данных
Language:
English
ECTS credits:
6
Contact hours:
60
Course Syllabus
Abstract
В курсе рассматриваются современные точные методы решения задач комбинаторной оптимизации, включая методы ветвей и границ, ветвей и отсечений, ветвей и цен. Все алгоритмы разбираются на примере известных задач оптимизации, таких как задача о максимальной клике, задача коммивояжера, задач маршрутизации транспорта и т д.
Learning Objectives
- Целями освоения дисциплины является знакомство с современными классическими и прикладными задачами оптимизации, моделями математического программирования, точными алгоритмами ветвей и границ, ветвей и отсечений, ветвей и отсечений и цен и другими современными методами. Изучение данной дисциплины базируется на следующих дисциплинах: • Исследование операций • Разработка программного обеспечения Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: • Задачи математического программирования, алгоритмы решения классических задач исследования операций Основные положения дисциплины могут быть использованы при написании курсовой и дипломной работы.
Expected Learning Outcomes
- Студент строит линейную модель по описанию задачи и решает задачу
- Студент строит модель целочисленного программирования по описанию задачи, программирует алгоритм ветвей и границ для решения задачи и решает задачу с помощью написанной программы.
- Студент разрабатывает эвристику для решения задачи, программирует ее и решает задачу с помощью этой программы.
- Студент разрабатывает модель с большим (обычно экспоненциально большим) числом ограничений для задачи, программирует алгоритм ветвей и отсечений для решения задачи и решает задачу с помощью реализованной программы.
- Студент разрабатывает модель с большим (экспоненциально большим) числом переменных, программирует алгоритм ветвей и цен для решения задачи с такой моделью и решает задачу с помощью разработанной программы.
- По модели математического программирования для задачи студент получает оценку на целевую функцию с помощью Лагранжевой релаксации.
Course Contents
- Linear problemsLinear programming, graphical and algebraic simplex method, dual problem
- Integer problems. Branch-and-bound method.Branch-and-bound algorithm, branching strategies, bounds, initial solutions. Maximum clique, travelling salesman, vertex coloring and other problems
- Local searchLocal search heuristics, maximum independent set problem.
- Branch-and-cut approachVehicle routing problem, mathematical models, branch-and-cut methods, efficient families of constraints (cutting planes).
- Branch-and-price approach.Branch-and-price method, vertex coloring and vehicle routing models
- Lagrangian relaxationLagrangian relaxation approach for efficient bounds.
Interim Assessment
- Interim assessment (1 module)0.5 * Домашние работы (программная реализация алгоритма) + 0.5 * Устный экзамен
- Interim assessment (2 module)0.5 * Домашние работы (программная реализация алгоритма) + 0.5 * Устный экзамен
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