• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Книга
Integral Robot Technologies and Speech Behavior

Kharlamov A. A., Pantiukhin D., Borisov V. et al.

Newcastle upon Tyne: Cambridge Scholars Publishing, 2024.

Статья
Clique detection with a given reliability

Semenov D., Koldanov A. P., Koldanov P. et al.

Annals of Mathematics and Artificial Intelligence. 2024.

Глава в книге
Neural Networks for Speech Synthesis of Voice Assistants and Singing Machines

Pantiukhin D.

In bk.: Integral Robot Technologies and Speech Behavior. Newcastle upon Tyne: Cambridge Scholars Publishing, 2024. Ch. 9. P. 281-296.

Препринт
DAREL: Data Reduction with Losses for Training Acceleration of Real and Hypercomplex Neural Networks

Demidovskij A., Трутнев А. И., Тугарев А. М. et al.

NeurIPS 2023 Workshop. ZmuLcqwzkl. OpenReview, 2023

Discrete optimization and operations research

2021/2022
Учебный год
ENG
Обучение ведется на английском языке
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

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