Современные методы принятия решений

Магистратура 2021/2022

Статус: Курс обязательный (Магистр по компьютерному зрению)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Кафедра прикладной математики и информатики (Нижний Новгород)

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

Когда читается: 1-й курс, 3 модуль

Формат изучения: с онлайн-курсом

Охват аудитории: для своего кампуса

Преподаватели: Бацын Михаил Владимирович

Прогр. обучения: Магистр по компьютерному зрению

Язык: английский

Кредиты: 8

Контактные часы: 2

Full 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 implement an efficient tabu search 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
to get acquainted with several examples of neighborhoods used for different optimization problems
to get acquainted with several examples of tabu search algorithms for a simple scheduling problem, maximum clique problem and min-k-tree problem
to get acquainted with tabu search approach allowing local search to go out of local optimums
to know basic parameters and features of branch-and-bound methods including branching strategy, bounds computation, initial heuristic solution
to know basic parameters of local search algorithms including initial solution construction, restart strategy, stopping criterion, first/best improvement strategies.
to know basic parameters of tabu search including tabu strategy, tabu list length, aspiration criterion
to understand the main feature which should be found for a problem to apply a dynamic programming approach: the problem should «repeat itself»

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 after week 1
Programming assignment after week 2
Programming assingment after 4 week
Final project
Tests (after 3,5,6 weeks)

Interim Assessment

2021/2022 3rd module
55% Programming assignments + 15% tests + 30% Final task (0.15*w1 + 0.15*w2 + 0.05*w3 + 0.25*w4 + 0.05*w5 + 0.05*w6 + 0.30*f )

Bibliography

Recommended Core Bibliography

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

Mauricio G.C. Resende, & Celso C. Ribeiro. (2016). Optimization by GRASP : Greedy Randomized Adaptive Search Procedures. Springer.

Course Syllabus