Master 2020/2021

Discrete optimization and operations research

Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'

Category 'Best Course for New Knowledge and Skills'

Type: Compulsory course (Data Mining)

Area of studies: Applied Mathematics and Informatics

Delivered by: Department of Applied Mathematics and Informatics

Where: Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod)

When: 1 year, 1, 2 module

Mode of studies: offline

Open to: students of all HSE University campuses

Instructors: Mikhail Vladimirovich Batsyn

Master’s programme: Интеллектуальный анализ данных

Language: English

ECTS credits: 6

Contact hours: 60

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
  Linear 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 search
  Local search heuristics, maximum independent set problem.
• Branch-and-cut approach
  Vehicle 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 relaxation
  Lagrangian relaxation approach for efficient bounds.

Assessment Elements

• Домашние работы (программная реализация алгоритма)
• Устный экзамен
• Устный экзамен
• Домашние работы (программная реализация алгоритма)
• Устный экзамен
• Устный экзамен

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