Séminaire Virginie Gabrel et Cécile Mural

Jeudi 16 Janvier 2014 (Salle G001)

Cécile Murat et Virginie Gabrel, Lambsade, Paris Dauphine.

Titre : Plus courts chemins robustes.

Résumé : En optimisation, il est fréquent de faire face à des éléments d’incertitude et d’imprécision qui rendent difficile l’attribution d’une valeur unique plausible à chacun des paramètres du modèle.

Lorsqu’il n’est pas possible, ni pertinent, d’associer des lois de probabilités aux paramètres du modèle, il est alors préférable d’attribuer un ensemble de valeurs à chacun d’entre eux. La spécification d’une valeur pour chacun des paramètres correspond à un scénario. Dans ce cadre, le problème d’optimisation est résolu en déterminant une solution qui soit optimale sur tous les scénarios. En général, une telle solution n’existe pas et il s’agit de déterminer une solution qui se comporte relativement bien quel que soit le scénario qui puisse se réaliser, une telle solution étant qualifiée de robuste. La plupart des travaux portant sur la robustesse en optimisation combinatoire s’accorde à qualifier de robuste une solution qui soit acceptable dans une grande majorité des scénarios et, qui ne soit jamais trop mauvaise. Cette caractérisation laisse place à de nombreuses interprétations possibles et, a donc donné lieu à différentes approches de la robustesse. Ces approches diffèrent de par la modélisation des éléments d’incertitude et d’indétermination du problème de décision considéré, par la méthodologie utilisée pour appréhender la robustesse, et enfin par l’analyse et la conception de méthodes de résolution. Dans cette présentation, nous aborderons différents modèles appliqués au problème du plus court chemin..