Author name cluster

Thibaut Lust

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

ECAI Conference 2024 Conference Paper

Generating Fair Solutions of Minimal Cost

Mohammed Bachir Bederina
Djamal Chaabane
Thibaut Lust

In this work, we consider combinatorial multi-agent optimization problems, i. e. , problems presenting a combinatorial set of solutions, and each solution is evaluated through a vector. An element of the vector corresponds to the utility that an individual agent receives from the solution. Given potential conflicts, it is improbable that a single feasible solution will be optimal for all agents. Consequently, a relevant objective is to identify solutions that are fair to all agents. There are several approaches to defining fairness in the context of optimization problems, and here we focus on Lorenz-optimal solutions. However, in some cases, in addition to the search for a fair solution, an economic criterion comes into play, i. e. , we also seek to find a least-cost solution. Since the optimal solution for the cost function is not necessarily fair (i. e. , Lorenz-optimal in our case), our aim is to generate a Lorenz-optimal solution with minimum cost. We propose a new exact method to solve this problem, and apply it to the multi-agent assignment problem and to the multi-agent knapsack problem. Results show that the new method is much more efficient than a method based on a complete enumeration of Lorenz-optimal solutions.

Details

AAAI Conference 2021 Conference Paper

Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization

Nawal Benabbou
Cassandre Leroy
Thibaut Lust
Patrice Perny

We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or nearoptimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.

PDF Details

AAAI Conference 2020 Conference Paper

An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems

Nawal Benabbou
Cassandre Leroy
Thibaut Lust

We propose a new approach consisting in combining genetic algorithms and regret-based incremental preference elicitation for solving multi-objective combinatorial optimization problems with unknown preferences. For the purpose of elicitation, we assume that the decision maker’s preferences can be represented by a parameterized scalarizing function but the parameters are initially not known. Instead, the parameter imprecision is progressively reduced by asking preference queries to the decision maker during the search to help identify the best solutions within a population. Our algorithm, called RIGA, can be applied to any multi-objective combinatorial optimization problem provided that the scalarizing function is linear in its parameters and that a (near-)optimal solution can be efﬁciently determined when preferences are known. Moreover, RIGA runs in polynomial time while asking no more than a polynomial number of queries. For the multi-objective traveling salesman problem, we provide numerical results showing its practical efﬁciency in terms of number of queries, computation time and gap to optimality.

PDF Details

ECAI Conference 2020 Conference Paper

Regret-Based Elicitation for Solving Multi-Objective Knapsack Problems with Rank-Dependent Aggregators

Nawal Benabbou
Cassandre Leroy
Thibaut Lust

In this paper, we consider multi-objective knapsack problems where the decision maker’s preferences are represented by a non-linear aggregation function whose parameters are initially not known. More precisely, we focus on rank-dependent aggregators such as ordered weighted averages (OWA) and Choquet integrals which are non-linear scalarizing functions that assign weights to ranks rather than to objectives in the aggregation process, so as to control the importance attached to the bottom performance or to any other order statistics; for instance, an OWA operator with decreasing weights helps promoting balanced solutions while ensuring overall efficiency. In this setting, we propose new interactive heuristic methods consisting in combining regret-based preference elicitation and heuristic search so as to quickly focus the search on the most promising solutions. For OWA operators and Choquet integrals, the proposed methods run in polynomial time and are guaranteed to generate no more than a polynomial number of queries. We perform numerical tests comparing our methods to different interactive solving methods in order to show the practical efficiency of our approach in terms of number of queries, computation time and gap to optimality.

Details

SoCS Conference 2019 Conference Paper

A General Interactive Approach for Solving Multi-Objective Combinatorial Optimization Problems with Imprecise Preferences

Nawal Benabbou
Thibaut Lust

In this paper, we develop a general interactive method to solve multi-objective combinatorial optimization problems with imprecise preferences. Assuming that preferences can be represented by a parameterized scalarizing function, we iteratively ask preferences queries to the decision maker in order to reduce the uncertainty over the preference parameters until being able to determine her preferred solution. To produce informative preference queries at each step, we generate promising solutions using the extreme points of the polyhedron representing the admissible preference parameters and then we ask the decision maker to compare two of these solutions (we propose different selection strategies). These extreme points are also used to provide a stopping criterion guaranteeing that the returned solution is optimal (or near-optimal) according to the decision maker

Details