Delivered at:: Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:: Compulsory course

When:: 2 year, 2 module

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

weekly tests
Final test

Interim Assessment

2024/2025 2nd module
0.6 * Final test + 0.4 * weekly tests

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

CHURAEV EGOR NIKOLAEVICH
Savchenko Andrei Vladimirovich

Master’s Programme 'Artificial Intelligence and Computer Vision'

Email

Modern tools for solving computer vision problems

Course Syllabus