Description
Date depot: 1 janvier 1900
Titre: Algorithmes interactifs pour l'optimisation combinatoire avec des préférences partiellement connues
Directeur de thèse:
Olivier SPANJAARD (LIP6)
Directeur de thèse:
Patrice PERNY (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Dans la plupart des problèmes d'optimisation combinatoire, les préférences entre solutions réalisables sont supposées connues de manière précise (typiquement, la fonction objectif est linéaire et ses coefficients sont supposés parfaitement connus). Néanmoins, dans de nombreux cas, cette hypothèse s'avère forte : les paramètres préférentiels peuvent présenter un caractère subjectif (par exemple, dans un problème d'affectation d'articles à des relecteurs dans le cadre d'une conférence, où les paramètres préférentiels sont les scores que les relecteurs attribuent aux différents papiers soumis), être soumis à l'incertitude (par exemple, dans un problème d'itinéraire routier, où les temps de parcours dépendent de l'état du trafic), ou encore être difficile à recueillir (par exemple, dans un problème d'optimisation multi-objectifs, où les paramètres de la fonction d'agrégation des objectifs requiert une procédure d'élicitation préalable, qui peut être fastidieuse). C'est d'autant plus dommageable qu'il est bien connu que le choix de la solution optimale peut être très sensible aux données numériques précises employées pour l'optimisation. Ces observations ont conduits au développement de différentes approches d'optimisation avec des préférences partiellement connues, parmi lesquelles :
-* Optimisation robuste [2, 8] . On considère un ensemble de scénarios possibles pour les paramètres préférentiels, et on cherche une solution qui reste satisfaisante quel que soit le scénario qui finalement se réalise. Selon le modèle de robustesse utilisé, un problème dont la version standard est de complexité polynomiale peut rester polynomial ou au contraire devenir NP-difficile.
-* Optimisation ordinale [4, 9]. Il s'agit de développer des algorithmes qui ne s'appuie que sur une information de nature ordinale sur les paramètres, comme par exemple un problème de sac à dos où l'on ne dispose que d'une relation d'ordre sur les objets. On peut alors s'intéresser à des modèles de préférence où l'on étend l'ordre sur les objets en un ordre total sur les solutions, ou à des modèles où l'on vise à déterminer un ensemble de solutions préférées (ordre partiel sur les solutions).
-* Optimisation avec des préférences partiellement spécifiées [7, 10]. Cette approche consiste à définir une relation de dominance entre solutions fondée sur l'information partielle dont l'on dispose sur les préférences (par exemple, dans un problème multi-objectifs, on peut disposer d'un jeu de paramètres possibles pour la fonction d'agrégation des objectifs), et à déterminer l'ensemble des solutions non-dominées pour cette relation.
-* Optimisation avec élicitation incrémentale des préférences [5, 6]. Cette dernière approche mêle optimisation et élicitation des préférences, en posant des questions au décideur au fur et à mesure de la résolution du problème considéré afin de raffiner suffisamment l'information préférentielle pour permettre d'identifier une solution proche d'être optimale (avec garantie sur la qualité de la solution retournée).
Les travaux que nous envisageons dans cette thèse relèvent principalement de cette dernière approche, avec comme objectifs de concevoir des algorithmes interagissant avec le décideur afin de converger le plus rapidement possible vers une solution préférée.
Doctorant.e: Bourdache Nadjet