Optimisation en environnements incertains et dynamiques

Objectifs : L’objectif de ce cours est de présenter les problématiques liées à l’optimisation combinatoire dans le cadre d’instances évolutives. Pour les différents cas envisagés, nous présenterons des résultats en termes de complexité, d’algorithmique et d’approximation.

Contenu :

Les grandes problématiques présentées seront :

  • L’optimisation on-line dans laquelle l’instance se révèle petit à petit

  • L’optimisation probabiliste dans laquelle il existe une incertitude sur la présence des données

  • La réoptimisation dans laquelle il s’agit de tirer profit de la connaissance d’une solution optimale lorsque l’instance est très peu perturbée

Nous aborderons les problèmes classiques d’optimisation combinatoire tels que le stable, la coloration, l’arbre couvrant… dans chacun de ces cadres.

Bibliographie

  • C. Murat, V. Paschos, Probabilistic Combinatorial Optimization on Graphs, ISTE, United Kingdom, Hermes Science Publishing, 272 pages, mars 2006.

  • S. Albers, Online Algorithms: a survey, Mathematical Programming, 97(1), 3-26, 2003.