Ancrage et arbre couvrant

Il est fréquent que les données d’un problème soient susceptibles d’évoluer au cours du temps. Ainsi, un décideur peut être amené à calculer une solution initiale S d’un problème sur la base des données connues à l’instant présent, puis à devoir modifier S en une solution S’ en fonction de l’évolution de ces données. Les modifications pour passer de S à S’ génèrent généralement des coûts, potentiellement élevés. De plus, ce changement de solutions engendre de fortes difficultés en pratique : il est impossible de débuter la réalisation de tâches, de s’engager auprès de fournisseurs ou de clients, si les décisions peuvent être remises en cause. Dans la problématique de l’ancrage, on cherche à minimiser cette incertitude en garantissant qu’un certain ensemble de décisions prises initialement (dans la solution S) ne seront pas remises en cause par la suite et peuvent donc être considérées comme définitives.

Cette problématique de l’ancrage s’inscrit dans le domaine de l’optimisation robuste [2,3]; elle a été récemment étudiée sur un problème d’ordonnancement lié à la gestion de projets [1]. Le but de ce stage est d’étudier la question de l’ancrage dans un problème de type arbre couvrant. Dans le problème de l’arbre couvrant, nous avons en entrée un graphe G (non orienté) connexe dont les arêtes ont des poids positifs, et le but est de choisir un ensemble d’arêtes de G de poids total minimum permettant de conserver la connexité. C’est un problème bien connu, résoluble très efficacement par des algorithmes classiques (algorithmes de Kruskal et de Prim notamment), et ayant de nombreuses variantes et généralisations, comme le problème de l’arbre de Steiner.

L’étude réalisée dans ce stage consistera dans un premier temps à concevoir et définir un ensemble de modèles et de questions pertinents sur la problématique de l’ancrage pour des problèmes d’arbres couvrants – on peut en effet imaginer plusieurs manières de modéliser l’incertitude sur les données, plusieurs fonctions liés à l’objectif d’ancrage,... Il s’agira ensuite d’aborder la résolution de certaines de ces questions : complexité algorithmique, conception d’algorithmes exacts ou approchés,... Le stage pourra également comporter une partie expérimentale pour tester les algorithmes proposés.

[1] Pascale Bendotti, Philippe Chrétienne, Pierre Fouilhoux, Adèle Pass-Lanneau. The Anchor-Robust
Project Scheduling Problem. 2019. hal-02144834
[2] Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations Research, 52:35{53, 2004.
[3] Virginie Gabrel, Cecile Murat, and Aurelie C. Thiele. Recent advances in robust optimization: An overview. European Journal of Operational Research, 235:471{483, 2014.

Lieu: 
LIP6
Encadrant: 
Bruno Escoffier
Co-Encadrant: 
P. Chretienne,P. Bendotti
Référent Universitaire: 
n/a
Fichier Descriptif: 
Attribué: 
No
Année: 
2 021

User login