Optimisation Combinatoire et Polyèdres

Ects : 3

Description du contenu de l'enseignement :
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