This information is indicative and can be subject to change. 
​
Advanced combinatorial optimization

Teacher:  Alexandre Skoda

E-mail:  askoda@univ-paris1.fr
ECTS: 2.5
Evaluation:   written exam
Previsional Place and time:  9  sessions (2h per session)

Prerequisites:  basic concepts in Graph theory (Path, trees, greedy algorithm), and in Linear programming (simplex method).
Aim of the course: Solving practical optimization problems often requires finding integer valued solutions. In the first part, we present modelizations requiring the introduction of integer variables. In particular, we will solve a problem on networks using a linear programming approach. In a second part we will review three general types of methods used to solve integer programs. Finally, we will end with an introduction to the analysis of algorithms.
 Syllabus: 

1. Introduction to integer linear programs
2. Methods
   1. Branch and bound methods.
   2.  Dynamic programming.
   3.  Cutting plane methods.
3. Computational complexity:
   1.  P, NP classes.
   2. Cook's Theorem.
   3. Examples of NP-complete problems.

 
References:

•  V. Chvatal, Linear Programming, Freeman, 1983.
• M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.
•  A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.