Dominance Rules for the Choquet Integral in Multiobjective Dynamic Programming

1 Introduction

Decision making in multiobjective combinatorial problems is one of the main issues investigated in algorithmic decision theory. It concerns decision problems in which the value of a solution is assessed with respect to several viewpoints, possibly conflicting each others (e.g. costs and benefits in a multicriteria decision making problem, individual utility functions in collective decision making, scenarios in optimization under uncertainty). In these different contexts, decision theory proposes various preference models enabling to compare feasible tradeoffs and to determine the best alternatives [Keeney and Raiffa, 1993; Bouyssou et al., 2009; Grabisch et al., 2009; Gilboa, 2009; Moulin, 1988; Domshlak et al., 2011].

∗This research was supported by the project ANR-09-BLAN0361 "GUaranteed Efficiency for PAReto optimal solutions Determination (GUEPARD)".

Such models can be used either for supporting human decision making (e.g. scientific management in organizations, recommender systems and e-commerce, preferencebased configuration) or to produce intelligent systems with autonomous decision capabilities (e.g. route planning systems, robot motion planning, resource allocation, network optimization). These various applications are a permanent incentive to revisit standard discrete optimization problems in terms of optimizing multiple objectives.

Despite the diversity of models proposed in decision theory to describe or simulate different decision behaviors, the great majority of algorithmic contributions in discrete multicriteria optimization focuses on the Pareto-dominance model and the computational effort is directed towards the determination of the whole set of Pareto-optimal tradeoffs (i.e. feasible tradeoffs that cannot be improved on one component without being weakened on another one) [Stewart and White III, 1991; Mandow and P´erez de la Cruz, 2005; Ehrgott and Gandibleux, 2000]. All these solutions can be seen as possible optima with respect to some Pareto-monotonic preference model. Unfortunately, in combinatorial domains the size of the Pareto set may grow exponentially with the size of the problem, even with only two criteria. Hence, its exact computation may require prohibitive computation times. Moreover there is generally no need to consider explicitly all possible tradeoffs, some of them being more or less equivalent, and some other being too far from the target or the aspirations of the Decision Maker.

One way out these problems is to determine an approximation of the Pareto set with performance guarantees [Papadimitriou and Yannakakis, 2000; Perny and Spanjaard, 2008; Marinescu, 2011]. Alternatively, when preference information is available, one can use a decision model to guide the search and determine the preferred tradeoff without a prior generation of the Pareto set. A typical example is given in [Carraway et al., 1990; Dasgupta et al., 1995] where the state space search is directed by a multiattribute utility function. Other examples can be found in [Ehrgott, 2000]. This is the path we follow in this paper dedicated to the use of the Choquet integral in multiobjective Dynamic Programming.

The Choquet integral, initially introduced in the context of Decision under Uncertainty [Schmeidler, 1986] is also one of the most general and flexible aggregators used in multicriteria analysis [Grabisch and Labreuche, 2010]. It includes many other aggregators as special cases, e.g. weighted means, min, max, median, OWA [Yager, 1998] and WOWA [Torra, 1997]. Roughly speaking, the Choquet integral is a weighted combination of scores derived from subsets of criterion values. It involves one weighting coefficient per subset of criteria, thus enabling a fine control of preferences. It makes it possible to take into account positive or negative interactions among criteria and to model complex synergies in the aggregation. This aggregator has been used in several discrete optimization problems addressed in AI like constraint programming [Le Hu´ed´e et al., 2006], state space search [Galand and Perny, 2007]. Following this line, our aim in this paper is to introduce a general preference-based search technique based on Multiobjective Dynamic Programming (MODP) to determine Choquet optimal solutions in discrete multicriteria optimization problems. As will be seen later, the main deadlock to overcome is that preferences induced by a Choquet integral do not satisfy the Bellman principle. Hence the application of usual dynamic programming concepts [Bellman, 1957] during the search is no longer possible; in particular, preferences induced by the Choquet model cannot be directly used for local pruning of sub-solutions during the search.

The first objective of this paper is to propose a general family of dominance rules, stronger than standard filters based on Pareto-dominance, enabling a local pruning during the search of the Choquet optimal solutions while preserving admissibility. The second objective is to integrate these rules in a MODP scheme and to assess the value of the resulting procedure. The paper is organized as follows: Section 2 presents preliminary definitions and the Choquet integral model. Section 3 presents MODP concepts and the violation of Bellman principle by Choquet integrals. In Section 4 we introduce a general family of dominance rules and establish some technical results providing guidelines to find the most efficient dominance rules in the family. Section 5 proposes an algorithm implementing dominance rules within a MODP scheme and presents numerical tests performed on random instances of multiobjective binary Knapsack problem.

2 The Choquet Integral Model

We first recall some standard definitions linked to setfunctions and capacities, a classical tool to model the importance of coalitions within a set N = {1, . . . , n} of criteria.

Definition 1 A set-function is any mapping v : 2N → R. A capacity is a set-function v such that v(∅) = 0, v(N) = 1 , and v(A) ≤ v(B) whenever A ⊆ B (monotonicity).

Definition 2 A set-function v is said to be convex or supermodular when v(A ∪ B) + v(A ∩ B) ≥ v(A) + v(B) for all A,B ⊆ N, additive when v(A ∪ B) + v(A ∩ B) = v(A) + v(B) for all A,B ⊆ N, and concave or submodular when v(A ∪ B) + v(A ∩ B) ≤ v(A) + v(B) for all A, B ⊆ N.

Definition 3 The dual ¯ v of a set-function v is a set-function defined by ¯ v(A) = v(N) - v(N\A) for all A ⊆ N.

Now we can introduce formally the Choquet integral [Schmeidler, 1986]. The Choquet integral of a utility vector x ∈ Rn with respect to capacity v is defined by:

where (.) denotes a permutation of (1, . . . , n) such that x(i) ≤ x(i+1) for all i = 1, . . . , n - 1 and X(i) = {j ∈ N, xj ≥ x(i)} is the subset of indices corresponding to the n + 1 - i largest components of x. Assume x and y are two performance vectors of Rn , x is preferred or indifferent to y according to the Choquet model when Cv(x) ≥ Cv(y).

Assume we want to compare two performance vectors x = (10, 6, 14) and y = (10, 12, 8) using capacity v, we have:

With Cv we observe that y is preferred to x.

In the definition of Cv, the use of a capacity v instead of an arbitrary set-function enforces compatibility with Paretodominance due to the monotonicity of v with respect to set inclusion. Hence Cv(x) ≥ Cv(y) whenever x Paretodominates y, i.e. xi ≥ yi for all i ∈ N and xj > yj for some j ∈ N. More generally Cv can be defined for any setfunction v. Function Cv is known to be convex whenever v is concave (submodular). Conversely, Cv is concave whenever v is convex (supermodular) [Lov´asz, 1983]. The concavity of Cv and therefore the use of a convex capacity in a Choquet integral has an interpretation in terms of preferences (see [Chateauneuf and Tallon, 1999]). Indeed, it is shown that if v is convex, then ∀x1 , x2 , . . . xp ∈ Rn , ∀k ∈ {1, 2, . . . , p} and ∀i ∈ {1, 2, . . . , p}, λi ≥ 0 such that ∑pi=1 λi = 1 we have:

For example, when using a convex capacity, if one is indifferent between utility vectors (0, 100) and (100, 0), one will prefer solution (50, 50), which corresponds to the average of the two vectors, than any of the two initial vectors. Obviously, we would obtain reverse preferences with a concave capacity since the associate Choquet integral is convex. Capacity v may both be concave and convex (i.e. it is additive) and in this case the Choquet integral boils down to a weighted sum. Alternatively, v could be neither convex nor concave to model more complex preferences (for more details see [Grabisch et al., 2009]).

Any set-function v admits an alternative representation in terms of the M¨obius inverse:

Definition 4 To any set-function v : 2N → R is associated m : 2N → R a mapping called M¨obius inverse, defined by:

v can be reconstructed from its M¨obius inverse as follows:

Coefficients m(B) for B ⊆ A are called M¨obius masses. Interestingly, a set-function whose M¨obius masses are nonnegative (a.k.a belief function) is necessarily convex [Shafer, 1976]. Using the M¨obius inverse, we can define the notion of k-additive capacities as follows [Grabisch et al., 2009]:

Definition 5 A capacity is said to be k-additive when its M¨obius inverse vanishes for any A ⊆ N such that |A| > k, and there exists at least one subset A of exactly k elements such that m(A) ̸= 0. More formally:

If k = 1 we get an additive capacity. k-additive capacities for small values of k greater than 1 are very useful because in practical situations, they offer a sufficient expressivity to model positive or negative interactions among criteria with a reduced number of parameters. For example, when k = 2 the capacity is completely characterized by (n2 + n)/2 coefficients.We conclude this section by mentioning two properties that will be useful in the paper:

3 Preference-based Dynamic Programming

For the sake of generality, we introduce an algebraic version of dynamic programming encompassing in the same formalism several preference systems including, among others, the standard one (maximization of an additive reward function) used in standard dynamic programming (DP) but also the multiobjective extension (determination of Pareto optimal reward vectors) used in MODP. We will then show how the Choquet integral model departs from this general framework.

Preference-based DP is a state space search method extending standard DP to handle complex preferences in sequential decision problems. It applies, with some restrictions on preferences that will be discussed later, to discrete optimization problems in which feasible solutions can be seen as the result of a sequence of p elementary decisions. For any decision step k ∈ {1, . . . , p}, let Sk be the (finite) set of possible states and Ak the (finite) set of possible actions. We consider also Sp+1 the (finite) set of final states, accessible after p decision steps. We assume here, without loss of generality, that S1 contains a single state s1 (initial state). At step k, a transition function fk gives the state sk+1 = fk(sk, ak) obtained when action ak is chosen in state sk. Let dk : Sk →Ak denote the decision function that assigns to any state sk ∈ Sk an action ak = dk(sk) ∈ Ak(sk) ⊆ Ak where Ak(sk) is the set of admissible actions in state sk. Then we define a policy as any sequence π = (d1, . . . , dp).

Let Rk(sk, ak) be the reward generated by action ak in state sk. We assume that R(sk, ak) ∈ V where V is an abstract valuation scale endowed with two operators ⊗ and ⊕.

Operator ⊗ is an associative operation used to cumulate rewards over the time (typically ⊗ = +). It admits a neutral element denoted 1 and an absorbing element denoted 0 thus making (V,⊗, 1) a monoid. Operation ⊕ is assumed to be commutative, associative and indempotent (x ⊕ x = x), admitting 0 as neutral element, thus making (V,⊕, 0) a commutative monoid. It is used as a preference-based selection operation (typically ⊗ = max or ⊗ = min). The correspondence between ⊕ and a preference relation ≿ defined on V is established as follows

In this algebraic setting, we want to determine a policy π = (d1, . . . , dp) such that V (π) = ⊗pk=1 R(sk, dk(sk)) is optimal. Optimality of π means here that V (π) ≿ V (π′ ) for any other feasible policy π′ where ≿ is defined by (5).

Last but not least, we assume that ⊗ is distributive over ⊕: (x⊕y)⊗z = (x⊗z)⊕(y⊗z) and z⊗(x⊕y) = (z⊗x)⊕(z⊗y). These algebraic properties make (V,⊕,⊗, 0, 1) a semiring, a standard valuation structure for DP in algebraic path problems [Gondran and Minoux, 1984]. Distributivity indeed enforces the Bellman principle (subpaths of optimal paths are themselves optimal) and justifies local pruning based on preferences during the search. Consider indeed two reward vectors x and y associated to two partial solutions σx and σy available in a given state sk (corresponding to two possible sequences of actions from the initial state). Then the first part of the distributivity condition tells that we can soundly discard σy and keep σx whenever x ⊕ y = x because any extension of σy with cost z is beaten by the same extension of σx, since (x ⊗ z) ⊕ (y ⊗ z) = (x ⊕ y) ⊗ z = x ⊗ z. The other part of distributivity ensures a similar property when policies are generated backward from terminal states to the initial states. Note also that, by Equation (5), we observe that distributivity entails the monotonicity of preferences w.r.t. ⊗:

Interestingly enough, this property is the key axiom used in utility-based MODP introduced in [Carraway et al., 1990]. We remark that the semiring structure also appears naturally in the standard context of DP and in MODP as well:

Example 2 (Valuation system in standard DP) The valuation system used in standard DP for scalar reward maximization is (V, ⊕, ⊗, 0, 1) = (R∪ {-∞}, max, +, -∞, 0) which is a semiring [Gondran and Minoux, 1984]. The preference associated to max through (5) is the natural order ≥ on R.

Example 3 (Valuation system inMODP) In a multiobjective setting there might be several Pareto-optimal policies to reach a given state sk from the initial state. Hence a set of reward vectors must be assigned to any state sk, corresponding to all distinct reward vectors of Pareto-optimal sub-policies leading to sk. The valuation system used in MODP is based on the following algebraic structure (V, ⊕, ⊗, 0, 1):

• V = {X ⊂ Rn : ND(X) = X} \ ∅ where ND(X) is the set of Pareto-optimal elements in X,
• ∀X, Y ∈ V, X ⊕ Y = ND(X ∪ Y )
• ∀X, Y ∈ V, X ⊗ Y = ND({x + y : x ∈ X, y ∈ Y })
• 0 = {(-∞, . . . ,-∞)} and 1 = {(0, . . . , 0)} This is a

semiring [Gondran and Minoux, 1984; Perny et al., 2005]. Here, the preference associated to ⊕ through (5) is the Pareto-dominance over vectors, extended to sets of vectors.

The theory of algebraic path problems [Gondran and Minoux, 1984; 2008] tells that the problem can be solved by Algorithm 1 given below, provided that (V,⊕,⊗, 1, 0) is a semiring. In particular it is admissible for MODP. Algorithm 1 implemented with the operations defined in Example 3 computes the sets of Pareto-optimal reward vectors Vk(sk) in every state sk. At the end, V1(s1) provides the set of Pareto-optimal tradeoffs associated to optimal policies. In this process, the evaluation of policies at any states is essentially similar to what is done for shortest path problems in MOA∗ algorithm [Stewart and White III, 1991]. The optimal actions and therefore the optimal policies can be recovered at every state by standard bookkeeping techniques.

Algorithm 1: Algebraic Dynamic Programming

Input: transition functions fk, reward functions Rk 1 Output: optimal policy for all sp+1 ∈ Sp+1 do Vp+1(sp+1) ← 1 for k = p downto 1 do 2 for all sk ∈ Sk do 3 Vk(sk) ← ⊕ ak∈Ak(sk) {Rk(sk, ak) ⊗ Vk+1(fk(sk, ak))} 4 end 5 end 6

Unfortunately, despite its generality, this algorithm does not fit to any preference system. In particular, it does not work for preferences induced by a Choquet integral in a multiobjective problem. Indeed, starting with Example 3 we have to redefine ⊕ as X⊕Y = argmax{Cv(z), z ∈ X∪Y } to model choices induced by the Choquet model. Unfortunately this new ⊕ is not distributive over ⊗. As a consequence the preference ≿ defined by Equation (5) is not monotonic. For example consider x = (7, 7, 12), y = (14, 10, 6) and the capacity v of Example 1. We have Cv(x) = 9.5 > 8.8 = Cv(y). Yet if z = (0, 4, 8), we obtain Cv(x + z) = 13.5 < 14 = Cv(y+z). The convenient semiring structure is lost here and Algorithm 1 is no longer admissible for preferences induced by the Choquet integral. To overcome the problem, we need a generalized DP algorithm as suggested in [Carraway et al., 1990] so as to discard partial solutions if they cannot lead to an optimal solution. This can be achieved by determining a dominance relation ≻d so as to restore the following weak monotonicity condition: x ≻d y ⇒ x ⊗ z ≻c y ⊗ z for all z, where ≻c is the strict preference induced by the Choquet integral. The challenge is to find some relations ≻d providing stronger pruning possibilities than Pareto-dominance. This is the aim of the next section.

4 Dominance Rules for Choquet-optimization

We present now a family of dominance rules which enables to detect some sub-solutions that can not lead to Choquetoptimal solutions, without any restriction on the capacity.

4.1 A Family of Dominance Rules

The dominance rules we consider for Choquet-optimization are based on decompositions of the capacity into a difference of set-functions. We establish a preliminary lemma and a proposition concerning such decompositions before formulating a general dominance rule:

Lemma 1 For any convex set-function v, Cv(x) - Cv(y) ≥ Cv(x - y) holds for any x, y ∈ Rn .

Proof. If v is convex then Cv is concave. Thus for any z, y ∈ Rn , Cv(z/2 + y/2) ≥ Cv(z)/2 + Cv(y)/2, i.e. 2Cv(z/2+y/2) ≥ Cv(z)+Cv(y). By Equation (3) we have 2Cv(z/2 + y/2) = Cv(z + y) ≥ Cv(z) + Cv(y). By setting x = z + y, we obtain Cv(x) ≥ Cv(x- y) +Cv(y). □

Proposition 1 For any decomposition of a capacity v into a difference of convex set-functions v1 and v2 (v = v1 - v2), and for any x, y ∈ Rn , we have:

Proof. Since v = v1 - v2, we have Cv(y) - Cv(x) = (Cv1 (y) - Cv1 (x)) + (Cv2 (x) - Cv2 (y)) by Equation (4). From Lemma 1, we know that (Cv1 (y)-Cv1 (x))+(Cv2 (x)- Cv2 (y)) ≥ Cv1 (y - x) + Cv2 (x - y) (since v1 and v2 are convex). Therefore if Cv1 (y - x) + Cv2 (x - y) > 0 we have Cv(y) - Cv(x) > 0. □

This result leads to a dominance rule for Choquetoptimization which enables local pruning during the search.

Proposition 2 (General Dominance Rule GDR) Let x, y ∈ Rn be two reward vectors attached to the same state sk and associated with two partial solutions σx, σy respectively. Let v1 and v2 be two convex set-functions such that v = v1 - v2. If Cv1 (y - x) +Cv2 (x - y) > 0 then any further extension of σx will be beaten by the same extension of σy and x can be discarded in the search for a Choquet-optimal solution.

Proof. Consider σx and σy two sub-solutions, and x, y ∈ Rn their reward vectors, such that Cv1 (y-x)+Cv2 (x-y) > 0. For any reward vector z ∈ Rn , we still have Cv1 ((y + z) - (x + z)) + Cv2 ((x + z) - (y + z)) > 0. Since v1 and v2 are convex, Proposition 1 holds and we get Cv(x + z) < Cv(y + z). □

Let ≻d be the preference relation defined by: y ≻d x iff Cv1 (y - x) + Cv2 (x - y) > 0 for a given decomposition of type v = v1 - v2 with v1, v2 convex. If a vector x ∈ V (sk) is ≻d-dominated (i.e. there exists y ∈ V (sk) such that y ≻d x) then x cannot lead to a Cv-optimal solution. Therefore, we may use GDR in Algorithm 1 (implemented with the valuation system introduced in Example 3) after Line 4 to discard any vector ≻d-dominated in V (sk). Remark that GDR assumes that v is decomposable as a difference of two convex set-functions. The following proposition shows that such a decomposition is always possible:

Proposition 3 Any capacity v can be decomposed as the difference of two convex set-functions.

Proof. Let m be the M¨obius masses of v. We define m+(B) = max{m(B), 0} and m-(B) = max{-m(B), 0}, such that m(B) = m+(B) - m-(B), for any B ⊆ N. Let v+ and v- be two set-functions such that v+(A) = ∑B⊆A m+(B) and v-(A) = ∑B⊆A m-(B). By construction, the M¨obius masses of these two set functions v+ and v- are positive, which means that these two set functions are convex. Furthermore, for any A ⊆ N, v(A) = ∑B⊆A (m+(B) -m-(B)) = v+(A) - v-(A) which concludes the proof. □

Hence there exists at least one decomposition of v to implement GDR. The instance of GDR based on the decomposition v = v+ - v- introduced in Proposition 3 is denoted DR1 hereafter. It is logically equivalent to the rule introduced in [Fouchal et al., 2011] involving M¨obius masses. The test using our formulation is computationally more efficient because it is performed in O(nlogn) whereas the test using M¨obius masses requires O(2n ) operations where n is the number of criteria. Obviously, many other decompositions are possible. For example, we know due to Proposition 3 that the dual of v can be decomposed as ¯ v = ¯ v+ - ¯ v- where ¯ v+ and ¯ vare convex. We set w+ = -¯ v- and w- = -¯ v+. Since ¯ v+ and ¯ v- are convex, their dual are concave, and w+ and ware convex. The following proposition shows that those two set-functions form a convenient decomposition of v:

Proposition 4 Set-functions w+ and w- defined above are such that v = w+ - w-

Proof. Let ¯m+ and ¯m- be the M¨obius inverse of ¯ v+ and ¯ v- respectively. By definition, for any A ⊆ N, we have w+(A) = ¯ v-( ¯ A) - ¯ v-(N) = - ∑B⊆N:B∩A̸=∅ ¯m-(B) and w-(A) = ¯ v+( ¯ A) - ¯ v+(N) = - ∑B⊆N:B∩A̸=∅ ¯m+(B). Furthermore, we also have v(A) = 1 - ¯ v( ¯ A) = 1 - ∑B⊆ ¯ A ¯m(B) = ∑B⊆N:B∩A̸=∅ ¯m(B) = ∑B⊆N:B∩A̸=∅ [ ¯m+(B) - ¯m-(B)] = w+(A) - w-(A) which concludes the proof. □

This second decomposition of v leads to a second instance of GDR denoted DR2 which can be used to prune extra sub-paths. Let us illustrate the complementarity of DR1 and DR2 on capacity v of Example 1 with the following decompositions:

Consider two vectors x = (1, 5, 7) and y = (6, 6, 6). We have Cv+(y - x) + Cv-(x - y) = 0.2 > 0 and x can be discarded, while Cw+(y - x) + Cw-(x - y) = -0.2 ≤ 0. Hence DR1 is active but not DR2. One could check that this is exactly the reverse for decompositions of ¯ v.

4.2 Optimality of a Decomposition

Proposition 3 shows that there always exists a decomposition v+ - v-. Besides, for any convex set-function v3, setfunctions v+ + v3 and v- + v3 are convex and form another valid decomposition for v. Hence the number of possible decompositions is infinite. In this subsection, we address the question of the existence of an optimal decomposition, in the sense that the resulting dominance rule based on Proposition 2 has stronger discarding possibilities. More precisely, a decomposition v = v1 - v2 with vi convex is said to be optimal if, for any other decomposition v = v′1 - v′2 with v′i convex, and for any x, y ∈ Rn , we have Cv1 (y - x) + Cv2 (x - y) ≥ Cv′1 (y - x) + Cv′2 (x - y). We discuss now optimal decompositions for various categories of capacities.

Convex or Concave Capacities

In order to provide an optimal decomposition for the case of a convex v, we need to prove the following lemma:

Lemma 2 For any convex set-function v, and any x, y ∈ Rn , we have Cv(y - x) + Cv(x - y) ≤ 0.

Proof. Since v is convex, we have (Lemma 1) for any x, y ∈ Rn , Cv(y - x) ≤ Cv(y) - Cv(x) and Cv(x - y) ≤ Cv(x) - Cv(y). By adding this two inequalities we obtain Cv(y-x)+ Cv(x - y) ≤ 0. □

If v0 denotes the set-function which is everywhere 0, then we can now prove that the decomposition v1 = v and v2 = v0 is optimal when the capacity is convex:

Proposition 5 When v is convex, then for any decomposition v = v1 - v2 with v1 and v2 convex, and any x, y ∈ Rn , we have Cv1 (y - x) + Cv2 (x - y) ≤ Cv (y - x).

Proof. We have v1 = v + v2. Moreover, we have Cv1 (y-x)+Cv2 (x-y) = Cv (y-x)+Cv2 (y-x)+Cv2 (x-y) by Equation (4). Set-function v2 is convex, so by Lemma 2 we have Cv2 (y - x) + Cv2 (x - y) ≤ 0. Combining these two results yields Cv1 (y - x) + Cv2 (x - y) ≤ Cv (y - x). □

Since the decomposition v = v - v0 leads to test if Cv(y - x) > 0, Proposition 5 shows that any other test of type Cv1 (y - x) + Cv2 (x - y) > 0 cannot succeed when Cv(y - x) > 0 fails, thus establishing the optimality of the test Cv(y - x) > 0 for convex capacities. Similarly, we can show that when v is concave, decomposition v = v0 - (-v) is optimal.

2-additive Capacities

When v is 2-additive, the decomposition of Proposition 3 is optimal as shown in the following:

Proposition 6 If v is 2-additive, for any decomposition v = v1-v2 of v, and for any x, y ∈ Rn , Cv1 (y-x)+Cv2 (x-y) ≤ Cv+ (y - x) + Cv- (x - y).

Proof. Let v′ be a set-function such that v′ = v1 - v+. We have v1 = v+ + v′ , v2 = v1 - v = v+ + v′ - v = v- + v′ , and so Cv1 (y - x) + Cv2 (x - y) = Cv+(y - x) + Cv-(x - y) + Cv′(y - x) + Cv′(x - y). If we suppose that v′ is convex, we get from Lemma 2 Cv′ (y-x)+Cv′ (x-y) ≤ 0 for any x, y ∈ Rn . It would mean that Cv1 (y - x) + Cv2 (x - y) ≤ Cv+ (y - x) + Cv- (x - y). So in order to conclude the proof, we only need to show that v′ is convex. Let m, m+, m-, m1, m2 and m′ be the respective M¨obius masses of v, v+, v-, v1, v2 and v′ . Chateauneuf and Jaffray [1989] have shown that v′ is convex if and only if for any {i, j} ⊆ N and any A ⊆ N\{i, j}, ∑B⊆A m′ ({i, j} ∪B) ≥ 0. Capacity v2 is convex, so we have 0 ≤ ∑B⊆A m2({i, j} ∪B) =

∑B⊆A m-({i, j} ∪B) + ∑B⊆A m′ ({i, j} ∪B). By construction if m({i, j}) ≥ 0, for any B ⊆ A, m-({i, j} ∪ B) = 0 since v is 2-additive, so we get 0 ≤ ∑B⊆A m′ ({i, j} ∪B). Capacity v1 is also convex, so we have 0 ≤ ∑B⊆A m1({i, j} ∪B) = ∑B⊆A m+({i, j} ∪B) + ∑B⊆A m′ ({i, j} ∪B). By construction if m({i, j}) < 0, for any B ⊆ A, m+({i, j} ∪ B) = 0 since v is 2-additive, and as a consequence we get 0 ≤ ∑B⊆A m′ ({i, j} ∪B) in any cases, which concludes the proof since v′ is convex. □

To our knowledge, finding the optimal decomposition for 3-additive capacities or more remains an open problem.

5 Application toMultiobjective Knapsack

The Knapsack problem is a standard NP-hard problem appearing each time a Decision Maker has to perform a selection of items within a set {1, . . . , p}, under a resource constraint. Its multiobjective version consists in maximizing quantities xi = ∑pk=1 uik ak under a budget constraint ∑pk=1 wkak ≤ W, where wk are positive weights, uik represents the utility of item k w.r.t. criterion i and ak is a boolean corresponding to possible actions (selection of object k or not). We present here an application of our work to maximize Cv(x1, . . . , xn) where xi's are defined as above. In order to recast the problem in the MODP framework introduced in Section 3 we define Ak = {0, 1}, S1 = {0} and Sk = {0, . . . ,W}, the possible actions and states for k = 2 to p + 1. Then the transition function at step k is given by fk(sk, ak) = sk +wkak (it gives the total weight of the selection after the k first decisions). The reward function is characterized by Rk(sk, ak) = (u1k ak, . . . , unk ak).

To solve this problem, we have implemented Algorithm 1 (with the valuation system introduced in Example 3 as explained in Section 3) modified by insertion of dominance rules DR1 and/or DR2 after Line 4. This enables to discard any ≻d-dominated vector in Vk(sk). Such dominance rules enable to decrease the number of vectors yielding to suboptimal paths (w.r.t. the Choquet integral) during the search, but the computation of these rules could be time consuming since each Choquet evaluation requires to sort the components of the vectors. We use the knapsack problem to study the impact of using DR1 (or DR2) compared to using only Pareto-dominance (DR0).

The experiments were performed in C++ on an Intel Xeon 2.27Ghz with 10Gb RAM. Utilities and weights of items are randomly drawn between 1 and 100. The capacity of the knapsack W is set to 50% of ∑k wk. Our experiments use different randomly drawn Choquet capacities v. We first present the results obtained for a concave capacity defined for any A ⊆ N by v(A) = √∑i∈A pi where pi's are coefficients randomly drawn in [0, 1], adding up to 1. Table 1 summarizes the average execution time (in seconds) over 20 random instances of knapsack (first row), and the number of thousands of sub-solutions generated (second row) for different number of items and objectives. We have tested the same variants DR0, DR1 or DR2. For this concave capacity, DR2

is always better than DR1. To save space, we thus only report the results of DR2 compared to DR0.

These results show that applying DR2 in a MODP procedure enables to significantly reduce the number of subsolutions generated. Consider for example the case of 30 items and 8 objectives where 91,000 sub-solutions are generated with DR2 instead of more than 1,3 million with DR0. Moreover DR2 is clearly faster than DR0 with this capacity.

In order to assess the impact of the convexity or concavity of v, we performed numerical experiments with a family of capacities generated from M¨obius masses as follows: given a number α ∈ [-1, 1], m({i}) = (α + 1)/n, m({i, j}) = -2α/n(n - 1), and m(A) = 0 for all A such that |A| > 2. Hence, if α < 0 then v is convex, if α > 0 then v is concave, and if α = 0 then v is additive. In Figure 1, we report the results obtained by varying α from -1 to 1 for a knapsack with 50 items and 3 objectives. The figure indicates the average execution time (top chart) and the average number of sub-solutions generated (bottom chart) with DR0, DR1, DR2 over 20 random instances. One can observe that DR1 and DR2 are similar and really faster than DR0 (horizontal top line), except for extreme values of α. Moreover DR1 and DR2 enable to significantly reduce the number of generated sub-solutions, even for extreme values of α. The efficiency of DR1 and DR2 increases as we get closer to linearity (i.e. when α tends to 0). Finally, we observe that when α is lower than 0, the Choquet integral is convex. To our knowledge, this is one of the very first methods able to determine a Choquetoptimal knapsack when the Choquet integral is convex (in maximization) without determining the entire Pareto set.