Méthodes de décomposition en programmation linéaire en nombres entiers (DECO)

dernière modif : le 18/12/2023 à 16:43:53
Titre :
Méthodes de décomposition en programmation linéaire en nombres entiers (DECO)
Section :
Obligatoire
État pour cette année :
OPEN
Mots clés :
Génération de contraintes, Décomposition de Dantzig Wolfe, Décomposition de Benders, Relaxation Lagrangienne
Ects :
3
Responsable :
Axel Parmentier (ENPC/CERMICS)
Intervenants :
Axel Parmentier (ENPC/CERMICS)
Prérequis :

Bases de programmation mathématique (simplexe, dualité, Branch-and-Bound, etc.)

Objectif :

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.

Contenu / Plan :

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.

  • Correction du TP et examen.


[^1]: De récentes bibliothèques Julia qui permettent d'implémenter chacun de ces algorithmes en moins de 30 lignes de code sur des problèmes purs
Bibliographie :
  • Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer programming (Vol. 271, pp. 67-70). Berlin: Springer.

  • Conejo, A. J., Castillo, E., Minguez, R., & Garcia-Bertrand, R. (2006). Decomposition techniques in mathematical programming: engineering and science applications. Springer Science & Business Media.

Liens :
(aucun)
Compétences visées :

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.

Modalités de contrôle :
  • Un compte rendu de TP sur l'application des différentes méthodes à un problème concret
  • Un examen