US333B

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


3 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2024 au 31-08-9999

Prérequis

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.

Compétences

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

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.

Modalités de validation

  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
Recherche opérationnelle
Nom du contact
Adresses email
secretariat.ro@cnam.fr
Numéros de téléphone
01 40 27 22 67
Adresse postale
2D4P20, 33-1-10, 2 rue Conté
Paris 75003