MA5051 - Optimisation combinatoire avancée

Objectifs

Objectif général :

Comprendre des méthodes avancées en optimisation discrète, savoir quand utiliser quelle méthode, savoir utiliser les méthodes (petits exercices d'implémentation)

Objectifs détaillés :

- Introduction aux techniques de décomposition- Dualité en programmation linéaire, lemme de Farkas, cônes.
Importance des variables duales. Théorème de la dualité.
- Décomposition de Benders. Génération de contraintes. Techniques d’accélération
- Décomposition de Dantzig-Wolfe. Lien avec la décomposition de Benders.
- Génération de colonnes
- Algorithmes de type Branch and Price
- Décomposition lagrangienne.

Place dans le cursus

Travaux pratiques sur ordinateurs. Langage python et API DOCPLEX pour le solveur CPLEX.
PRÉ-REQUIS
Programmation linéaire, programmation linéaire en nombres entiers, théorie des graphes, recherche arborescente

Examens

Nombre total d'heures d’évaluation : 3