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.

Integer Linear Programming and Polytopes

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

Exercices: Some exercises

Practical session: solving MIP:
Practical Sessions
A first example in Julia
An example of a first MILP in Julia
An example for manipulating Graph in Julia
A MILP for the stable set problem
DIMACS examples

Practical session: Polyhedra with PORTA:
Practical Session about PORTA
Solutions

SDP and Column Generation

1 - Lecture on Semi-Definite and Conic Optimization

2 - Lecture on Column Generation and Branch-and-Price

Exercices: Some exercises

Practical session: solving SDP:
Practical Sessions
Instance for k-QKP
Instance generator

Reference books

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