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

Modern Methods of Decision Making

2021/2022
Учебный год
ENG
Обучение ведется на английском языке
8
Кредиты

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

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

Course Contents

  • Combinatorial optimization problems and greedy algorithms
    1. Polynomial (easy) and exponential (hard) scheduling problems and greedy algorithms 2.Hard graph problems
  • Simple and efficient heuristics: max-regret, greedy randomized and others
    1. Easy combinatorial problems on trees and greedy algorithms 2. Easy and hard problems from transportation logistics, constructive algorithms 3. Greedy randomized algorithms
  • Local search algorithms
    1.Local search, iterated local search, GRASP algorithms 2.Variable neighborhood search and large neighborhood search
  • Tabu search approach
    1. Tabu search approach 2. Tabu search for maximum clique problem
  • Branch-and-bound methods
    1. Constructive branch-and-bound algorithm 2. Branch-and-bound algorithm for maximum clique problem
  • Dynamic programming methods
    1. Introduction to dynamic programming 2. Well-known dynamic programming problems
Assessment Elements

Assessment Elements

  • non-blocking Programming Assignment after week 1
  • non-blocking Programming assignment after week 2
  • non-blocking Programming assingment after 4 week
  • non-blocking Final project
  • non-blocking Tests (after 3,5,6 weeks)
Interim Assessment

Interim Assessment

  • Interim assessment (3 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

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.