Portail nationalFormations hybrides

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

Code UE : US333B

  • Cours
  • 3 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Public, conditions d’accès et 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 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.

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é d'évaluation

  • Examen final

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Package
Lieu(x) Paris
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé