Master
2022/2023
Modern operations research methods
Type:
Compulsory course (Master of Computer Vision)
Area of studies:
Applied Mathematics and Informatics
Delivered by:
Department of Applied Mathematics and Informatics
When:
1 year, 3 module
Mode of studies:
distance learning
Online hours:
90
Open to:
students of one campus
Instructors:
Mikhail Vladimirovich Batsyn
Master’s programme:
Master of Computer Vision
Language:
English
ECTS credits:
6
Contact hours:
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
- 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
- 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
- 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
- Programming assignment / week 1
- Programming assignment / week 2
- Programming assignment / week 3
- Final Programming assignment
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