Modélisation de problèmes classiques. Méthodes d'énumération implicite (branch-and-bound) : arbre d'énumération, stratégie d'exploration, règles de branchement. Théorie polyédrale : inégalités valides, dimension, faces et facettes. Unimodularité. Méthodes de plans coupants. Coupes de Chvátal-Gomory et de Gomory. Algorithmes de séparation spécialisés. Décomposition de Dantzig-Wolfe et génération de colonnes. Relaxation lagrangienne. Décomposition de Benders. Étude détaillée des problèmes de sac à dos et du commis voyageur.
- Responsable du site: Guy Desaulniers
- Responsable du site: Andrea Lodi
- Responsable du site: Secmath MAGI
- Enseignant (éditeur) : Gabriele Dragotto