Description
Date depot: 1 janvier 1900
Titre: Algorithmes avec garantie de performance pour l'optimisation combinatoire multi-criteres/multi-agents
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, élaboration de politiques publiques, recherche sur le web) a conduit les chercheurs opérationnels et les chercheurs en aide à la décision à formuler des problèmes dans lesquels l’intérêt d’une solution doit être analysé selon plusieurs critères. Outre la difficulté d’explorer des espaces de solutions de grande taille, l’introduction explicite de plusieurs critères conflictuels est une source supplémentaire de complexité, offrant de nouveaux challenges algorithmiques aux informaticiens.
Dès lors que plusieurs critères sont considérés dans l’évaluation d’une solution, la notion d’optimalité ne va pas de soi et diverses définitions alternatives sont proposées dans la littérature sur la théorie de la décision et l’analyse multicritère. Parmi elles, la notion d’optimalité de Pareto ou efficacité est la plus largement utilisée. Une solution est dite Pareto-optimale ou efficace si on ne peut l’améliorer sur un critère sans la détériorer sur un autre. Dans les problèmes d’optimisation combinatoire, l’énumération complète des solutions Pareto-optimales est intraitable puisque, dans le pire des cas, la taille de l’ensemble de ces solutions croît exponentiellement avec la taille de l’instance. Ainsi, calculer l’ensemble des solutions Pareto-optimales induit des temps de réponses prohibitifs et nécessite un espace mémoire très important. Pour cette raison, dans de nombreuses applications les personnes confrontées à de telles difficultés ont recours a des simplifications artificielles du problème, soit en se focalisant sur le critère le plus important (comme dans les systèmes d’aide à la planification d’itinéraires), soit en agrégeant a priori les critères par une combinaison linéaire pour obtenir une version monocritère du problème à résoudre, soit encore en utilisant une heuristique pour engendrer des échantillons de bonnes solutions, ce qui dans tous les cas ne produit aucune garantie sur la qualité des solutions obtenues.
Face à ce constat, l’objet de cette thèse est de développer de nouvelles approches opérationnelles pour résoudre les problèmes combinatoires multicritères en fournissant des garanties sur la qualité des solutions. En particulier, on s’intéressera à développer des algorithmes efficaces permettant d’approximer la frontière de Pareto, avec garantie de performance, tout en conservant une bonne représentation de la diversité des compromis possibles. La classe de problèmes concernés inclus une large variété de problèmes multicritères concrets qui se formalisent comme des problèmes de graphes ou de programmation linéaire en nombre entier, 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 (sac-à-dos, voyageur de commerce,….). Nous nous intéresserons à la détermination de l’ensemble des solutions Pareto optimales et à la détermination d’un compromis spécifique dans cet ensemble. Par ailleurs, lorsque les critères représentent les utilités d'agents dans des problèmes de décision collective sur des domaines combinatoires, on peut craindre d'éventuelles manipulations stratégiques des agents qui consisteraient à communiquer de fausses utilités pour que la procédure de décision multicritère conduise à une solution qui leur soit plus favorable. On peut donc s'intéresser à développer des mécanismes à véracité garantie pour les procédures de décisions exactes ou approchées évoquées plus haut. On peut aussi s'intéresser à la recherche ou l'approximation d'équilibres entre les agents.
Doctorant.e: Ismaili Anisse