Méthodes de décomposition en programmation linéaire en nombre entiers
Public Concerné
Bases de programmation mathématique (simplexe, dualité, Branch-and-Bound, etc.)
Objectifs pédagogiques
L'objectif du cours est d'introduire les méthodes de décomposition classiques qui permettent de résoudre des programmes linéaires en nombre entiers de grande taille. Les objectifs du cours sont (1) d'introduire les différentes méthodes de décomposition et algorithmes, (2) de présenter les outils théoriques permettant d'analyser et comparer les formulations obtenues en appliquant divers types de décomposition et (3) de former les élèves à l'utilisation pratique de ces méthodes sur des problèmes d'optimisation combinatoire. Une attention particulière sera apportée aux liens entres ces différentes méthodes et à leur analyse en utilisant des outils issus de la dualité. En fonction de l'aisance des étudiants, des ouvertures pourront se faire vers l'usage de ces méthodes en programmation non-linéaire.
Capacité et compétences acquises
Confronté à une formulation PLNE qu'un solveur ne sait pas résoudre de manière frontale, les élèves sauront identifier des méthodes de décomposition pertinentes, les analyser théoriquement pour identifier celles qui sont a priori les plus prometteuses, et les mettre en place. Les étudiants seront également capables d'utiliser les mécanismes de callback des solveurs.
Contenu de la formation
Chaque séance contiendra un TD réalisé pendant le cours, qui permettra d'illustrer les algorithmes étudiés sur des applications. Dans le cadre d'un TP à faire à la maison, les élèves devront implémenter les algorithmes sur un problème jouet utilisé en fil rouge[^1].
- Polyèdres et programmation linéaire. La séance est dédiée à l'étude des polyèdres en PL : définition, dimension, face, facette, arête et rayon. Cône de recession, Minkowski-Weyl. Séparation et lien entre séparation et optimisation. Génération de lignes.
- Polyèdres et programmation linéaire en nombres entiers. Branch and cut. Inégalités valides. Branch and cut. Théorème de Meyer.
- Décomposition de Benders. Rappels de dualité. Décomposition de Benders, algorithmes et applications.
- Décomposition de Dantzig Wolfe et génération de colonne. La séance rappellera la notion bonne formulation d'un PLNE. Elle introduira la décomposition et reformulation de Dantzig Wolfe, ainsi que l'algorithme de génération de colonnes. Des applications. Lien (dualité) avec la décomposition de Benders. Branch and price.
- Relaxation lagrangienne. La séance présentera la notion de relaxation Lagrangienne, son interprétation géométrique (théorème de Geoffrion) et l'algorithme de sous-gradient. Les avantages respectifs de la relaxation lagrangienne et de la décomposition de Dantzig Wolfe seront détaillés.
Description des modalités de validation
- Examen final
En alternance ou en formation continue en journée :
Merci de consulter directement le secrétariat pédagogique de votre formation pour obtenir le planning.
En formation « à la carte Hors Temps de Travail », en présentiel, à distance ou hybride :
Voir les dates, les lieux d'enseignement et les modalités d'inscription sur les sites internet des centres régionaux qui proposent cette formation.
