Optimisation Combinatoire et Polyèdres

Crédit : 3 ECTS
Langue du cours : anglais

Plusieurs problèmes concrets issus de domaines divers peuvent être formulés comme des problèmes d’optimisation combinatoire. La résolution de ces problèmes se ramène à l’optimisation d’une fonction objectif sur un polyèdre. Ce cours est une introduction à l’analyse polyédrale pour les problèmes d’optimisation combinatoire. On introduit les principaux éléments nécessaires pour une telle analyse et étudie les conséquences algorithmiques pour la résolution des problèmes sous-jacents. Certaines applications seront présentées pour illustrer ces approches.
Optimisation combinatoire et polyèdres
Dimension, faces et facettes de polyèdres
Description minimale d’un polyèdre par un système d’inégalités linéaires
Approche polyédrale
Polyèdres combinatoires et relations min-max
Applications

Bibliographie
W. Cook, W. Cunningham, W.R. Pulleyblank, A. Schrijver, "Combinatorial Optimization", Wiley (1998).
A. R. Mahjoub, "Approches polyédrales", dans "Optimisation Combinatoire 1: Concepts fondamentaux", V. Paschos (Ed.), Hermes (2005) pp. 263-329.
G. L. Nemhauser and L. A. Wolsey, "Integer and Combinatorial Optimization", Wiley (1988)



Année universitaire 2019 - 2020 - Fiche modifiée le : 08-07-2019 (12H07) - Sous réserve de modification.