Algorithmes pour l'optimisation temporelle

Il est fréquent dans un contexte applicatif que les données d’un problème soient susceptibles d’évoluer au cours du temps. L'objectif est alors généralement de maintenir une solution réalisable au cours de ce processus dynamique, tout en essayant de combiner deux objectifs potentiellement contradictoires:
- avoir à chaque instant une bonne solution sur l'instance courante
- garder une certaine stabilité, en minimisant les coûts de transition pour passer d'une solution à une autre.

Trouver une solution optimisant la somme des deux objectifs précédents est un problème généralement difficile, et l'on s'intéresse alors à la conception d'heuristiques trouvant de bonnes solutions. Quelques premiers travaux ont été réalisées en ce sens sur cette thématique émergente.

Ce projet se focalise sur un problème d'optimisation particulier (le couplage) dans ce contecte d'optimisation temporelle. Il s'agira:
- d'implanter des algorithmes simples permettant d'obtenir des solutions approchées;
- de réaliser des tests pour mesurer la qualité de ces algorithmes; pour cela il faudra s'intéresser à la génération d'instances, et potentiellement à l'implantation d'un algorithme exact;
- de réaliser une interface permettant de définir des instances et de visualiser les solutions;
- potentiellement de concevoir (avec les encadrants) et implanter des heuristiques pour améliorer les approches précédentes.