An Interactive Polyhedral Approach for Multi-objective Combinatorial Optimization with Incomplete Preference Information

Abstract

In this paper, we develop a general interactive polyhedral approach to solve multi-objective combinatorial optimization problems with incomplete preference information. 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 imprecision 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. We provide numerical results for the multi-objective spanning tree and traveling salesman problems with preferences represented by a weighted sum to demonstrate the practical efficiency of our approach. We compare our results to a recent approach based on minimax regret, where preference queries are generated during the construction of an optimal solution. We show that better results are achieved by our method both in terms of running time and number of questions.

1 Introduction

The increasing complexity of applications encountered in Computer Science significantly complicates the task of decision makers who need to find the best solution among a very large number of options. Multi-objective optimization is concerned with optimization problems involving several (conflicting) objectives/criteria to be optimized simultaneously (e.g., minimizing costs while maximizing profits). Without preference information, we only know that the best solution for the decision maker (DM) is among the Pareto-optimal solutions (a solution is called Pareto-optimal if there exists no other solution that is better on all objectives while being strictly better on at least one of them). The main problem with this kind of approach is that the number of Pareto-optimal solutions can be intractable, that is exponential in the size of the problem (e.g. [13] for the multicriteria spanning tree problem). One way to address this issue is to restrict the size of the Pareto set in order to obtain a “well-represented” Pareto set; this approach is often based on a division of the objective space into different regions (e.g., [15]) or on $\epsilon$-dominance (e.g., [18]). However, whenever the DM needs to identify the best solution, it seems more appropriate to refine the Pareto dominance relation with preferences to determine a single solution satisfying the subjective preferences of the DM. Of course, this implies the participation of the DM who has to give us some insights and share her preferences.

In this work, we assume that the DM’s preferences can be represented by a parameterized scalarizing function (e.g., a weighted sum), allowing some trade-off between the objectives, but the corresponding preference parameters (e.g., the weights) are initially not known; hence, we have to consider the set of all parameters compatible with the collected preference information. An interesting approach to deal with preference imprecision has been recently developed [19, 21, 30] and consists in determining the possibly optimal solutions, that is the solutions that are optimal for at least one instance of the preference parameters. The main drawback of this approach, though, is that the number of possibly optimal solutions may still be very large compared to the number of Pareto-optimal solutions; therefore there is a need for elicitation methods aiming to specify the preference model by asking preference queries to the DM.

In this paper, we study the potential of incremental preference elicitation (e.g., [23, 27]) in the framework of multi-objective combinatorial optimization. Preference elicitation on combinatorial domains is an active topic that has been recently studied in various contexts, e.g. in multi-agents systems [1, 3, 6], in stable matching problems [9], in constraint satisfaction problems [7], in Markov Decision Processes [11, 24, 28] and in multi-objective optimization problems [4, 14, 16]. Our aim here is to propose a general interactive approach for multi-objective optimization with imprecise preference parameters. Our approach identifies informative preference queries by exploiting the extreme points of the polyhedron representing the admissible preference parameters. Moreover, these extreme points are also used to provide a stopping criterion which guarantees the determination of the (near-)optimal solution. Our approach is general in the sense that it can be applied to any multi-objective optimization problem, providing that the scalarizing function is linear in its preference parameters (e.g., weighted sums, Choquet integrals [8, 12]) and that there exists an efficient algorithm to solve the problem when preferences are precisely known (e.g., [17, 22] for the minimum spanning tree problem with a weighted sum).

The paper is organized as follows: We first give general notations and recall the basic principles of regret-based incremental elicitation. We then propose a new interactive method based on the minimax regret decision criterion and extreme points generation. Finally, to show the efficiency of our method, we provide numerical results for two well-known problems, namely the multicriteria traveling salesman and multicriteria spanning tree problems; for the latter, we compare our results with those obtained by the state-of-the-art method.

2 Multi-objective Combinatorial Optimization

In this paper, we consider a general multi-objective combinatorial optimization (MOCO) problem with n objective functions $y_i,i \in \{1,\ldots ,n\}$, to be minimized. This problem can be defined as follows:

$$ \underset{x \in \mathcal {X}}{\text {minimize}} \big (y_1(x),\ldots ,y_n(x)\big )$$

In this definition, $\mathcal {X}$ is the feasible set in the decision space, typically defined by some constraint functions (e.g., for the multicriteria spanning tree problem, $\mathcal {X}$ is the set of all spanning trees of the graph). In this problem, any solution $x \in \mathcal {X}$ is associated with a cost vector $y(x)= (y_1(x),\ldots ,y_n(x)) \in \mathbb {R}^n$ where $y_i(x)$ is the evaluation of x on the i-th criterion/objective. Thus the image of the feasible set in the objective space is defined by $\{y(x) : x \in \mathcal {X}\} \subset \mathbb {R}^n$.

Solutions are usually compared through their images in the objective space (also called points) using the Pareto dominance relation: we say that point $u=(u_1,\ldots ,u_n) \in \mathbb {R}^n$ Pareto dominates point $v=(v_1,\ldots ,v_n)\in \mathbb {R}^n$ (denoted by $u \prec _P v$) if and only if $u_i \le v_i$ for all $i \in \{1,\ldots ,n\}$, with at least one strict inequality. Solution $x^* \in \mathcal {X}$ is called efficient if there does not exist any other feasible solution $x \in \mathcal {X}$ such that $y(x) \prec _P y(x^*)$; its image in objective space is then called a non-dominated point.

3 Minimax Regret Criterion

We assume here that the DM’s preferences over solutions can be represented by a parameterized scalarizing function $f_\omega$ that is linear in its parameters $\omega$. Solution $x\in \mathcal {X}$ is preferred to solution $x'\in \mathcal {X}$ if and only if $f_\omega (y(x)) \le f_\omega (y(x'))$. To give a few examples, function $f_\omega$ can be a weighted sum (i.e. $f_\omega (y(x)) = \sum _{i=1}^n \omega _i y_i(x)$) or a Choquet integral with capacity $\omega$ [8, 12]. We also assume that parameters $\omega$ are not known initially. Instead, we consider a (possibly empty) set $\varTheta$ of pairs $(u,v)\in \mathbb {R}^n\times \mathbb {R}^n$ such that u is known to be preferred to v; this set can be obtained by asking preference queries to the DM. Let $\varOmega _\varTheta$ be the set of all parameters $\omega$ that are compatible with $\varTheta$, i.e. all parameters $\omega$ that satisfy the constraints $f_\omega (u) \le f_\omega (v)$ for all $(u,v) \in \varTheta$. Thus, since $f_\omega$ is linear in $\omega$, we can assume that $\varOmega _\varTheta$ is a convex polyhedron throughout the paper. The problem is now to determine the most promising solution under the preference imprecision (defined by $\varOmega _\varTheta$). To do so, we use 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 } \{ f_\omega (y(x)) - f_\omega (y(x')) \} $$

In other words, $PMR(x,x',\varOmega _\varTheta )$ is the worst-case loss when choosing solution x instead of solution $x'$.

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 ) $$

Thus $MR(x, \mathcal {X},\varOmega _\varTheta )$ is the worst-case loss when selecting solution x instead of any other feasible solution $x' \in \mathcal {X}$. We can now define the minimax regret:

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 ) $$

According to the minimax regret criterion, an optimal solution is a solution that achieves the minimax regret (i.e., any solution in $\arg \min _{x \in \mathcal {X}} MR(x,\mathcal {X},\varOmega _\varTheta )$), allowing to minimize the worst-case loss. Note that if $MMR(\mathcal {X},\varOmega _\varTheta ) = 0$, then any optimal solution for the minimax regret criterion is necessarily optimal according to the DM’s preferences.

4 An Interactive Polyhedral Method

Our aim is to produce an efficient regret-based interactive method for the determination of a (near-)optimal solution according to the DM’s preferences. Note that the value $MMR(\mathcal {X},\varOmega _\varTheta )$ can only decrease when inserting new preference information in $\varTheta$, as observed in previous works (see e.g., [5]). Therefore, the general idea of regret-based incremental elicitation is to ask preference queries to the DM in an iterative way, until the value $MMR(\mathcal {X},\varOmega _\varTheta )$ drops below a given threshold $\delta \ge 0$ representing the maximum allowable gap to optimality; one can simply set $\delta = 0$ to obtain the preferred solution (i.e., the optimal solution according to the DM’s preferences).

At each iteration step, the minimax regret $MMR(\mathcal {X},\varOmega _\varTheta )$ could be obtained by computing the pairwise max regrets $PMR(x,x',\varOmega _\varTheta )$ for all pairs $(x,x')$ of distinct solutions in $\mathcal {X}$ (see Definitions 2 and 3). However, this would not be very efficient in practice due to the large size of $\mathcal {X}$ (recall that $\mathcal {X}$ is the feasible set of a MOCO problem). This observation has led a group of researchers to propose a new approach consisting in combining preference elicitation and search by asking preference queries during the construction of the (near-)optimal solution (e.g., [2]). In this work, we propose to combine incremental elicitation and search in a different way: at each iteration step, we generate a set of promising solutions using the extreme points of $\varOmega _{\varTheta }$ (the set of admissible parameters), we ask the DM to compare two of these solutions, we update $\varOmega _\varTheta$ according to her answer and we stop the process whenever a (near-)optimal solution is detected (i.e. a solution $x \in \mathcal {X}$ such that $MR(x,\mathcal {X},\varOmega _\varTheta ) \le \delta$ holds). More precisely, taking as input a MOCO problem P, a tolerance threshold $\delta \ge 0$, a scalarizing function $f_\omega$ with unknown parameters $\omega$ and an initial set of preference statements $\varTheta$, our algorithm iterates as follows:

• 1. First, the set of all extreme points of polyhedron $\varOmega _\varTheta$ are generated. This set is denoted by $EP_\varTheta$ and its kth element is denoted by $\omega ^k$.

• 2. Then, for every point $\omega ^k \in EP_\varTheta$, P is solved considering the precise scalarizing function $f_{\omega ^k}$ (the corresponding optimal solution is denoted by $x^k$).

• 3. Finally $MMR(X_\varTheta , \varOmega _\varTheta )$ is computed, where $X_\varTheta = \{x^k : k \in \{1,\ldots ,|EP_\varTheta |\}\}$. If this value is strictly larger than $\delta$, then the DM is asked to compare two solutions $x,x' \in X_\varTheta$ and $\varOmega _\varTheta$ is updated by imposing the linear constraint $f_\omega (x) \le f_\omega (x')$ (or $f_\omega (x) \ge f_\omega (x')$ depending on her answer); the algorithm stops otherwise.

Our algorithm, called IEEP (for Incremental Elicitation based on Extreme Points), is summarized in Algorithm 1. The implementation details of Select, Optimizing and ExtremePoints procedures are given in the numerical section. Note however that Optimizing is a procedure that depends on the optimization problem (e.g., Prim algorithm could be used for the spanning tree problem). The following proposition establishes the validity of our interactive method:

Proposition 1

For any positive tolerance threshold $\delta$, algorithm IEEP returns a solution $x^*\in \mathcal {X}$ such that the inequality $MR(x^*,\mathcal {X},\varOmega _\varTheta ) \le \delta$ holds.

Proof

Let $x^*$ be the returned solution and let K be the number of extreme points of $\varOmega _\varTheta$ at the end of the execution. For all $k \in \{1,\ldots , K\}$, let $\omega ^k$ be the kth extreme point of $\varOmega _\varTheta$ and let $x^k$ be a solution minimizing function $f_{\omega ^k}$. Let $X_\varTheta = \{x^k : k \in \{1,\ldots ,K\}\}$. We know that $MR(x^*,X_\varTheta , \varOmega _\varTheta ) \le \delta$ holds at the end of the while loop (see the loop condition); hence we have $f_\omega (x^*) - f_\omega (x^k) \le \delta$ for all solutions $x^k \in X_\varTheta$ and all parameters $\omega \in \varOmega _\varTheta$ (see Definition 2).

We want to prove that $MR(x^*,\mathcal {X},\varOmega _\varTheta ) \le \delta$ holds at the end of execution. To do so, it is sufficient to prove that $f_\omega (x^*) - f_\omega (x) \le \delta$ holds for all $x \in \mathcal {X}$ and all $\omega \in \varOmega _\varTheta$. Since $\varOmega _\varTheta$ is a convex polyhedron, for any $\omega \in \varOmega _\varTheta$, there exists a vector $\lambda =(\lambda _1,\ldots ,\lambda _K) \in [0,1]^K$ such that $\sum _{k=1}^K \lambda ^k =1$ and $\omega = \sum _{k=1}^K \lambda _k\omega ^k$. Therefore, for all solutions $x \in \mathcal {X}$ and for all parameters $\omega \in \varOmega _\varTheta$, we have:

$$\begin{aligned} f_\omega (x^*) - f_\omega (x)&= \sum _{k=1}^K \Big [ \lambda ^k (f_{\omega ^k}(x^*) - f_{\omega ^k}(x)) \Big ] \text{ by } \text{ linearity }\\&\le \sum _{k=1}^K \Big [ \lambda ^k (f_{\omega ^k}(x^*)\! -\! f_{\omega ^k}(x^k)) \Big ] \text{ since } x^k \text{ is } f_{\omega ^k}\text{-optimal } \\&\le \sum _{k=1}^K \Big [ \lambda ^k \times \delta \Big ] \text{ since } f_\omega (x^*) - f_\omega (x^k) \le \delta \\&= \delta \times \sum _{k=1}^K \lambda ^k \\&= \delta . \end{aligned}$$

   $\square$

For illustration proposes, we now present the execution of our algorithm on a small instance of the multicriteria spanning tree problem.

Example 1

Consider the multicriteria spanning tree problem with 5 nodes and 7 edges given in Fig. 1. Each edge is evaluated with respect to 3 criteria. Assume that the DM’s preferences can be represented by a weighted sum $f_\omega$ with unknown parameters $\omega$. Our goal is to determine an optimal spanning tree for the DM ($\delta = 0$), i.e. a connected acyclic sub-graph with 5 nodes that is $f_\omega$-optimal. We now apply algorithm IEEP on this instance, starting with an empty set of preference statements (i.e. $\varTheta = \emptyset$).

Initialization: As $\varTheta = \emptyset$, $\varOmega _\varTheta$ is initialized to 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. 2, $\varOmega _\varTheta$ is represented by the triangle ABC in the space $(\omega _1,\omega _2)$; value $\omega _3$ is implicitly defined by $\omega _3 = 1-\omega _1-\omega _2$. Hence the initial extreme points are the vectors of the natural basis of the Euclidean space, corresponding to Pareto dominance [29]; in other words, we have $EP_\varTheta =\{\omega ^1,\omega ^2,\omega ^3\}$ with $\omega ^1=(1,0,0)$, $\omega ^2=(0,1,0)$ and $\omega ^3=(0,0,1)$. We then optimize according to all weighting vectors in $EP_\varTheta$ using Prim algorithm [22], and we obtain the following three solutions: for $\omega ^1$, we have a spanning tree $x^1$ evaluated by $y(x^1)=(15,17,14)$; for $\omega ^2$, we obtain a spanning tree $x^2$ with $y(x^2)=(23,8,16)$; for $\omega ^3$, we find a spanning tree $x^3$ such that $y(x^3)=(17,16,11)$. Hence we have $X_\varTheta = \{x^1,x^2,x^3\}$.

Fig. 1.

A three-criteria minimum spanning tree problem.

Iteration Step 1: Since $MMR(X_\varTheta ,\varOmega _\varTheta )=8>\delta = 0$, we ask the DM to compare two solutions in $X_\varTheta$, say $x^1$ and $x^2$. Assume that the DM prefers $x^2$. In that case, we perform the following updates: $\varTheta = \{((23,8,16),(15,17,14))\}$ and $\varOmega _\varTheta = \{\omega : f_\omega (23,8,16)\le f_\omega (15,17,14)\}$; in Fig. 3, $\varOmega _\varTheta$ is represented by triangle BFE. We then compute the set $EP_\varTheta$ of its extreme points (by applying the algorithm in [10] for example) and we obtain $EP_\varTheta =\{\omega ^1,\omega ^2,\omega ^3\}$ with $\omega ^1=(0.53,0.47,0)$, $\omega ^2=(0,0.18,0.82)$ and $\omega ^3=(0,1,0)$. We optimize according to these weights and we obtain three spanning trees: $X_\varTheta = \{x^1,x^2,x^3\}$ with $y(x^1)=(23,8,16)$, $y(x^2)=(17,16,11)$ and $y(x^3)=(19,9,14)$.

Iteration Step 2: Here $MMR(X_\varTheta ,\varOmega _\varTheta )=1.18>\delta = 0$. Therefore, we ask the DM to compare two solutions in $X_\varTheta$, say $x^1$ and $x^2$. Assume she prefers $x^2$. We then obtain $\varTheta = \{((23,8,16),(15,17,14)),((17,16,11),(23,8,16))\}$ and we set $\varOmega _\varTheta = \{\omega : f_\omega (23,8,16)\le f_\omega (15,17,14)\wedge f_\omega (17,16,11)\le$ $f_\omega (23,8,16)\}$. We compute the corresponding extreme points which are given by $EP_\varTheta = \{(0.43,0.42,0.15),(0,0.18,0.82),$ $(0,0.38,0.62)\}$ (see triangle HGE in Fig. 4); finally we have $X_\varTheta = \{x^1,x^2\}$ with $y(x^1) = (17,16,11)$ and $y(x^2)=(19,9,14)$.

Iteration Step 3: Now $MMR(X_\varTheta ,\varOmega _\varTheta )=1.18>\delta = 0$. Therefore we ask the DM to compare $x^1$ and $x^2$. Assuming that she prefers $x^2$, we update $\varTheta$ by inserting the preference statement ((19, 9, 14), (17, 16, 11)) and we update $\varOmega _\varTheta$ by imposing the following additional constraint: $f_\omega (19,9,14)\le f_\omega (17,16,11)$ (see Fig. 5); the corresponding extreme points are given by $EP_\varTheta =\{(0.18,0.28,0.54),(0,0.3,0.7),$ $(0,0.38,0.62),(0.43,0.42,0.15)\}$. Now the set $X_\varTheta$ only includes one spanning tree $x^1$ and $y(x^1)=(19,9,14)$. Finally, the algorithm stops (since we have $MMR(X_\varTheta ,\varOmega _\varTheta )=0 \le \delta =0$) and it returns solution $x^1$ (which is guaranteed to be the optimal solution for the DM).

Fig. 2.

Initial set.

Fig. 3.

After step 1.

Fig. 4.

After step 2.

Fig. 5.

After step 3.

5 Experimental Results

We now provide numerical results aiming to evaluate the performance of our interactive approach. At each iteration step of our procedure, the DM is asked to compare two solutions selected from the set $X_\varTheta$ until $MR(X_\varTheta ,\varOmega _\varTheta ) \le \delta$. Therefore, we need to estimate the impact of procedure Select on the performances of our algorithm. Here we consider the following query generation strategies:

• Random: The two solutions are randomly chosen in $X_\varTheta$.

• Max-Dist: We compute the Euclidean distance between all solutions in the objective space and we choose a pair of solutions maximizing the distance.

• CSS: The Current Solution Strategy (CSS) consists in selecting a solution that minimizes the max regret and one of its adversary’s choice [7]¹.

These strategies are compared using the following indicators:

• time: The running time given in seconds.

• eval: The number of evaluations, i.e. the number of problems with known preferences that are solved during the execution; recall that we solve one optimization problem per extreme point at each iteration step (see Optimizing).

• queries: The number of preference queries generated during the execution.

• qOpt: The number of preference queries generated until the determination of the preferred solution (but not yet proved optimal).

We assume here that the DM’s preferences can be represented by a weighted sum $f_\omega$ but the weights $\omega =(\omega _1,\ldots ,\omega _n)$ are not known initially. More precisely, we start the execution with an empty set of preference statements (i.e. $\varTheta = \emptyset$ and $\varOmega _\varTheta = \{\omega \in \mathbb {R}^n_+ : \sum _{i=1}^n \omega _i =1 \}$) and then any new preference statement $(u,v)\! \in \! \mathbb {R}^2$ obtained from the DM induces the following linear constraint over the weights: $\sum _{i=1}^n \omega _i u_i \le \sum _{i=1}^n \omega _i v_i$. Hence $\varOmega _\varTheta$ is a convex polyhedron. In our experiments, the answers to queries are simulated using a weighting vector $\omega$ randomly generated before running the algorithm, using the procedure presented in [25], to guarantee a uniform distribution of the weights.

Implementation Details. Numerical tests were performed on a Intel Core i7-7700, at 3.60 GHz, with a program written in C. At each iteration step of our algorithm, the extreme points associated to the convex polyhedron $\varOmega _\varTheta$ are generated using the polymake library². Moreover, at each step, we do not compute PMR values using a linear programming solver. Instead, we only compute score differences since the maximum value is always obtained for an extreme point of the convex polyhedron. Furthermore, to reduce the number of PMR computations, we use Pareto dominance tests between the extreme points to eliminate dominated solutions, as proposed in [20].

5.1 Multicriteria Spanning Tree

In these experiments, we consider instances of the multicriteria spanning tree (MST) problem, which is defined by a connected graph $G = (V, E)$ where each edge $e \in E$ is valued by a cost vector giving its cost with respect to different criteria/objectives (every criterion is assumed to be additive over the edges). A spanning tree of G is a connected sub-graph of G which includes every vertex $v \in V$ while containing no cycle. In this problem, $\mathcal {X}$ is the set of all spanning trees of G. We generate instances of $G=(V,E)$ with a number of vertices |V| varying between 50 and 100 and a number of objectives n ranging from 2 to 6. The edge costs are drawn within $\{1, \dots , 1000\}^n$ uniformly at random. For the MST problem, procedure Optimizing$(P,EP_\varTheta )$ proceeds as follows: First, for all extreme points $\omega ^k \in EP_\varTheta$, an instance of the spanning tree problem with a single objective is created by simply aggregating the edge costs of G using weights $\omega ^k$. Then, Prim algorithm is applied on the resulting graphs. The results obtained by averaging over 30 runs are given in Table 1 for $\delta =0$.

Table 1. MST: comparison of the different query strategies (best values in bold).

Running Time and Number of Evaluations. We observe that Random and Max-Dist strategies are much faster than CSS strategy; for instance, for $n=6$ and $|V|=100$, Random and Max-Dist strategies end before one minute whereas CSS needs almost a minute and a half. Note that time is mostly consumed by the generation of extreme points, given that the evaluations are performed by Prim algorithm which is very efficient. Since the number of evaluations with CSS drastically increases with the size of the problem, we may expect the performance gap between CSS and the two other strategies to be much larger for MOCO problems with a less efficient solving method.

Number of Generated Preference Queries. We can see that Max-Dist is the best strategy for minimizing the number of generated preference queries. More precisely, for all instances, the preferred solution is detected with less than 40 queries and the optimality is established after at most 50 queries. In fact, we can reduce even further the number of preference queries by considering a strictly positive tolerance threshold; to give an example, if we set $\delta = 0.1$ (i.e. $10\%$ of the “maximum” error computed using the ideal point and the worst objective vector), then our algorithm combined with Max-Dist strategy generates at most 20 queries in all considered instances. In Table 1, we also observe that CSS strategy generates many more queries than Random, which is quite surprising since CSS strategy is intensively used in incremental elicitation (e.g., [4, 7]). To better understand this result, we have plotted the evolution of minimax regret with respect to the number of queries for the bigger instance of our set ($|V|=100$, $n=6$). We have divided the figure in two parts: the first part is when the number of queries is between 1 and 20 and the other part is when the number of queries is between 20 and 50 (see Fig. 6). In the first figure, we observe that there is almost no difference between the three strategies, and the minimax regret is already close to 0 after only 20 questions (showing that we are very close to the optimum relatively quickly). However, there is a significant difference between the three strategies in the second figure: the minimax regret with CSS starts to reduce less quickly after 30 queries, remaining strictly positive after 50 queries, whereas the optimal solution is found after about 40 queries with the other strategies. Thus, queries generated with CSS gradually becomes less and less informative than those generated by the two other strategies. This can be explained by the following: CSS always selects the minimax regret optimal solution and one of its worst adversary. Therefore, when the minimax regret optimal solution does not change after asking a query, the same solution is used for the next preference query. This can be less informative than asking the DM to compare two solutions for which we have no preference information at all; Random and Max-Dist strategies select the two solutions to compare in a more diverse way.

Fig. 6.

MST problem with $n=6$ and $|V|=100$: evolution of the minimax regret between 1 and 20 queries (left) and between 21 and 50 queries (right).

Comparison with the State-of-the-Art Method. In this subsection, we compare our interactive method with the state-of-the-art method proposed in [2]. The latter consists essentially in integrating incremental elicitation into Prim algorithm [22]; therefore, this method will be called IE-Prim hereafter. The main difference between IE-Prim and IEEP is that IE-Prim is constructive: queries are not asked on complete solutions but on partial solutions (edges of the graph). We have implemented ourselves IE-Prim, using the same programming language and data structures than IEEP, in order to allow a fair comparison between these methods. Although IE-Prim was only proposed and tested with CSS in [2], we have integrated the two other strategies (i.e., Max-Dist and Random) in IE-Prim.

Table 2. MST: comparison between IEEP and IE-Prim (best values in bold).

In Table 2, we compare IEEP with Max-Dist and IE-Prim in terms of running times and number of queries³. We see that IEEP outperforms IE-Prim in all settings, allowing the running time and the number of queries to be divided by three in our biggest instances. Note that Max-Dist and Random strategies improve the performances of IE-Prim (compared to CSS), but it is still not enough to achieve results comparable to IEEP. This shows that asking queries during the construction of the solutions is less informative than asking queries using the extreme points of the polyhedron representing the preference uncertainty.

Now we want to estimate the performances of our algorithm seen as an anytime algorithm (see Fig. 7). For each iteration step i, we compute the error obtained when deciding to return the solution that is optimal for the minimax regret criterion at step i (i.e., after i queries); this error is here expressed in terms of percentage from the optimal solution. For the sake of comparison, we also include the results obtained with IE-Prim. However IE-Prim cannot be seen as an anytime algorithm since it is constructive. Therefore, to vary the number of queries, we used different tolerance thresholds: $\delta =0.3$, 0.2, 0.1, 0.05 and 0.01.

Fig. 7.

MST problem with $|V|=100$: Comparison of the errors with respect to the number of queries for $n=3$ (left) and for $n=6$ (right).

In Fig. 7, we observe that the error drops relatively quickly for both procedures. Note however that the error obtained with IE-Prim is smaller than with IEEP when the number of queries is very low. This may suggest to favor IE-Prim over IEEP whenever the interactions are very limited and time is not an issue.

5.2 Multicriteria Traveling Salesman Problem

We now provide numerical results for the multicriteria traveling salesman problem (MTSP). In our tests, we consider existing Euclidean instances of the MTSP with 50 and 100 cities, and $n=2$ to 6 objectives⁴. Moreover, we use the exact solver Concorde⁵ to perform the optimization part of IEEP algorithm (see procedure Optimizing). Contrary to the MST, there exist no interactive constructive algorithms to solve the MTSP. Therefore, we only provide the results obtained by our algorithm IEEP with the three proposed query generation strategies (namely Random, Max-Dist and CSS). The results obtained by averaging over 30 runs are given in Table 3 for $\delta =0$.

In this table, we see that Max-Dist remains the best strategy for minimizing the number of generated preference queries. Note that the running times are much higher for the MTSP than for the MST (see Table 1), as the traveling salesman problem is much more difficult to solve exactly with known preferences.

Table 3. MTSP: comparison of the different query strategies (best values in bold)

6 Conclusion and Perspectives

In this paper, we have proposed a general method for solving multi-objective combinatorial optimization problems with unknown preference parameters. The method is based on a sharp combination of (1) regret-based incremental preference elicitation and (2) the generation of promising solutions using the extreme points of the polyhedron representing the admissible preference parameters; several query generation strategies have been proposed in order to improve its performances. We have shown that our method returns the optimal solution according to the DM’s preferences. Our method has been tested on the multicriteria spanning tree and multicriteria traveling salesman problems until 6 criteria and 100 vertices. We have provided numerical results showing that our method achieves better results than IE-Prim (the state-of-the-art method for the MST problem) both in terms of number of preference queries and running times.

Thus, in practice, our algorithm outperforms IE-Prim which is an algorithm that runs in polynomial time and generates no more than a polynomial number of queries. However, our algorithm does not have these performance guarantees. More precisely, the performances of our interactive method strongly depend on the number of extreme points at each iteration step, which can be exponential in the number of criteria (see e.g., [26]). Therefore, the next step could be to identify an approximate representation of the polyhedron which guarantees that the number of extreme points is always polynomial, while still being able to determine a (near-)optimal solution according to the DM’s preferences.