Combining Local Search and Elicitation for Multi-Objective Combinatorial Optimization

Abstract

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.

1 Introduction

Designing efficient preference elicitation procedures to support decision making in combinatorial domains is one of the hot topics of algorithmic decision theory. On non-combinatorial domains, various model-based approaches are already available for preference learning. The elicitation process consists in analyzing preference statements provided by the decision maker (DM) to assess the parameters of the decision model and determine an optimal solution (see, e.g., [5, 7, 9, 10, 14, 31]). Within this stream of work, incremental approaches are of special interest because they aim to analyze the set feasible solutions to identify the critical preference information needed to find the optimal alternative. By a careful selection of preference queries, they make it possible to determine the optimal choice within large sets, using a reasonably small number of questions, see e.g., [10] for an example in a Bayesian setting, and [7] for another approach based on a progressive reduction of the uncertainty attached to the model parameters.

The incremental approach was efficiently used in various decision contexts such as multiattribute utility theory or multicriteria decision making [8, 30, 34], decision making under risk [10, 17, 26, 32] and collective decision making [23]. However, extending these approaches for decision support on combinatorial domains is more challenging due to the implicit definition of the set of solutions and the huge number of feasible solutions. In order to overcome this problem, several contributions aim to combine standard search procedures used in combinatorial optimization with incremental preference elicitation. Examples can be found in various contexts such as constraint satisfaction [15], committee election [3], matching [13], sequential decision making under risk [28, 33], fair multiagent optimization [6] and multicriteria optimization [1, 19].

In multicriteria optimization, the search procedure combines the implicit enumeration of Pareto-optimal solutions with preferences queries allowing a progressive reduction of the uncertainty attached to the parameters of the preference aggregation model, in order to progressively focus the exploration on the most attractive solutions. Various attempts to interleave incremental preference elicitation methods and constructive algorithms have been proposed. The basic principle consists in constructing the optimal solution from optimal sub-solutions using the available preference information, and to ask new preference information when necessary. This has been tested for greedy algorithms, for dynamic programming, for $A^*$ and branch-and-bound search, see [4] for a synthesis.

In this paper we explore another way by considering non-constructive algorithms. We propose to interleave the elicitation with local search for multicriteria optimization. To illustrate our purpose, let us consider the following example:

Fig. 1.

An instance of the TSP with two criteria.

Example 1

Let us consider the instance of the multi-objective traveling salesman problem (TSP) depicted in Fig. 1, including 5 nodes and two additive cost functions to be minimized (one looks for a cycle passing exactly once through each node of the graph and minimizing costs). Let us start a local search from the boldface tour $x_0=ADBECA$ whose cost vector is (45, 35), using a neighborhood definition based on the simple exchange of two consecutive nodes. Among the neighbors of $x_0$, there is $x'_0=ABDECA$ whose cost vector is (31, 49). Assume that the DM declares that $x_0$ is better than $x'_0$ (denoted $x_0 \succ x'_0$).

Let us show what could be a local search on this instance using partial preference information interpreted under a linear model assumption:

Using a Linear Model. We assume here that DM’s preferences can be represented by a linear model of the form: $f_\omega (y_1,y_2) = \omega y_1 +(1-\omega ) y_2$ for some unknown $\omega \in (0, 1)$, where $(y_1, y_2)$ is the cost vector associated to a feasible tour. In this case the $x_0 \succ x'_0$ condition implies $f_\omega (45,35) < f_\omega (31,49)$ and therefore $\omega \in (0, 1/2)$. After this restriction of the set of possible values for $\omega$ it can easily be checked that the optimal neighbor of $x_0$ is solution $x_1 = ADBCEA$ of cost (60, 20). Then by exploring the neighborhood of $x_1$ it can easily be checked that no other solution can improve $x_1$ given that $\omega < 1/2$. We get a local optimum which is actually the optimal solution for this instance.

We can see here that, under the linear model assumption, an optimal solution has been obtained using a single preference query. However, the linear model is not always suitable. For example, when one looks for a compromise solution between the two criteria, one could prefer resorting to a decision model favoring the generation of solutions having a balanced cost vector. For this reason we consider now another elicitation session using a non-linear weighted aggregation function commonly used to control the balance between criterion values, namely the Ordered Weighted Average (OWA, [22, 35]).

Using the OWA Model. Now, let us assume that the DM’s preferences are represented by a non-linear model of the form: $f_\omega (y_1,y_2) = \omega \max \{y_1,y_2\} +$$(1-\omega ) \min \{y_1,y_2\}$ for some unknown $\omega \in (0, 1)$. In this case the $x_0 \succ x'_0$ condition implies $45 \omega + 35(1-\omega ) < 49 \omega + 31 (1- \omega )$ and therefore $\omega \in (1/2,1)$ (note that although OWA is not linear in y, it is linear in $\omega$ and therefore any preference statement translates into a linear constraint on $\omega$). After this restriction of the set of possible values for $\omega$ it can easily be checked that the optimal neighbor of $x_0$ is solution $x_2 = ABECDA$ whose cost vector is (40, 40). Then, by exploring the neighborhood of $x_2$, it can easily be checked that no other solution can improve $x_2$ given that $\omega > 1/2$. We obtain a local optimum which is actually the OWA-optimal solution for this instance, given the restriction on $\omega$.

These simple executions of local search using partial preference information show the potential of interactive local search combining local exploration of neighborhoods and model-based preference elicitation. For a given class of preference models, the successive answers from the DM to preference queries make it possible to progressively reduce the set of possible parameters and to discriminate the solutions belonging to the neighborhood of solutions found so far.

The combination of preference elicitation has several specific advantages. In particular, preference elicitation is based on very simple queries because they involve neighbor solutions that are cognitively simpler to compare than pairs of solutions varying in all aspects. Moreover, preference queries only involve complete solutions. This provides two advantages: (1) solutions are easier to compare, and (2) no independence assumption is required in the definition of preferences (no need to reason on partial descriptions under the assumption that preferences hold everything all being equal). The latter point is of special interest when preferences are represented by non-linear decision models. With such models, the cost of partial solutions is a poor predictor of the actual cost of their extensions. This seriously reduces possibilities of pruning sub-solutions in constructive algorithms. Since we consider only complete solutions in local search, this problem vanishes. Another interest of studying incremental elicitation approaches in local search is to tackle preference-based combinatorial optimization problems for which no efficient exact algorithm is known.

The paper is organized as follows. Section 2 introduces some preliminary background and notations. Then, we present a general interactive local search in Sect. 3. In Sect. 4 we further specify our approach for application to the multi-objective TSP and provide numerical tests showing the practical efficiency of the proposed incremental elicitation process.

2 Background and Notations

In this section, we present the necessary background on multi-objective combinatorial optimization and regret-based incremental elicitation.

2.1 Multi-Objective Combinatorial Optimization

We consider a multi-objective combinatorial optimization (MOCO) problem with n objectives/criteria $y_i,i \in \{1,\ldots ,n\}$, that need to be minimized. This problem can be formulated as follows: $\underset{x \in \mathcal {X}}{\text {minimize}} \big (y_1(x),\ldots ,y_n(x)\big )$ where $\mathcal {X}$ is the feasible set in the decision space (e.g., for the TSP, $\mathcal {X}$ is the set of all Hamiltonian cycles). In this problem, any solution $x \in \mathcal {X}$ is associated with a vector $y(x)= (y_1(x),\ldots ,y_n(x)) \in \mathbb {R}^n$ that gives its evaluations on all criteria. Solutions are usually compared through their images in the objective space (also called points) using the Pareto dominance relation: point $a=(a_1,\ldots ,a_n) \in \mathbb {R}^n$ is said to Pareto dominate point $b=(b_1,\ldots ,b_n)\in \mathbb {R}^n$ (denoted by $a \prec _P b$) if and only if $a_i \le b_i$ for all $i \in \{1,\ldots ,n\}$ and $a_i < b_i$ for some $i \in \{1,\ldots ,n\}$. A solution $x \in \mathcal {X}$ is said to be efficient if there is no other feasible solution $x' \in \mathcal {X}$ such that $y(x') \prec _P y(x)$ and the set $\mathcal {X}_E$ of all efficient solutions is called the efficient set (their images are respectively called non-dominated point and Pareto front).

We assume here that the DM needs to select a single solution. Without any preference information, we only know that her preferred solution is an element of the efficient set. However, it is well-known that the number of efficient solutions (and the number of non-dominated points) can be exponential in the size of the problem (e.g., [18] for the multicriteria spanning tree problem); in such situations, identifying the Pareto front is not enough to help the DM in making a decision. One way to address this issue is to reduce the size of the Pareto front by constructing a “well-represented” set; for instance, this set can be obtained by dividing the objective space into different regions (e.g., [20]) or by using some approximate dominance relation (e.g., $\epsilon$-dominance [21]). However, in situations where the DM needs to select only one solution, it seems more appropriate to refine the Pareto dominance with preferences in order to determine the optimal solution according to the DM’s subjective preferences.

In this work, we assume that the DM’s subjective preferences can be represented by a parameterized scalarizing function $f_\omega$ that is linear in its preference parameters $\omega$. For example, function $f_\omega$ can be a weighted sum (i.e., $f_\omega (a) = \sum _{i=1}^n \omega _i a_i$), an OWA aggregator ($f_\omega (a) =\sum _{i=1}^n \omega _i a_{(i)}$ where $a_{(i)}\ge \ldots \ge a_{(n)}$ are the components of a sorted in non-increasing order, see e.g. [35]) or even a Choquet integral with capacity $\omega$ (see e.g. [11, 16]). In this context, solution $x\in \mathcal {X}$ is preferred to solution $x'\in \mathcal {X}$ by the DM if and only if $f_\omega (y(x)) \le f_\omega (y(x'))$. Thus any solution $x \in \mathcal {X}$ that minimizes function $f_\omega$ is optimal according to the DM’s preferences.

2.2 Regret-Based Incremental Elicitation

For the purpose of elicitation, we assume that preference parameters $\omega$ are not known initially. More precisely, we are given a (possibly empty) set $\varTheta$ of preference statements of type $(a,b) \in \mathbb {R}^n\times \mathbb {R}^n$, meaning that the DM prefers point a to point b, and we consider the set $\varOmega _\varTheta$ of all parameters $\omega$ that are compatible with $\varTheta$ the available preference information. Formally, set $\varOmega _\varTheta$ is defined by $\varOmega _\varTheta =\{\omega : \forall (a,b) \in \varTheta , f_\omega (a) \le f_\omega (b)\}$. Note that $\varOmega _\varTheta$ is a convex polyhedron since function $f_\omega$ is assumed to be linear in its parameters $\omega$.

Our goal now is to determine the most promising solution under the parameter imprecision characterized by $\varOmega _\varTheta$. To this aim, we consider the minimax regret approach (e.g., [7]) which is based on the following definitions:

Definition 1 (Pairwise Max Regret)

The Pairwise Max Regret (PMR) of solution $x \in \mathcal {X}$ with respect to solution $x' \in \mathcal {X}$ is:

$$ PMR(x,x',\varOmega _\varTheta ) = \max _{\omega \in \varOmega _\varTheta } \Big \{ f_\omega (y(x)) - f_\omega (y(x')) \Big \} $$

By definition, $PMR(x,x',\varOmega _\varTheta )$ is the worst-case loss when recommending solution x instead of solution $x'$ to the DM¹.

Definition 2 (Max Regret)

The Max Regret (MR) of solution $x \in \mathcal {X}$ is:

$$ MR(x, \mathcal {X},\varOmega _\varTheta ) = \max _{x' \in \mathcal {X}} PMR(x,x',\varOmega _\varTheta ) $$

In other words, $MR(x, \mathcal {X},\varOmega _\varTheta )$ is the worst-case loss when choosing x instead of any other solution $x' \in \mathcal {X}$. Finally, the minimax reget is defined as follows:

Definition 3 (Minimax Regret)

The MiniMax Regret (MMR) is:

$$ MMR(\mathcal {X},\varOmega _\varTheta ) = \min _{x \in \mathcal {X}} MR(x,\mathcal {X},\varOmega _\varTheta ) $$

A solution $x^* \in \mathcal {X}$ is optimal according to the minimax regret decision criterion if $x^*$ achieves the minimax regret, i.e. if $x^* \in \arg \min _{x \in \mathcal {X}} MR(x,\mathcal {X},\varOmega _\varTheta )$. Recommending such a solution guarantees that the worst-case loss is minimized (given the imprecision surrounding the DM’s preferences). Moreover, if $MMR(\mathcal {X},\varOmega _\varTheta ) = 0$, then we know that any optimal solution for the minimax regret criterion is necessarily optimal according to the DM’s preferences.

Note that we have $MMR(\mathcal {X},\varOmega _{\varTheta '}) \le MMR(\mathcal {X},\varOmega _\varTheta )$ for any set $\varTheta ' \supseteq \varTheta$, as already observed in previous works (see e.g., [5]). Thus the general principle of regret-based incremental elicitation is to iteratively collect preference information by asking preference queries to the DM until $MMR(\mathcal {X},\varOmega _\varTheta )$ drops below a given tolerance threshold $\delta \ge 0$ (representing the maximum allowable gap to optimality); if we set $\delta = 0$, then we obtain the (optimal) preferred solution at the end of the execution.

3 An Interactive Local Search Algorithm

For MOCO problems, regret-based incremental elicitation may induce prohibitive computation times since it may require to compute the pairwise max regrets for all pairs of distinct solutions in $\mathcal {X}$ (see Definitions 2 and 3). This observation has led a group of researchers to propose a new approach consisting in combining regret-based incremental elicitation and search by asking preference queries during the construction of the (near-)optimal solution (e.g. [2]). In this paper, we combine incremental elicitation and search in a different way. More precisely, we propose an interactive local search procedure that generates preference queries (1) before the local search to determine a promising starting point and (2) during the local search to help identifying the best solution within a neighborhood.

Our interactive algorithm takes as input a MOCO problem P, two thresholds $\delta = (\delta _1,\delta _2), (\delta _1,\delta _2 \ge 0)$, a scalarizing function $f_\omega$ with unknown parameters $\omega$, an initial set of preference statements $\varTheta$ (possibly empty), and m the number of possible starting solutions (generated at the beginning of the procedure). First, our algorithm identifies a promising starting solution as follows:

• 1. A set of m admissible preference parameters $\omega ^k$, $k \in \{1,\ldots , m\},$ are randomly generated within $\varOmega _\varTheta$.

• 2. Then, for every $k \in \{1,\ldots , m\},$ a (near-)optimal solution is determined for the precise scalarizing function $f_{\omega ^k}$ using an existing efficient algorithm. Let $X_0$ be the set of generated solutions.

• 3. Finally, preference queries are generated in order to discriminate between the solutions in $X_0$. More precisely, while $MMR(X_0, \varOmega _\varTheta ) > \delta _1$, the DM is asked to compare two solutions $x,x' \in X_0$ and the set of admissible parameters is updated by inserting the constraint $f_\omega (x) \le f_\omega (x')$ (or $f_\omega (x) \ge f_\omega (x')$ depending on her answer); once $MMR(X_0, \varOmega _\varTheta )$ drops below $\delta _1$, the starting solution $x^*$ is arbitrarily chosen in $\arg \min _{x \in X_0} MR(x,X_0,\varOmega _\varTheta )$.

Then, our algorithm moves from solution to solution by considering local improvements. More precisely, it iterates as follows:

• 1. Firstly, a set $X^*$ of solutions is generated from $x^*$ using a neighborhood function defined on the search space; we add $x^*$ to $X^*$ and remove from $X^*$ any solution that is Pareto-dominated by another solution in this set.

• 2. Secondly, while $MMR(X^*, \varOmega _\varTheta ) > \delta _2$, the DM is asked to compare two solutions $x,x' \in X^*$ and $\varOmega _\varTheta$ is restricted by inserting the constraint $f_\omega (x) \le f_\omega (x')$ (or $f_\omega (x) \ge f_\omega (x')$).

• 3. Finally, if $MR(x^*,X^*,\varOmega _\varTheta ) > \delta _2$ holds, solution $x^*$ is then replaced by a neighbor solution minimizing the max regret in $X^*$; otherwise, the algorithm stops by returning solution $x^*$.

Our algorithm is called ILS for Interactive Local Search and is summarized in Algorithm 1.

Note that procedures Select&Optimize and Neighbors depend on the problem considered; for instance, for the multicriteria spanning tree problem with a weighted sum model, the optimization part can be performed using Prim algorithm [27] and the neighborhood function can be defined by edge swaps. Note also that procedure Query(X) can implement any query generation strategy that selects two solutions in X and asks the DM to compare them; in the numerical section, we propose and compare different query generation strategies.

It is well-known that local search is a heuristic search that may stuck at a locally optimal point that is not globally optimal; the problem obviously remains when using our interactive local search. However, it is worth noting that our algorithm with $\delta _2=0$ provides the same performance guarantees as the corresponding local search algorithm with precise preferences. To give an example, when using the 2-opt neighborhood function [12], our algorithm approximately solves the TSP within a differential-approximation ratio bounded above by 1/2 (see [24] for further details); in the numerical section, we will see that the error is even lower in practice.

For illustration purposes, we now present an execution of our algorithm on a small instance of the multi-objective TSP:

Fig. 2.

The graph on the left side of the figure represents an instance of the 3-objective TSP with 6 vertices. The two others graphs give an example of a 2-opt movement: the dashed edges of the cycle in the middle are deleted and then replaced by the dashed edges in the right side of the figure.

Example 2

Consider the 3-objective TSP with 6 vertices defined by Fig. 2. In this problem, the set $\mathcal {X}$ of feasible solutions is the set of all Hamiltonian cycles, i.e. cycles that include every node exactly once. We now apply ILS algorithm with $\delta =(0,0)$ on this instance considering the neighborhood function defined by 2-opt swaps [12]; in other words, the neighbors of cycles are all the cycles that can be obtained by deleting two edges and adding two other edges from the graph (see Fig. 2 for an example).

We assume here that the DM’s preferences can be represented by a weighted sum with the hidden weight $\omega ^* = (0.2, 0.1, 0.7)$ and we start the execution with an empty set of preference statements (i.e. $\varTheta = \emptyset$). Hence $\varOmega _\varTheta$ is initially the set of all weighting vectors $\omega =(\omega _1,\omega _2,\omega _3) \in [0,1]^3$ such that $\omega _1+\omega _2+\omega _3=1$. In Fig. 3, we represent $\varOmega _\varTheta$ by the triangle ABC in the space $(\omega _1,\omega _2)$, $\omega _3$ being implicitly defined by $\omega _3 = 1-\omega _1-\omega _2$.

Identification of a Promising Starting Solution: First, we generate $m=2$ weighting vectors $\omega ^1$ and $\omega ^2$ at random and we determine then the corresponding optimal solutions $x^1$ and $x^2$. If $\omega ^1 = (0.6, 0.3, 0.1)$ and $\omega ^2 = (0.3, 0.6, 0.1)$, we obtain the following evaluation: $y(x^1)=(19, 34, 30)$ and $y(x^2) = (21, 32, 27)$. Let $X_0 = \{x^1,x^2\}$. Since $MMR(X_0,\varOmega _\varTheta ) = 2 > \delta _1$, we ask the DM to compare $x^1$ and $x^2$. Since $f_{\omega ^*}(y(x^1)) = 28.2 > f_{\omega ^*}(y(x^2)) = 26.3$, the DM prefers solution $x^2$ to $x^1$. Therefore we set $\varTheta =\{((21, 32, 27), (19, 34, 30))\}$ and $\varOmega _\varTheta$ is restricted by imposing the constraint $f_\omega (y(x^2))\le f_\omega (y(x^1))$, i.e. $\omega _2 \le -5\omega _1+3$ (see Fig. 4 where $\varOmega _\varTheta$ is represented by ABDE). Now we have $MMR(X_0, \varOmega _\varTheta ) = MR(x^2,X_0, \varOmega _\varTheta ) = 0 \le \delta _1$, and therefore $x^2$ is chosen to be the starting solution (i.e. $x^* = x^2$).

Local Search: At the first iteration step, three neighbors of $x^*$ are Pareto non-dominated, and the set $X^*$ contains four solutions, denoted by $x^1$, $x^2(=x^*)$, $x^3$ and $x^4$ evaluated as follows: $y(x^1)=(23, 34, 26)$, $y(x^2)=(21, 32, 27)$, $y(x^3) = (19, 34, 30)$ and $y(x^4)=(20, 31, 30)$. Since $MMR(X^*,\varOmega _\varTheta ) = 1 > \delta _2$, we ask the DM to compare two solutions in $X^*$, say $x^1$ and $x^*$. As $f_{\omega ^*}(y(x^1)) = 26.2 < f_{\omega ^*}(y(x^*)) = 26.3$, the DM prefers $x^1$ to $x^*$. Therefore we obtain $\varTheta =\{((21, 32, 27), (19, 34, 30)), ((23, 34, 26),(21, 32, 27))\}$ and $\varOmega _\varTheta$ is restricted by the linear constraint $f_{\omega }(y(x^1)) \le f_{\omega }(y(x^*))$, i.e. $\omega _2 \le -\omega _1 + 1/3$ (see Fig. 5 where $\varOmega _\varTheta$ is represented by AGF). Then we stop asking queries at this step since we have $MMR(X^*, \varOmega _\varTheta ) = MR(x^1,X^*, \varOmega _\varTheta ) = 0 \le \delta _2$. We move from $x^* = x^2$ to solution $x^1$ for the next step (i.e., we now set $x^*=x^1$).

At the second iteration step, $X^*$ only includes three solutions denoted by $x^1 (=x^*)$, $x^2$ and $x^3$ with $y(x^1)=(23, 34, 26)$, $y(x^2)=(21, 32, 27)$ and $y(x^3)=(19, 33, 31)$. Since $MMR(X^*,\varOmega _\varTheta ) = 0 \le \delta _2$, no query is generated at this step. Moreover, $MR(x^*,X^*,\varOmega _\varTheta ) = 0\le \delta _2$ (that is $x^* \in \arg \min _{x \in X^*} MR(x,X^*,\varOmega _\varTheta )$) and $x^*$ is thus a local optimum (variable improve is set to false and the while loop ends). Therefore, after two iteration steps, ILS algorithm stops by returning the solution $x^* = x^1$ which is the preferred solution in this problem. Note that only two preference queries were needed to discriminate between the 60 feasible solutions (among which 10 are Pareto-optimal).

Fig. 3.

Initial set $\varOmega _\varTheta$.

Fig. 4.

$\varOmega _\varTheta$ after 1 query.

Fig. 5.

$\varOmega _\varTheta$ after 2 queries.

To illustrate ILS and the impact of m (the number of initial solutions), we show the evolution of the local search on a randomly generated instance of the bi-criteria TSP with 100 cities (see Fig. 6). The left part of the figure ($m=1$) shows that the neighborhood function enables to go straight to the optimal solution instead of following the Pareto front. However the number of iterations can still be very large when the starting solution is far from the optimal solution in the objective space. The right part of the figure ($m=2$) shows that the number of iterations can be much reduced when increasing the number of possible starting solutions and selecting the most preferred one.

Fig. 6.

Results obtained for an instance of the 2-criteria TSP.

4 Numerical Tests

In this section, we provide numerical results aiming to estimate the performance of our algorithm. In these experiments, we use existing Euclidean instances² of the multi-objective TSP with 25 to 100 cities, and $n=3$ to 6 objectives. Numerical tests were performed on a Intel Core i7-8550U CPU with 16 GB of RAM, with a program written in C++³.

4.1 Preferences Represented by a Weighted Sum

We assume here that the preferences are represented by a weighted sum $f_\omega$ with imprecise weights, with an empty set of preference statements (i.e. $\varTheta = \emptyset )$. The answers to queries are simulated using a weighting vector $\omega$ randomly generated before running the algorithm, using the procedure presented in [29], to guarantee a uniform distribution of the weights.

In ILS algorithm, procedure Query(X) selects two solutions from X and then asks the DM to compare them. We first want to estimate the impact of the query generation strategy on the performances of ILS algorithm. To do so, we consider the following two query generation strategies:

• Random: the set of possibly optimal solutions in X are computed and then two of them are selected at random at each iteration step; note that the set of possibly optimal solutions in X can be determined in polynomial time in the size of X (see e.g.,  [1]).

• CSS: The Current Solution Strategy (CSS) selects a solution $x^* \in X$ that minimizes the max regret $MR(x^*,X,\varOmega _\varTheta )$ and then the DM is asked to compare solution $x^*$ with one of its adversary’s choice (i.e. a solution in $\arg \max _{x\in X} PMR(x^*,x,\varOmega _\varTheta )$) [7].

These strategies are compared in terms of computation time (given in seconds), number of generated queries and the error (expressed in terms of percentage from the optimal solution). Results averaged over 100 runs are given in Table 1 for the instance with 50 cities. In this table, “/” means that the timeout is exceeded (the timeout is set to 900 seconds).

Table 1. Comparison between CSS and Random strategies, 50 cities, $\delta =(0,0)$.

First, we see that the query strategy has an important impact on the quality of the results: with the random strategy the number of queries and computation time are much higher than with the CSS strategy, showing that preference queries must be carefully chosen when designing incremental elicitation methods. Then we see that ILS with CSS achieves better results when increasing the number of possible initial solutions, in terms of computation times, queries and error (as the selected starting solution is becoming closer to the best solution). Although the error is very low (about less than $2\%$) for both strategies, the number of queries is quite high for instances with 6 criteria (at least 54 queries). This is due to the fact that we use the tolerance thresholds $\delta =(0,0)$.

We now compare the results obtained with $\delta = (0,0)$ and $\delta = (0.1,0.4)$ (see the left part of Table 2); we set $\delta _1<\delta _2$ since the starting point selection has a significant impact on local search performances. We also give the results obtained by ILS when a ranking of the objectives can be provided by the DM prior to the search (see the right part of Table 2). We vary n the number of criteria between 3 and 6, and we set m the number of initial solutions to 100.

In Table 2, we see that using strictly positive thresholds enables to reduce both the number of queries and the computation time without having much impact on the error. For instance, for $n=6$, the error is equal to $1.35 \%$ with $\delta = (0,0)$ whereas it is equal to $1.77\%$ with $\delta = (0.1,0.4)$, while the number of queries is reduced from 54.40 to 32.24. We also remark that knowing the ranking of the objectives allows to further reduce the number of queries (only 23.75 queries for $n=6$, with an error of $1.51\%$).

Table 2. Performances of ILS combined with CSS, with (left) and without the ranking of the objectives (right), 50 cities, $m=100$, 100 runs.

In Fig. 7, we show the evolution of the number of queries according to the number of criteria (left part, 50 cities) and number of cities (right), with $\delta =(0.1,0.4)$ and $m=100$. We note that the number of queries evolves more or less linearly according to the number of criteria/cities.

Fig. 7.

Evolution of the queries according to number of criteria and number of cities.

4.2 Preferences Represented by an OWA Aggregator

Now we assume that the DM’s preferences can be represented by an OWA aggregator, with decreasing weights, favoring well-balanced solutions [35] (as the larger weights are associated with the worst values). Contrary to the weighted sum, when the weights $\omega$ are known, we cannot reduce the multi-objective TSP to a single-objective TSP as the OWA aggregator is not a linear operator. Therefore, to obtain the optimal solution with known weights (to be able to compute the error), we have used a well-known linearization of the OWA operator with decreasing weights (see [25]); for information purposes, we also provide the computation time needed when solving the corresponding linear program with the LP-solver (see “LP time”).

In Table 3, we give the results obtained by ILS combined with the CSS for the instances with 50 cities, 3 to 6 criteria and $m=10$ starting solutions (obtained by optimizing 10 randomly generated weighted sum). The results show that the number of queries is much reduced compared to the weighted sum, with an error also around $2\%$. Moreover, we observe that using our algorithm to solve the problem with unknown weights is much faster than using the LP-solver to obtain the optimal solution when the weights are known. This shows that our algorithm can be used to efficiently solve multi-objective optimization problems with complex decision models, even for problems such that there is no efficient algorithm for the determination of the optimal solution with known preference parameters.

Table 3. ILS combined with CSS with OWA, 50 cities, $m=10$.

Finally, in Fig. 8, we illustrate the iterations of ILS when preferences are represented by an OWA operator with decreasing weights (which favors well-balanced solutions).

Fig. 8.

Results obtained for an instance of the 2-criteria TSP with OWA operator.

5 Conclusion

In this paper, we have proposed a general approach based on local search and incremental elicitation for solving multi-objective combinatorial optimization problems with unkown preference parameters. We have applied the method to a NP-hard combinatorial optimization problem and we have shown that, by combining the generation of promising starting solutions with an adaptive preference-based local search, we are able to rapidly obtain high quality solutions, even with a non-linear aggregation function like OWA. The approach can be applied to any multi-objective combinatorial optimization problem provided that the scalarizing function used to compare solutions is linear in its parameters.