Optimisation en environnements incertains et dynamiques

Crédit : 3 ECTS
Langue du cours : anglais

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



Année universitaire 2019 - 2020 - Fiche modifiée le : 04-06-2019 (10H57) - Sous réserve de modification.