• 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

Modern operations research methods

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

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

Course Syllabus

Abstract

The course is devoted to heuristic and exact algorithms for combinatorial optimization problems. The prerequisites for this course are graph theory; basic data structures (vector, list, tree, heap, stack, queue etc), algorithms (DFS, BFS, binary search, sort etc) and their complexity; experience in C++ programming.
Learning Objectives

Learning Objectives

  • To get acquainted with efficient algorithms, which can be applied to solve a large class of problems coming from real life – combinatorial optimization problems
  • To get programming experience and understanding of many well-known problems and algorithms to solve them
  • To be able to suggest a couple of heuristic algorithms and an exact algorithm for almost every real-life problem related to discrete optimization.
Expected Learning Outcomes

Expected Learning Outcomes

  • to be able to implement a branch-and-bound algorithm in C++ program
  • to be able to implement a greedy algorithm in C++ program
  • to be able to implement an efficient constructive algorithm in C++ program
  • to be able to suggest a constructive branch-and-bound algorithm for an arbitrary combinatorial optimization problem
  • to be able to suggest a dynamic programming algorithm for an optimization problem which can be expressed via the same problem, but having a smaller size
  • to be able to suggest a greedy algorithm for an arbitrary combinatorial optimization problem
  • to be able to suggest an efficient constructive algorithm for an arbitrary combinatorial optimization problem
  • to be able to suggest an efficient local search algorithm for an arbitrary combinatorial optimization problem
  • to be able to suggest an efficient tabu search algorithm for an arbitrary combinatorial optimization problem
  • to get acquainted with branch-and-bound methods applied to find an exact globally optimal solution for a combinatorial optimization problem
  • to get acquainted with different combinatorial optimization problems
  • to get acquainted with different local search algorithms including ILS (Iterated Local Search, GRASP (Greedy Randomized Adaptive Search Procedure), VNS (Variable Neighborhood Search), LNS (Large Neighborhood Search)
  • to get acquainted with dynamic programming methods applied to find an exact globally optimal solution for polynomial and pseudo-polynomial problems including the shortest path, the longest common subsequence, the pattern matching, the knapsack, the partition problems
  • to get acquainted with examples of branch-and-bound algorithms for the travelling salesman problem and maximum clique problem
  • to get acquainted with several examples of greedy approaches
  • to get acquainted with several examples of max-regret, greedy randomized and other constructive approaches
Course Contents

Course Contents

  • Combinatorial optimization problems and greedy algorithms
  • Simple and efficient heuristics: max-regret, greedy randomized and others
  • Local search algorithms
  • Tabu search approach
  • Branch-and-bound methods
  • Dynamic programming methods
Assessment Elements

Assessment Elements

  • non-blocking Programming assignment / week 1
  • non-blocking Programming assignment / week 2
  • non-blocking Programming assignment / week 3
  • non-blocking Final Programming assignment
Interim Assessment

Interim Assessment

  • 2023/2024 3rd module
    0.2 * Programming assignment / week 2 + 0.3 * Final Programming assignment + 0.3 * Programming assignment / week 1 + 0.2 * Programming assignment / week 3
Bibliography

Bibliography

Recommended Core Bibliography

  • Combinatorial optimization and applications, 3rd International Conference, COCOA 2009 Huangsham, China, June 10-12, 2009 : Proceedings, eds. Ding-Zhu, Xiaodong Hu, Panos M. Pardalos, 542 p., , 2009
  • Mauricio G.C. Resende, & Celso C. Ribeiro. (2016). Optimization by GRASP : Greedy Randomized Adaptive Search Procedures. Springer.
  • Michael L. Pinedo. (2016). Scheduling : Theory, Algorithms, and Systems: Vol. Fifth edition. Springer.
  • Potvin, J.-Y., & Gendreau, M. (2010). Handbook of Metaheuristics (Vol. 2nd ed). New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=373689

Recommended Additional Bibliography

  • Data Correcting Approaches in Combinatorial Optimization, 114 p., Goldengorin, B., Pardalos, P. M., 2012