Description
Date depot: 1 janvier 1900
Titre: Recherche de solutions potentiellement optimales en décision multicritère, décision multi-agents et décision dans l'incertain.
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é:
La complexité croissante des applications réelles dans divers domaines (e.g. optimisation des réseaux de communication, problèmes de transport et de
localisation, planification des traitements thérapeutiques, allocation de ressources, élaboration de politiques publiques, commerce électornique sur le web) a conduit les chercheurs en aide à la décision à formuler des problèmes d'optimisation dans lesquels l’intérêt d’une solution doit être analysé selon plusieurs points de vues (critères, agents, scénarios).
Outre la difficulté d’explorer des espaces de solutions de grande taille, l’introduction explicite de plusieurs points de vue est une source supplémentaire de complexité. Dès lors que plusieurs critères, plusieurs agents ou plusieurs scénarios sont considérés dans l’évaluation d’une solution, la notion d’optimalité ne va pas de soi et divers modèles décisionnels sont proposés dans la littérature pour définir une préférence globale (en décison multicritère : critère de Tchebycheff, OWA, WOWA, intégrales de Choquet, dans l'incertain : modèles EU, RDU, CEU). Si ces modèles définissent implicitement les solutions optimales dans un problème combinatoire, ils ne donnent pas automatiquement les moyens de les calculer efficacement ou de les approcher. De plus ces modèles utilisent des paramètres préférentiels (poids, capacité, fonction d'utilité) qui ne sont pas toujours connus de manière précise et qui compliquent la détermination des meilleures solutions.
L’objet de cette thèse est de s’intéresser à la recherche des solutions potentiellement optimales (au sens de certains des modèles mentionnées plus haut) dans des problèmes d’optimisation combinatoire multicritères, multi-agents ou multi-scénarios, en présence de paramètres préférentiels imprécisément connus. Une solution est dite 'potentiellement optimale' si elle est optimale pour au moins une instance des paramètres préférentiels du modèle décisionnel considéré. On s'intéressera en particulier à l'exploitation de relations de dominances partielles (dominance Pareto, Lorenz, Dominance stochastique du premier et deuxième ordre, dominance en utilité) qui permettent d'approcher les modèles décisionnels plus discriminants et de calculer les vainqueurs potentiels au sens de ces modèles. On cherchera ensuite à exploiter ces dominances partielles au sein de processus d'élicitation interactifs pour les enrichir et se focaliser progressivement sur les toutes meilleures solutions. La classe de problèmes concernés inclus une large variété de problèmes d'optimisation concrets qui se formalisent comme des problèmes de graphes ou de programmation linéaire en nombres entiers, que leur version monocritère puisse être résolue en temps polynomial (plus courts chemins, arbres couvrants de poids minimum, affectation…) ou soit NP-difficile.
Doctorant.e: Benabbou Nawal