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

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.3 * Final Programming assignment + 0.3 * Programming assignment / week 1 + 0.2 * Programming assignment / week 2 + 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

Authors

  • BATSYN MIKHAIL VLADIMIROVICH