Description
Date depot: 12 avril 2023
Titre: Algorithmes approchés avec garanties de performance pour la décision sur domaine combinatoire
Directeur de thèse:
Patrice PERNY (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Aide à la décision et recherche opérationnelle
Resumé: La thèse relève de la théorie de la décision algorithmique et porte sur la conception d'algorithmes approchés avec garanties de performance pour la prise de décision en environnement complexe. Par complexe on entend ici d'une part le fait que l'espace des solutions admissibles est défini de manière implicite (par un système de contraintes ou un ensemble de propriétés structurelles à satisfaire) et inclut possiblement un grand nombre d'éléments du fait de sa structure combinatoire, et d'autre part que le modèle de décision qui définit la notion de préférence et d'optimalité est une fonction généralement non-linéaire des variables de décision pour pouvoir rendre compte de préférences sophistiquées. Cette problématique apparait dans de nombreux contextes décisionnels, que ce soit en décision multicritère et collective ou en décision dans l'incertain et dans le risque.
Un premier objectif sera d'étudier l'apport potentiel de méthodes d'optimisation approchées avec garanties de performance pour différentes classes de modèles décisionnels, en particulier dans la famille des critères d'agrégation dépendants du rang (OWA, Gini, RDU, intégrale de Choquet) afin de pouvoir calculer efficacement des solutions presque optimales sur de grandes instances de problèmes combinatoires ou d’étudier le caractère approximable des problèmes posés. On pourra aussi envisager des approches exploitant la complexité paramétrique et des approches visant l’approximation efficace. Un deuxième objectif sera éventuellement de coupler de telles méthodes d'optimisation avec des techniques d'élicitation de préférences pour apprendre le modèle de décision en cours d'optimisation.
Résumé dans une autre langue: The thesis topic lies in algorithmic decision theory and focuses on the design of approximate algorithms with performance guarantees for decision making in a complex environment. By complex we mean here on the one hand the fact that the admissible space of solutions is defined implicitly (by a system of constraints or a set of structural properties to be satisfied) and possibly includes a large number of elements due to its combinatorial structure, and on the other hand that the decision model which defines the notion of preference and optimality is a generally non-linear function of the decision variables to account for sophisticated preferences. This problem appears in many decision-making contexts, whether in multi-criteria and collective decision-making or in decision-making under uncertainty and risk. A first objective will be to study the potential contribution of approximate optimization methods with performance guarantees for different classes of decision models, in particular in the family of rank-dependent aggregation criteria (OWA, Gini, RDU, Choquet integral) in order to be able to efficiently compute nearly optimal solutions on large instances of combinatorial problems or to study the approximability of the problems posed. Other approaches exploiting parametric complexity and approaches aiming at efficient approximation could also be considered. A second objective will possibly be to couple such optimization methods with preference elicitation techniques to learn the decision model during the optimization process.