• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Postgraduate course 2019/2020

Discrete Optimization

Type: Elective course
Area of studies:  Informatics and Computer Engineering
When: 2 year, 1 semester
Mode of studies: Full time
Instructors: Laurent Beaudou
Language: English
ECTS credits: 4

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

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

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

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

Assessment Elements

  • non-blocking Project
    A small project with a paper writing assignment and oral presentation.
  • non-blocking Exam
Interim Assessment

Interim Assessment

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

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