• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Master 2021/2022

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 one campus
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

Learning Objectives

  • Целями освоения дисциплины является знакомство с современными классическими и прикладными задачами оптимизации, моделями математического программирования, точными алгоритмами ветвей и границ, ветвей и отсечений, ветвей и отсечений и цен и другими современными методами. Изучение данной дисциплины базируется на следующих дисциплинах: • Исследование операций • Разработка программного обеспечения Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: • Задачи математического программирования, алгоритмы решения классических задач исследования операций Основные положения дисциплины могут быть использованы при написании курсовой и дипломной работы.
Expected Learning Outcomes

Expected Learning Outcomes

  • По модели математического программирования для задачи студент получает оценку на целевую функцию с помощью Лагранжевой релаксации.
  • Студент разрабатывает модель с большим (обычно экспоненциально большим) числом ограничений для задачи, программирует алгоритм ветвей и отсечений для решения задачи и решает задачу с помощью реализованной программы.
  • Студент разрабатывает модель с большим (экспоненциально большим) числом переменных, программирует алгоритм ветвей и цен для решения задачи с такой моделью и решает задачу с помощью разработанной программы.
  • Студент разрабатывает эвристику для решения задачи, программирует ее и решает задачу с помощью этой программы.
  • Студент строит линейную модель по описанию задачи и решает задачу
  • Студент строит модель целочисленного программирования по описанию задачи, программирует алгоритм ветвей и границ для решения задачи и решает задачу с помощью написанной программы.
Course Contents

Course Contents

  • Linear problems
  • Integer problems. Branch-and-bound method.
  • Local search
  • Branch-and-cut approach
  • Branch-and-price approach.
  • Lagrangian relaxation
Assessment Elements

Assessment Elements

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

Interim Assessment

  • 2021/2022 1st module
    0.5 * Домашние работы (программная реализация алгоритма) + 0.5 * Устный экзамен
  • 2021/2022 2nd module
    0.5 * Домашние работы (программная реализация алгоритма) + 0.5 * Устный экзамен
Bibliography

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

Authors

  • BATSYN MIKHAIL VLADIMIROVICH