Description

This 4 hour lecture is an introduction to Combinatorial Optimization (CO) problems and their exact solving through mathematical progamming. These NP-hard problems are taken among classical CO problems (knapsack, stable set, TSP...).

In this lecture, we present several mathematical programming approaches to CO problems. These problems come either from the classical literature (stable set, max-cut, Travelling Salesman, graph coloring), or from ind ustrial applications (energy production, telecom, VLSI design...). The main topic is to show that several Mixed Integer Programs (MIP) can be written for the same problem, and that each of these MIPs can be solved by a dedicated algorithmic method (cutting plane or column generation approach). We will conclude by introducing the theoretical issues raised by these polyhedral and algorithmic approaches in the aim to make understant what is inside an integer solver.

Documents de cours et TD

Intro		0 - Introduction
Intro		1 - Linear Programming
Intro		2 - Non compact formation
Intro		3 - Introduction to polyhedral approach

TD: Some exercises

Reference books

• Combinatorial Optimization, W. Cook, W. Cunningham, W. Pulleyblank et A. Schrijver , Wiley-Interscience, 1997.
• Integer Programming, L. Wolsey, Wiley-Interscience, 1998.