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's preferences. For the multi-objective spanning tree problem with a linear aggregation function, we provide numerical results to demonstrate the practical efficiency of our approach and we compare our results to a recent approach based on minimax regret, where preferences are asked during the construction of a solution. We show that better results are achieved by our method both in terms of running time and number of questions.

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e.g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.

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's preferences. For the multi-objective spanning tree problem with a linear aggregation function, we provide numerical results to demonstrate the practical efficiency of our approach and we compare our results to a recent approach based on minimax regret, where preferences are asked during the construction of a solution. We show that better results are achieved by our method both in terms of running time and number of questions.