Il est fréquent dans un contexte applicatif que les données d’un problème soient susceptibles d’évoluer au cours du temps. Pour faire face à ce type de situations, des algorithmes permettant de résoudre dynamiquement un problème d’optimisation (c’est-à-dire de maintenir une solution optimale au cours d’un processus où l’instance du problème évolue) ont été conçus, par exemple pour le problème du plus court chemin ou celui de l’arbre couvrant de poids minimum. Lorsque l’on considère un problème NP-difficile, la situation est bien évidemment plus délicate et l’on ne peut imaginer résoudre efficacement dynamiquement le problème. Dans ce cadre, la réoptimisation s’intéresse à un cas particulier intéressant, celui où une instance déjà résolue subit de légères modifications ; il s’agit alors de savoir dans quelle mesure on peut résoudre cette instance modifiée.
Dans le cadre de conception d’un algorithme dynamique, trois aspects majeurs doivent être pris en compte :
- l’efficacité de l’algorithme (complexité algorithmique)
- la qualité des solutions proposées
- la stabilité des solutions, dans le sens où, lorsque l’instance évolue, la modification d’une solution S en une solution S’ induit des coûts de transition. Il s’agit donc de trouver une solution S’ induisant peu de changement par rapport à S.
Ces aspects étant potentiellement contradictoires, il est intéressant de trouver des solutions algorithmiques présentant de bons compromis sur ces trois critères.
Ce stage consiste à étudier cette question en réalisant:
- une étude de la littérature pour mettre en perspective les différentes approches, et une réflexion sur les cadres de travail et questions qui semblent les plus pertinentes ;
- une étude sur un problème d’optimisation classique : cette étude pourra revêtir à la fois un aspect analytique (calcul de garantie de performance d’algorithmes notamment) et expérimental.
On pourra se focaliser tout d’abord sur le cadre de la réoptimisation, et éventuellement aborder ensuite un aspect dynamique plus global.
Stage rémunéré (selon la gratification en vigueur, soit environ 500 euros par mois). Durée 5 ou 6 mois.