- To give students basic and advanced knowledge on methods used for solving discrete (combinatorial) optimization problems. The course provides both a theoretical understanding and a practical approach of these methods.
- Understanding of the purpose.
- Ability to model problem and interpret results.
- Ability to design adequate algorithms.
- Full understanding of algorithms and implications.
- Ability to model hard problems.
- Ability to approach problems out of reach by previous methods.
- Understanding the algorithms and its implications.
- Introduction to discrete optimizationExamples of problems, computational complexity, naive algorithms.
- Linear ProgrammingTheoretical approach, choosing appropriate model, what can be learned from LP.
- Dynamic ProgrammingRules of dynamic programming, examples.
- Milestone problem: max-flow/min-cutThorough study of max flow in graphs. Variations (flow of minimum cost). Unexpected use of this problem.
- Integer and Mixed Integer ProgrammingLinear relaxation, Lagrangian relaxation, Branch-and-Bound.
- HeuristicsLocal search, genetic algorithms, etc. Examples for famous problems.
- Milestone problem: Maximum matchingBlossom algorithm (J. Edmonds). Application.
- ProjectA small project with a paper writing assignment and oral presentation.
- Diestel R. Graph Theory. – Springer, 2017. – 428 pp.
- Cormen, T. H. (2009). Introduction to Algorithms (Vol. 3rd ed). Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=343613