Description
Date depot: 1 janvier 1900
Titre: Algorithmes d'enumération implicite pour l'optimisation multi-objectifs exacte et approchee
Directeur de thèse:
Patrice PERNY (LIP6)
Directeur de thèse:
Olivier SPANJAARD (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
De nombreux problèmes de décision rencontrés en pratique en Intelligence Artificielle ou en Recherche Opérationnelle nécessitent la prise en compte de plusieurs critères conflictuels et hétérogènes. En particulier, il est fréquent de considérer simultanément des critères de nature quantitative (performance, durée, coût…), et même parfois de nature qualitative (aspects environnementaux par exemple). La prise en compte explicite de ces critères permet au décideur de mieux apprécier les différents arbitrages possibles et de progresser dans la définition d’une solution de meilleur compromis. Dans cette thèse, nous nous focaliserons sur les problèmes d’optimisation combinatoire multicritère, où la difficulté liée à la présence de plusieurs critères est combinée à la nature combinatoire de l’ensemble des solutions potentielles [1].
Deux problématiques peuvent être envisagées dans la résolution des problèmes d’optimisation combinatoire multicritère :
• P1 : trouver l’ensemble des solutions Pareto-optimales, i.e. qui ne peuvent être améliorées sur un critère sans être détériorées sur un autre [6];
• P2 : déterminer une solution de meilleure compromis parmi les solutions Pareto-optimales [2 ;3 ;4].
Les deux problématiques soulèvent des difficultés computationnelles intéressantes à étudier. Concernant P1, il est souvent assez difficile d’identifier l’ensemble des solutions Pareto-optimales, même pour des instances de taille moyenne. Ceci est dû principalement à deux raisons. D’une part, la taille de l’ensemble des solutions Pareto-optimales est souvent importante, et même exponentielle dans la taille de l’instance. D’autre part, pour la plupart des problèmes d’optimisation combinatoire multicritère, déterminer si une solution donnée est Pareto-optimale est un problème coNP-difficile, et ce même si la version monocritère du problème est résoluble en temps polynomial. Pour résoudre P2, deux types d’approches peuvent être développés. On peut soit sélectionner une solution de meilleure compromis après génération de l’ensemble des solutions Pareto-optimales, auquel cas on se retrouve confronté aux difficultés précédentes, soit focaliser directement la recherche sur une solution de meilleure compromis, auquel cas on est souvent ramené à un problème NP-difficile.
Doctorant.e: Delort Charles