Description

This 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 industrial 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

Intro		Presentation of the module and schedule
Intro		0 - Introduction
Intro		1 - Linear Programming
Intro		2 - Polynomial Cases
Intro		3 - Non compact formation
Intro		4 - Introduction to polyhedral approach

Exercices: Some exercises

Practice:
Practical Sessions
A first example in Julia
An example of a first MILP in Julia

Reference books

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