Postgraduate course
2020/2021
Discrete Optimization
Type:
Elective course
Area of studies:
Informatics and Computer Engineering
Delivered by:
School of Data Analysis and Artificial Intelligence
Where:
Faculty of Computer Science
When:
2 year, 1 semester
Mode of studies:
offline
Instructors:
Laurent Beaudou
Language:
English
ECTS credits:
5
Contact hours:
38
Course Syllabus
Abstract
This course aims to present methods commonly used when it comes to optimize a function on some discrete space. After a brief introduction, we shall approach the Linear Programming as a all-around tool to model a wide set of problems. We also focus on Dynamic Programming as a technique for designing efficient algorithms. Integer Programming revolves around specific techniques when Linear Program require integrality of variables. Finally we'll consider some usual heuristics when nothing works.
Learning Objectives
- 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.
Expected Learning Outcomes
- 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.
Course Contents
- 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.
Assessment Elements
- ProjectA small project with a paper writing assignment and oral presentation.
- Exam
- ProjectA small project with a paper writing assignment and oral presentation.
- Exam
Bibliography
Recommended Core Bibliography
- Diestel R. Graph Theory. – Springer, 2017. – 428 pp.
Recommended Additional Bibliography
- 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