Direction de recherche : Patrice PERNY
Co-encadrement : LUST Thibault, BENABBOU Nawal

Élicitation incrémentale combinée à la recherche heuristique pour l'optimisation combinatoire multi-objectifs

Cette thèse s'intéresse à la résolution de problèmes de décision sur domaine combinatoire par des méthodes d'élicitation incrémentale des préférences basée le regret pour l'optimisation interactive.

On suppose que les préférences du décideur peuvent être représentées par une fonction de scalarisation paramétrée (somme pondérée, OWA et intégrale de Choquet), mais que les paramètres (par exemple, le jeu de poids) ne sont pas connus au départ. L'apprentissage actif des paramètres est entremêlé à la résolution du problème dans le but d'apprendre seulement la part d'information sur ce paramètre qui est utile pour résoudre le problème donné. L'originalité de ces travaux réside dans la conception de méthodes fondées sur la recherche heuristique couplée à l'élicitation incrémentale pour déterminer la meilleure solution du décideur.

Nous proposons d'abord deux méthodes pour résoudre des problèmes d'optimisation combinatoire multiobjectifs avec des préférences imprécises, la première basée sur la recherche locale et la seconde sur un algorithme génétique.

Nous proposons ensuite deux approches permettant l'élicitation d'une fonction d'ensemble linéaire, sous-modulaire et super-modulaire avec la construction d'un sous-ensemble indépendant optimal soumis à une contrainte de matroïde. La première approche est basée sur un algorithme glouton et l'autre sur la recherche locale. Afin de démontrer l'efficacité pratique de nos approches, nos algorithmes sont testés numériquement sur différents problèmes et évalués en termes de temps de calcul, de nombre de requêtes et d'erreur empirique.

Soutenance : 05/12/2022

Membres du jury :

Matthieu BASSEUR, Professeur, Université du Littoral Côte d'Opale, Laboratoire d'informatique, signal et image de la Côte d'Opale. [Rapporteur]
Laëtitia JOURDAN, Professeure, Université de Lille, Centre de Recherche en Informatique, Signal et Automatique de Lille. [Rapporteur]
Daniel VANDERPOOTEN, Professeur, Université Paris Dauphine, Laboratoire d'Analyse et Modélisation de Systèmes pour l'Aide à la Décision.
Nawal BENABBOU, Maîtresse de conférence, Sorbonne Université, Laboratoire LIP6.
Thibaut LUST, Maître de conférence, Sorbonne Université, Laboratoire LIP6.
Patrice PERNY, Professeur, Sorbonne Université, Laboratoire LIP6.

Publications 2019-2022

• 2022
  • C. Leroy : “Élicitation incrémentale combinée à la recherche heuristique pour l’optimisation combinatoire multi-objectifs”, soutenance de thèse, soutenance 05/12/2022, direction de recherche Perny, Patrice, co-encadrement : Lust, Thibault, Benabbou, Nawal (2022)
• 2021
  • N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Interactive Optimization of Submodular Functions under Matroid Constraints”, ADT 2021 - 7^th International Conference on Algorithmic Decision Theory, vol. 13023, Lecture Notes in Computer Science book series, Toulouse, France, pp. 307-322, (Springer-Verlag), (ISBN: 978-3-030-87755-2) (2021)
  • N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Élicitation Incrémentale combinée à la Recherche Locale et Recherche Gloutonne pour l’Optimisation de Matroïdes Pondérés”, 22^e congrès annuel de la société française de recherche opérationnelle et d'aide à la décision, Mulhouse (en ligne), France (2021)
  • N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization”, Proceedings of the 35^th AAAI Conference on Artificial Intelligence (AAAI'21), Virtual, France (2021)
• 2020
  • N. Benabbou, C. Leroy, Th. Lust : “Regret-Based Elicitation for Solving Multi-Objective Knapsack Problems with Rank-Dependent Aggregators”, The 24^th European Conference on Artificial Intelligence (ECAI'20), Saint Jacques de Compostelle, Spain (2020)
  • N. Benabbou, C. Leroy, Th. Lust : “Élicitation Incrémentale combinée à la Recherche Heuristique pour l’Optimisation Combinatoire Multi-objectifs”, 21^e congrès annuel de la société française de recherche opérationnelle et d'aide à la décision, Montpellier, France (2020)
  • N. Benabbou, C. Leroy, Th. Lust : “An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems”, Proceedings of the 34^th AAAI Conference on Artificial Intelligence (AAAI'20), New York, United States (2020)
• 2019
  • N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Combining Local Search and Elicitation for Multi-Objective Combinatorial Optimization”, ADT 2019 - 6^th International Conference on Algorithmic Decision Theory, Durham, NC, United States (2019)