Programme de l’UE :
- Les bases. Programme linéaire.
Algorithme du Simplexe. Lemme de Farkas. Dualité. Ecarts complémentaires. Analyse de sensitivité. - Programmation en nombres entiers.
Polyèdres et Polytopes. Relaxation fractionnaire. Matrices totalement unimodulaires et TDI. Arrondis déterministes et aléatoires. Générations de coupes. - Modélisation et applications classiques.
Flots et réseaux de transport. Stratégies mixtes (jeux matriciels). Codes correcteurs. Compressed sensing. - Extensions possibles.
Ellipsoide. Oracles de coupe (Grotschel Lovasz Schrijver). Programmation semi-définie (Capacité Shannon, Fonction Theta, coupe minimum de Goemans et Williamson). Minimisation des fonctions sous-modulaires.
Intervenants
Cours: Stephan Thomassé
TDs: Guillaume Aupy