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
En bref
Crédits ECTS : Cf UE
Nombre d'heures 23
Contact(s)
Lieu(x)
- Toulouse