LEROY Cassandre

PhD student at Sorbonne University
Team : DECISION
https://lip6.fr/Cassandre.Leroy

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.


Phd defence : 12/05/2022

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.

Departure date : 09/30/2022

2019-2022 Publications