• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Discrete optimization and operations research

2019/2020
Учебный год
ENG
Обучение ведется на английском языке
6
Кредиты

Преподаватель

Course Syllabus

Abstract

В курсе рассматриваются современные точные методы решения задач комбинаторной оптимизации, включая методы ветвей и границ, ветвей и отсечений, ветвей и цен. Все алгоритмы разбираются на примере известных задач оптимизации, таких как задача о максимальной клике, задача коммивояжера, задач маршрутизации транспорта и т д.
Learning Objectives

Learning Objectives

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

Expected Learning Outcomes

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

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

Assessment Elements

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

Interim Assessment

  • Interim assessment (1 module)
    0.5 * Домашние работы (программная реализация алгоритма) + 0.5 * Устный экзамен
  • Interim assessment (2 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