Modern operations research methods

2022/2023

Учебный год

ENG

Обучение ведется на английском языке

6

Кредиты

Кто читает:

Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс обязательный

Когда читается:

1-й курс, 3 модуль

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

Бацын Михаил Владимирович

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

Interim Assessment

• 2022/2023 3rd module
  1 * 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