LEROY Cassandre
Supervision : Patrice PERNY
Co-supervision : LUST Thibault, BENABBOU Nawal
Incremental elicitation combined with heuristic search for multi-objective combinatorial optimization
This thesis is concerned with solving combinatorial domain decision problems using incremental regret-based preference elicitation methods for interactive optimization.
It is assumed that the decision maker's preferences can be represented by a parameterised scalarization function (weighted sum, OWA and Choquet integral), but the parameters (e.g., set of weights) are not known at the beginning. The active learning of the parameters is intertwined with the solution of the problem in order to learn only that part of the information about the parameter that is useful to solve the given problem. The originality of this work lies in the use of methods based on heuristic search coupled with incremental elicitation to determine the best solution for the decision maker.
At first we propose two methods for solving multi-objective combinatorial optimisation problems with imprecise preferences, the first based on local search and the second on a genetic algorithm.
We then propose two approaches to the elicitation of a linear, submodular and super-modular set function with the construction of an optimal independent subset subject to a matroid constraint. The first approach is based on a greedy algorithm and the other on the local search. In order to demonstrate the practical effectiveness of our approaches, our algorithms are numerically tested on different problems and evaluated in terms of computation time, number of queries and empirical error.
Defence : 12/05/2022 - 15h - Campus Pierre et Marie Curie, salle Jacques Pitrat (25-26/105)
Jury members :
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.
2019-2022 Publications
-
2022
- C. Leroy : “Élicitation incrémentale combinée à la recherche heuristique pour l’optimisation combinatoire multi-objectifs”, thesis, defence 12/05/2022, supervision Perny, Patrice, co-supervision : Lust, Thibault, Benabbou, Nawal (2022)
-
2021
- N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Interactive Optimization of Submodular Functions under Matroid Constraints”, ADT 2021 - 7th 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”, 22e 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 35th 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 24th 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”, 21e 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 34th 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 - 6th International Conference on Algorithmic Decision Theory, Durham, NC, United States (2019)