Ce projet de recherche doctorale est publié a été réalisé par Patrice Perny

Description d'un projet de recherche doctoral

Recherche de solutions potentiellement optimales en décision multicritère, décision multi-agents et décision dans l'incertain.

Mots clés :

Résumé du projet de recherche (Langue 1)

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.

Résumé du projet de recherche (Langue 2)

La manipulation de modèles décisionnels complexes sur des espaces de solutions implicites pose deux types de difficultés : d'une part les paramètres préférentiels qui permettent de contrôler le type de solution recherché sont souvent difficiles à éliciter de manière précise et l'on doit travailler avec un ensemble de jeux de paramètres possibles ce qui complique l'analyse. D'autre part même lorsque ces paramètres sont précisément définis, on ne dispose pas toujours d'algorithme efficace pour calculer les solutions optimales du fait du caractère complexe (non-linéaire, partiel) du modèle considéré. L'apport de ce sujet est de s'attaquer ici à ces deux difficultés envisagées conjointement de manière à produire des algorithmes capables de déterminer l'ensemble des solutions potentiellement optimales ou une couverture approchée de celui-ci avec garantie de performance. Ces travaux visent non-seulement à faciliter la production de recommandations pertinentes en aide à la décision mais peuvent également faciliter l'élicitation des préférences d'un agent dans des procédures de décision interactives (e.g. systèmes de recommandation sur le web).

Informations complémentaires (Langue 1)

Cette thèse relève de la théorie de la décision algorithmique, une thématique récente qui se développe rapidement en France et à l'étranger au carrefour de la théorie de la décision et de l'algorithmique discrète, notamment dans le cadre du Groupe de recherche (GDR) international ALGODEC (Algorithmic Decision Theory) soutenu par le CNRS et du groupe de travail Européen M-Pref sur la décision. Les travaux dans ce domaine concernent à la fois la communauté Recherche Opérationnelle et la communauté Intelligence Artificielle.