Une nouvelle borne pour les problèmes d’optimisation combinatoire robuste avec des coûts sous forme d’intervalles

Hugo Gilbert, Olivier Spanjaard
ROADEF 2016
Second price at the "prix jeunes chercheurs"

Abstract : Dans cette communication, nous nous intéressons au problèmes d'optimisation combinatoire robuste utilisant le critère minmax regret. Nous proposons une procédure de calcul d’une borne inférieure sur le regret de la solution optimale et nous montrons que la borne que nous proposons est toujours plus précise que celle proposé par Chassein et Goerigk. La validité de la borne inférieure proposée se fonde sur des arguments de théorie des jeux, et son calcul est réalisé à l’aide d’un algorithme de double oracle que nous spécifions. Cette borne inférieure est très générale et peut être calculée pour tout problème d’optimisation combinatoire robuste si une primitive résolvant le problème d’optimisation classique est connue. Nous détaillons ensuite comment implanter efficacement cette borne dans le cadre d’un algorithme de type branch and bound. Enfin nous appliquons notre méthode au problème de plus court chemin robuste. Nous montrons que notre approche permet des gains de temps de calcul significatifs.

PDF