Programme de l’UE :

  1. Les bases. Programme linéaire.
    Algorithme du Simplexe. Lemme de Farkas. Dualité. Ecarts complémentaires. Analyse de sensitivité.
  2. 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.
  3. Modélisation et applications classiques.
    Flots et réseaux de transport. Stratégies mixtes (jeux matriciels). Codes correcteurs. Compressed sensing.
  4. 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