*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:

- Introduction to integer linear programs
- Methods
- Branch and bound methods.
- Dynamic programming.
- Cutting plane methods.

- Computational complexity:
- P, NP classes.
- Cook's Theorem.
- 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.