Méthodes de décomposition en programmation linéaire en nombre entiers

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

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.

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.