Optimisation Combinatoire et Polyèdres

Objectifs : 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.

Contenu :

  • 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).