Intervenants : Frédéric Giroire, Frédéric Havet et Nicolas Nisse

Dates : du 23 au 27 janvier 2012, à ENS Lyon, amphi B (sauf la séance de TP en E001)

Programme

Lundi
9h00 – 11h30
13h30 – 15h00
15h30 – 17h30
Introduction, Modelisation de problemes en PL, Simplexe approche geometrique.

Mardi
9h00 – 11h30 Dualité I
14h00 – 15h30 Dualité II
16h00 – 17h30 Ellipsoïde.

Mercredi
9h00 – 11h30 TP
13h30 – 15h00 Relaxation fractionnaire: Totale unimodularite.
15h30 – 17h30 Relaxation Lagrangienne.

Jeudi
9h – 11h30 Relaxation fractionnaire: Arrondis deterministes et aleatoires, integral gap.

Vendredi
9h – 11h30 Algorithmes primal-dual.
13h30 – 15h00 Examen.

Correspondant local : Nicolas Trotignon

Magnifiques notes de cours :
Introduction to linear programming duality
Ellipsoid method
Fractional relaxation
Lagrangian relaxation