Combining Local Search and Elicitation for Multi-Objective Combinatorial Optimization - Sorbonne Université Access content directly
Conference Papers Year : 2019

Combining Local Search and Elicitation for Multi-Objective Combinatorial Optimization

Nawal Benabbou
Cassandre Leroy
  • Function : Author
Thibaut Lust
Patrice Perny


In this paper, we propose a general approach based on local search and incremental preference elicitation for solving multi-objective combinatorial optimization problems with imprecise preferences. We assume that the decision maker's preferences over solutions can be represented by a parameterized scalarizing function but the parameters are initially not known. In our approach, the parameter imprecision is progressively reduced by iteratively asking preference queries to the decision maker 1) before the local search in order to identify a promising starting solution and 2) during the local search but only when preference information are needed to discriminate between the solutions within a neighborhood. This new approach is general in the sense that it can be applied to any multi-objective combinatorial optimization problem provided that the scalarizing function is linear in its parameters (e.g., a weighted sum, an OWA aggregator, a Choquet integral) and that a (near-)optimal solution can be efficiently determined when preferences are precisely known. For the multi-objective traveling salesman problem, we provide numerical results obtained with different query generation strategies to show the practical efficiency of our approach in terms of number of queries, computation time and gap to optimality.
Fichier principal
Vignette du fichier
ADT.pdf (719.71 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-02170910 , version 1 (02-07-2019)


  • HAL Id : hal-02170910 , version 1


Nawal Benabbou, Cassandre Leroy, Thibaut Lust, Patrice Perny. Combining Local Search and Elicitation for Multi-Objective Combinatorial Optimization. ADT 2019 - 6th International Conference on Algorithmic Decision Theory, Oct 2019, Durham, NC, United States. ⟨hal-02170910⟩
158 View
219 Download


Gmail Mastodon Facebook X LinkedIn More