Discrete Optimization

2020/2021

Academic Year

ENG

Instruction in English

5

ECTS credits

Delivered by:

School of Data Analysis and Artificial Intelligence

Type:

Elective course

When:

2 year, 1 semester

Instructor

Beaudou, Laurent

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 optimization
  Examples of problems, computational complexity, naive algorithms.
• Linear Programming
  Theoretical approach, choosing appropriate model, what can be learned from LP.
• Dynamic Programming
  Rules of dynamic programming, examples.
• Milestone problem: max-flow/min-cut
  Thorough study of max flow in graphs. Variations (flow of minimum cost). Unexpected use of this problem.
• Integer and Mixed Integer Programming
  Linear relaxation, Lagrangian relaxation, Branch-and-Bound.
• Heuristics
  Local search, genetic algorithms, etc. Examples for famous problems.
• Milestone problem: Maximum matching
  Blossom algorithm (J. Edmonds). Application.

Assessment Elements

• Project
  A small project with a paper writing assignment and oral presentation.
• Exam
• Project
  A small project with a paper writing assignment and oral presentation.
• Exam

Interim Assessment

• Interim assessment (1 semester)
  0.6 * Exam + 0.4 * Project

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