Multiobjective Optimization using GAI Models

1 Introduction

The complexity of human decision making in organizations, the importance of the issues raised in decision problems and the increasing need to explain or justify any decision has led decision makers to seek a scientific support in the preparation of their decisions. During many years, rational decision making was understood as solving a single-objective optimization problem, the optimal decision being implicitly defined as a feasible solution minimizing a cost function under some technical constraints. However, the practice of decision making in organizations has shown the limits of such formulations. First, there is some diversity and subjectivity in human preferences that requires distinguishing between the objective description of the alternatives of a choice problem and their value as perceived by individuals. In decision theory, alternatives are often seen as multiattribute items characterized by a tuple in a product set of attributes domains, the value system of each individual being encoded by a utility function defined on the multiattribute space and measuring the relative attractiveness of each tuple. Hence objectives of individuals take the form of multiattribute utilities to be optimized. Typically, in a multiagent decision problem, we have to deal with several such utilities that must be optimized simultaneously. Since individual utilities are generally not commensurate, this is not always possible to construct an overall utility that might simplify the optimization task and we have to solve a multiobjective problem. Moreover, even when there is a single decision maker, several conflicting points of views may be considered in the preference analysis, leading to the definition of several criteria. All these observations have motivated the emergence of multicriteria methodologies for preference modeling and human decision support, an entire stream of research that steadily developed for 40 years [Keeney and Raiffa, 1993].

In human decision problems, alternatives are often characterized by a combination of local decisions providing the feasible set with a combinatorial structure. This explains the growing interest for multiobjective combinatorial optimization [Ehrgott, 1999], with applications in various contexts such as planning actions of autonomous agents, organizing production workflows, solving resource allocation problems. Besides the existence of several criteria, the combinatorial nature of multiattribute spaces is a significant source of complexity. This has motivated the development of preference representation languages aiming at simplifying preference handling and decision making on combinatorial domains.

As far as utility functions are concerned, the works on compact representation aim at exploiting preference independence among some attributes so as to decompose the utility of a tuple into a sum of smaller utility factors. Different decomposition models of utilities have been developed to model preferences. The most widely used assumes a special kind of independence among attributes called "mutual preferential independence". It ensures that preferences are representable by an additively decomposable utility [Krantz et al., 1971; Bacchus and Grove, 1995]. Such decomposability makes both the elicitation process and the query optimizations very fast and simple. However, in practice, it may fail to hold as it rules out any interaction among attributes. Generalizations have thus been proposed in the literature to significantly increase the descriptive power of additive utilities. Among them, multilinear utilities [Keeney and Raiffa, 1993] and GAI (generalized additive independence) decompositions [Braziunas and Boutilier, 2005; Gonzales and Perny, 2004] allow quite general interactions between attributes [Bacchus and Grove, 1995] while preserving some decomposability. The latter has been used to endow CP-nets with utilities (UCPnets) [Boutilier et al., 2001; Brafman et al., 2004]. GAI decomposable utilities can be compiled into graphical structures closely related to junction trees, the so-called GAI networks. They can be exploited to perform classical optimization tasks (e.g. find a tuple with maximal utility) using a simple collect/distribute scheme essentially similar to that used in the Bayes net community. The next step is to address multiobjective optimization problems with such graphical models.

The aim of this paper is to show the potential of GAI models in representing and solving multiobjective combinatorial optimization problems. Assuming each objective is represented by a GAI decomposable utility function defined on the multiattribute space, we investigate the determination of Pareto-optimal elements. More precisely, in Section 2, we introduce exact and approximated optimality concepts linked to the notion of Pareto dominance. In Section 3, we show how both exact and approximated Pareto sets can be determined efficiently using GAI nets. Finally, in Section 4, we present numerical experimentations showing the impact of decomposition and approximation on solution times.

2 Non-dominated Solutions and their Approximation

We assume that alternatives are characterized by n variables x1 , . . . , xn taking their values in finite domains X1 , . . . , Xn respectively. Hence alternatives can be seen as elements of the product set of these domains X = X1 × . . . ×Xn. By abuse of notation, for any set Y ⊆ {1, ..., n}, xY will refer to the projection of x ∈ X on ∏i∈Y Xi. Considering a finite set of objectives M = {1, ...,m}, any solution x ∈ X can be characterized by a utility vector (u1 (x), ..., um(x)) ∈ Zm+ where ui : X → Z+ is the ith utility function. It measures the relative utility of alternatives with respect to the ith point of view (criterion or agent) considered in the problem. Hence, the comparison of alternatives reduces to that of their utility vectors. The set of all utility vectors attached to solutions in X is denoted by U. We recall now some definitions related to dominance and optimality in multiobjective optimization.

Definition 1 The weak Pareto dominance relation is defined on utility vectors of Zm+ as: u ≿P v ⇔ [∀i ∈ M, ui ≥ vi ].

Definition 2 Any utility vector u ∈ U is said to be nondominated in U (or Pareto-optimal) if, for all v ∈ U, v ≿P u ⇒ u ≿P v. The set of non-dominated vectors in U is denoted ND(U) and is referred to as the "Pareto set".

The Pareto set can be very large as U is the image of a combinatorial set X in Zm+ and, in the worst case, all elements in U are non-dominated as shown by the following example:

Example 1 Consider a decision problem with two objectives on a set X = ∏nk=1 Xk, where Xk = {0, 1}, k = 1, . . . , n. Assume the objectives are additive utility functions defined, for any Boolean vector x = (x1 , . . . , xn) ∈ X, by ui (x) = ∑nk=1 uik (xk), i = 1, 2, where uik is a marginal utility function defined on Xk by u1k (xk) = 2k-1xk and u2k (xk) = 2k-1 (1 - xk). Then for all x ∈ {0, 1}n , u1 (x) = ∑nk=1 2k-1xk and u2 (x) = ∑nk=1 2k-1 (1 - xk) and therefore u1 (x) + u2 (x) = ∑nk=1 2k-1 = 2n - 1. So there exist 2n different Boolean vectors in X with distinct images in the utility space. Actually, all feasible utility vectors of type (u1 , u2) ∈ U are on the same line characterized by equation u1 + u2 = 2n - 1. This line is orthogonal to vector (1, 1) which proves that all these vectors are Pareto-optimal. Here ND(U) = U. In such a case, the size of the Pareto set grows exponentially with the number of attributes.

Although pathological, this example shows that the determination of Pareto-optimal vectors may be intractable in practice on large size instances. Numerical tests presented in Section 4 will confirm this point. For this reason, relaxing the notion of Pareto dominance to approximate the Pareto set with performance guarantee is a good alternative in practice. In this perspective, we consider the notion of ε-dominance defined as follows [Papadimitriou and Yannakakis, 2000; Laumanns et al., 2002; Perny and Spanjaard, 2008]:

Definition 3 For any ε > 0, the ε-dominance relation is defined on utility vectors of Zm+ as follows:

For instance, on the left part of Fig. 1, the black point in cone C ε-dominates any other point in the cone. Hence we can define the notion of approximation of the Pareto set as follows:

Definition 4 For any ε > 0 and any set V ⊆ U of bounded utility vectors, a subset W ⊆ V is said to be an ε-covering of ND(V) if ∀v ∈ ND(V), ∃w ∈ W : w ≿ε v.

In general, multiple ε-coverings of ND(V) exist, with different sizes, the most interesting being minimal w.r.t. set inclusion. For instance, on the left part of Fig. 1, the gray and the four black points form an ε-covering of the Pareto set since the union of cones A,B,C,D,E covers all feasible utility vectors. But the five points do not form a minimal covering since, excluding the gray point, the four remaining points still cover the entire feasible set as can be seen on Fig. 1.

The strength of the ε-covering concept derives from the following result due to [Papadimitriou and Yannakakis, 2000]: for any fixed number m > 1, for any finite ϵ > 0 and any set U of bounded utility vectors such that 0 < ui (x) ≤ K for all i ∈ M, there exists in U an ε-covering of the Pareto set ND(U) the size of which is polynomial in log K and 1/ log(1 + ϵ). The result can be simply explained as follows: to any utility vector u ∈ Zm+ , we can assign vector ϕ(u) the components of which are ϕ(ui ) = ⌈ logui log(1+ε) ⌉. By definition, the following property holds:

Thanks to the scaling and rounding operation, the number of different possible values for ϕ is bounded on each axis by ⌈log K/ log(1 + ε)⌉. Hence the cardinality of set ϕ(U) = {ϕ(u), u ∈ U} is upper bounded by B(K,m, ε) = ⌈log K/ log(1 + ε)⌉m. This can easily be explained using the right part of Fig. 1 representing a logarithmic grid in the space of criteria. Any square of the grid represents a different class of utility vectors having the same image through ϕ. Thanks to Proposition 1, we can see that any vector belonging to a given square covers any other element of the square in terms of ≿ε. Hence, choosing one representative in each square, we cover the entire set U. The size of the covering is bounded by the number of squares in the grid, i.e., B(K,m, ε). The covering can easily be refined by keeping only the elements of ND(ϕ(U)) in the covering (plotted in black on Fig. 1). Since we have no more than one Pareto-optimal element for each different value of ϕ(u) such a covering will include at most ⌈log K/ log(1 + ε)⌉m-1 elements. In Example 1, if items are described by 20 Boolean attributes, then the Pareto set contains more than one million of elements (220 ) whereas ⌈log 220 / log 1.1⌉ = 146 elements are sufficient to cover this set with a tolerance threshold of 10% (ε = 0.1).

It is now natural to wonder how GAI decomposability of utility functions can be used to efficiently compute i) the exact set of Pareto-optimal utility vectors (when it is not too large) and ii) an ε-covering of the Pareto set when it is too large for complete enumeration. In both cases, we would like to be able to recover a feasible solution for each returned vector. These questions are discussed in the following sections.

3 Pareto Set Computation using GAI nets

GAI decompositions are extensions of additive and multilinear decompositions [Bacchus and Grove, 1995]. They encode utilities as a sum of subutilities with overlapping factors:

Definition 5 (GAI decomposition) Let X = ∏ni=1 Xi. Let Z1 , . . . ,Zr ⊆ N = {1, . . . , n} be such that N = ∪ri=1Zi. For every i, let XZi = ∏j∈Zi Xj. Utility u(·) is GAIdecomposable w.r.t. the XZi 's iff there exist functions ui : XZi ↦→ R such that u(x) = ∑ri=1 ui(xZi ), for all x ∈ X, where xZi denotes the tuple constituted by the xj's, j ∈ Zi.

GAI decompositions can be represented by graphical structures called GAI networks [Gonzales and Perny, 2004] which are essentially similar to the junction graphs used for Bayesian networks [Jensen, 1996; Cowell et al., 1999]:

Definition 6 (GAI network) Let X = ∏ni=1 Xi. Let Z1 , . . . ,Zr be some subsets of N = {1, . . . , n} such that ⋃ri=1 Zi = N. Let u(x) = ∑ri=1 ui(xZi ) for all x ∈ X. Then a GAI network representing u(·) is an undirected graph G = (V, E), satisfying the following two properties:

1. V = {XZ1 , . . . , XZr };
2. For every (XZi ,XZj ) ∈ E, Zi ∩Zj ̸= ∅. For every

pair of nodes XZi ,XZj such that Zi ∩ Zj = Tij ̸= ∅, there exists a path in G linking XZi and XZj such that all of its nodes contain all the indices of Tij (Running intersection property).

Nodes of V are called cliques. Every edge (XZi ,XZj ) ∈ E is labeled by XTij = XZi∩Zj and is called a separator.

Cliques are drawn as ellipses and separators as rectangles. Here, we shall only consider GAI trees. This is not restrictive as general GAI nets can always be compiled into GAI trees [Gonzales and Perny, 2004]. For any GAI decomposition, by Definition 6, the cliques of the GAI net should be the sets of variables of the subutilities. For instance, the GAI net of Fig. 2 represents the GAI decomposition: u(a, b, c, d, e, f ) = u1(a, b) + u2(c, e) + u3(b, c, d) + u4(d, f ).

3.1 Exact Pareto Set Computation

To understand how GAI nets can be exploited to compute Pareto sets, assume that two agents have preferences over a set X = A × B × C × D × E × F. Both agents have utilities decomposable according to the GAI net of Fig. 2, i.e., ui (a, b, c, d, e, f ) = ui1 (a, b) + ui2 (c, e) + ui3 (b, c, d) + ui4 (d, f ), i = 1, 2, the tables of Fig. 2 showing pairs (u1j , u2j ). Denote by U the set of all possible values of u. The key property of our algorithm is that, for any additive utility vector vi (x, y) = vi1 (x) + vi2 (y), i = 1, 2, the Pareto set w.r.t. v can only be constituted by non-dominated vectors v1(x)'s and v2(y)'s. Indeed, if v1(x) ≻P v1(x′ ), then, for any y, v1(x) + v2(y) ≻P v1(x′ ) + v2(y), hence v1(x′ ) cannot be part of the Pareto set w.r.t. v. Now, let us come back to the GAI net of Fig. 2. For a fixed value, say b1, of separator B, ui (a, b, c, d, e, f ) becomes an additive utility: ui1 (a, b1) + vi (b1 , c, d, e, f ). Consequently, for B = b1, vectors in ND(U) can only be constituted with non-dominated u1(a, b1)'s and, for instance, it cannot contain u1(a3 , b1) = (7, 1) as u1(a2 , b1) = (8, 2) ≻P u1(a3 , b1). Hence, if clique AB sends to BCD message MB containing, for each value bj of B, non-dominated vectors u1(a, bj), then only these vectors need be considered for determining ND(U). For the same reason, only non-dominated vectors MC of u2 need be considered. Now, for each value dj of D, u(a, b, c, dj, e, f ) can be decomposed additively as w(a, b, c, dj , e)+ u4(dj , f ). Hence only non-dominated vectors w(a, b, c, dj, e) need be considered for determining ND(U). But, as shown previously, w(a, b, c, dj , e) must be equal to the sum of one vector of MB, one vector of MC and one compatible vector of u3. By compatible, we mean that if the vector chosen in MB (resp. MC) corresponds to B = bi (resp. C = ck), then only vector u3(bi, ck, dj) is allowed. For determining ND(U), only non-dominated such sums need be considered. These are precisely stored in message MD sent from clique BCD to clique DF . Finally, ND(U) can be exactly determined by computing all the sums of one vector of MD with a compatible vector in u4 and keeping only those non-dominated. This corresponds to message M. Note the efficiency of the algorithm: in our example |X| = 192, hence a naive approach would make dominance tests between 192 different vectors. Here, for each bi (resp. cj, dk), message MB (resp. MC, MD) requires dominance tests between 3 (resp. 4, 16) vectors, andMneeds dominance tests between 14 vectors.

This process can be automated as follows: first, we need a function that, given two sets of vectors, computes the non dominated vectors of their sums. GetLabelsNonDom defined below performs this operation. Actually, this function takes in argument some sets of labels V and W rather than sets of vectors. A label is simply a pair 〈v, P〉 such that v is a utility vector and P is some information enabling to get the instantiation of the attributes that led to v's utility value. In this function, operator ⊕ is defined as V ⊕W ↦→ L = {〈v + v′ , P ′′ 〉 : 〈v, P〉 ∈ V and 〈v′ , P ′ 〉 ∈ W}, i.e., operator ⊕ combines all vectors in V with all vectors in W. The rest of the function removes iteratively all dominated vectors and Lout contains the labels of all the non-dominated vectors.

Function GetLabelsNonDom(label sets V,W)

01 L ← V ⊕W; Lout ← ∅ 02 for all labels 〈v, P〉 ∈ L do 03 if ̸ ∃〈v′ , P ′ 〉 ∈ Lout s.t. v′ ≿P v then 04 remove fromLout all labels 〈v′ , P ′ 〉 s.t. v ≿P v′ Lout ← Lout ∪ {〈v, P 〉}

05 done

06 return Lout

Given this function, it is easy to compute the M's messages mentioned previously. Consider for instance the generation of message Ma of Fig. 3. Let XCp1 , . . . ,XCpr be the cliques adjacent to XCa that already sent their messages MPi 's to XCa . Let XSab be the separator between cliques XCa and XCb and let XDa be the attributes in clique XCa that do not belong to this separator. For any fixed value xSab of XSab , let Ma[xSab ] denote the non-dominated vectors given xSab to be sent to clique XCb . Then, as mentioned at the beginning of this section, Ma[xSab ] is the set of the non-dominated vectors among ∪xDa ∈XDa {ua(xDa , xSab ) + ∑rj=1 vij : vij ∈ MPij are compatible with (xDa , xSab )}. To compute this, we exploit the transitivity of Pareto dominance and first add to a given ua(xDa , xSab ) all its compatible vi1 's vectors. In function GetLabelsMessage, this is done on Line 07. Then combine the resulting vectors with all the compatible vi2 's and extract the non-dominated vectors.

This is done on Line 09 by a call to GetLabelsNonDom. Iterate over all the XCpi 's neighbors (loop 08-10). As a result, we get all the non-dominated vectors compatible with a given value xDa . There remains to make the unions of these sets of vectors for different instantiations (loop 06-12) and to extract from these unions the non-dominated vectors (Line 11). GetLabelsMessage thus computes correctlyMa.

Function GetLabelsMessage(XCa , XCb ) 01 let XCp1 ,...,XCpr be the cliques adjacent to XCa except XCb 02 letMpi , i = 1, ..., r, be the vectors sets sent by XCpi to XCa 03 let Sab =Ca ∩Cb, Da =Ca\Sab and Spia =Cpi ∩Ca 04 for all xSab ∈ XSab do 05 Ma[xSab ] ← ∅ 06 for all xDa ∈ XDa do 07 V ← {〈ua(xCa ), xCa 〉}⊕Mp1 [xSp1 a] 08 for all i ∈ {2, . . . , r} do 09 V ← GetLabelsNonDom(V , Mpi [xSpi a]) 10 done 11 Ma[xSab ] ← GetLabelsNonDom(V , Ma[xSab ]) 12 done 13 done 14 returnMa = {Ma[xSab ] : xSab ∈ XSab }

Now, to complete the computation of the Pareto set, there remains to organize the calls to GetLabelsMessage. This can be done by a classical "collect" algorithm as described below. Create a dummy attribute A of domain size 1 as well as a dummy clique root containing only A. Select an arbitrary clique XCa , add A to it, and add an edge between XCa and root. Then calling Collect(XCa ,root) clearly results in message Ma sent by XCa to root being the Pareto set. Now, for any v ∈ Ma, it is possible to determine which instantiations of the attributes have utility v because the collect phase returned labels which, by definition, contain enough informations to get back the instantiations.

Function Collect(clique XCa by clique XCb ) 01 for all cliques XCpi adjacent to XCa except XCb do 02 call Collect (XCpi , XCa ) 03 Ma ← GetLabelsMessage(XCa , XCb ) 04 send to XCb label setMa 05 done

For a fixed number of objectives m, function Collect is pseudopolynomial, i.e., it returns the Pareto set in time and space bounded by a polynomial in K, the largest of the ui 's over X, and L|XC|, the size of the instance, where L is the number of cliques in the GAI net and |XC| is the size of the biggest clique (i.e., the product of the domain sizes of its attributes). Actually, label sets V and W passed to GetLabelsNonDom have less than Km elements as each utility value is an integer between 1 and K. Hence, on line 01, L is computed in O(mK2m). But |L| ≤ Km as L contains sums of compatible subutilities. So, the for loop of lines 02-05 is executed at most Km times. As Lout ⊆ L, lines 03 and 04 can be executed in O(mKm). Hence GetLabelsNonDom is in O(mK2m). In function GetLabelsMessage, the for loops of lines 04 and 06 parse all the elements of XCa . Within these loops, Line 07 is performed in O(mKm) and lines 09 and 11 in O(mK2m). Hence the whole function is in O(|XCa |rmK2m), hence within O(|XC|rmK2m). Finally, function Collect calls GetLabelsMessage over all the cliques, hence all edges should be parsed and thus Collect is in O(|XC|LmK2m). Note that |XC| is exponential in w where w is the treewidth of the GAI net (i.e. the number of attributes in its largest clique). The algorithm is hence exponential in w but remains pseudo-polynomial for bounded w. In practice, w is small as subutility factors usually involve only a few attributes.

3.2 A FPTAS for the Pareto Set

Computing an ε-covering is in essence similar to computing a Pareto set. However, care must be taken when using εdominance. Let XCa and XCb be two adjacent cliques. Let v, v′ , v′′ be three vectors on clique XCa such that v ≿ϵ v′ and v, v′′ are non-dominated on clique XCa . Let w,w′′ be two vectors on clique XCb such that v′′ + w′′ ≿ϵ v + w. Since v + w is dominated, it should be deleted. However, to preserve a covering of the Pareto set, we need to be sure that v′′ + w′′ ≿ϵ v′ +w. Unfortunately, although v +w ≿ϵ v′ +w by additivity, we only have (1 + ϵ)2 (v′′ + w′′ ) ≿P v′ + w instead of (1 + ε)(v′′ + w′′ ) ≿P v′ + w. For this reason, we should have used an ε/2-dominance to ensure that the message sent by the second clique is actually an ε-covering. More generally, we need a finer dominance notion:

Definition 7 For any utility vectors u, v ∈ Zm+ , and any w > 0, u ≿wϵ v ⇔ (1 + ε)w u ≿P v. Then u is said to (ε, w)-dominate v, and a set of (ε, w)-non-dominated vectors is called an (ε, w)-covering.

Lemma 1 Let x, xi, y, yi, z be some positive vectors and w, wi be positive numbers. Then the following properties hold: P1: x ≿wϵ y =⇒ x + z ≿wϵ y + z. P2: [x ≿wϵ y and y ≿w′ ϵ z] =⇒ x ≿w+w′ ϵ z.

Hence as the collect over k cliques requires chaining k (ε,wi)-dominance tests, i = 1, ..., k, a sufficient condition to get an ε-covering is to choose the wi's summing to 1. Weights wi's can be chosen equal to 1/L, where L is the number of cliques or, better, they can be proportional to the sizes of the cliques. To implement this idea (with all the wi's equal to 1/L), we substitute function GetLabelsNonDom by the one below which computes (ϵ, 1/L)-covering labels.

Proposition 2 Let XCa be any clique of the GAI net. Add to XCa a dummy attribute A with a domain size of 1. Add to the GAI net a dummy clique root containing only A and an edge between XCa and root. Call Collect(XCa ,root). Then the message sent by XCa to root is an ε-covering.

Provided 1 ≤ K ≤ 2p(L|XC|) , where p denotes some polynomial, function Collect using the newly defined GetLabelsNonDom is a Fully Polynomial Time Approximation Scheme (FPTAS), i.e., it returns the ε-covering in time and space bounded by a polynomial in 1/ε and the instance size L|XC|. Indeed, vector sets V and W passed to GetLabelsNonDom are some (ε,w)-coverings, so they contain at most ⌈L log K/ log(1 + ε)⌉m elements. Here, we only consider small ε's, hence 1/ log(1 + ε) ≤ 2/ε. So, V and W contain less than (2L log K/ε)m elements and L is computed in O(m(L log K/ε)2m). By definition, Lgrid cannot contain more than ⌈L log K/ log(1 + ε)⌉m elements and checking whether ϕ(v) ∈ Lgrid is in O(m). We thus check whether v′ ≿1/L ϵ v at most (2L log K/ε)m times. For the same reason, Lout cannot have more than (2L log K/ε)m elements, hence line 05 can be completed in O((L log K/ε)m). Hence GetLabelsNonDom is within O(m(L log K/ε)2m). Therefore, the overall complexity of Collect is in O(L|XC|m(L log K/ε)2m).

4 Experimentations

In order to evaluate the performance of our algorithm, we performed numerical tests on a Core 2 Duo 2.66 GHz with 4 Gb of RAM. The first part of the experiments aims at illustrating the potential of GAI-decompositions to reduce computation times for the exact Pareto set. To this end, we have considered a search space with 17 attributes of size 5 and a GAI-net having a chain structure with 16 cliques XCi ={Xi,Xi+1}, i = 1, ..., 16, so as to have XCi ∩XCi+1 ={Xi+1} as separators. Then we drew utility tables randomly and computed the exact Pareto set using this GAI-net. Next, we merged cliques by pairs to form 8 cliques XC′ i = XC2i-1 ∪XC2i , i = 1, ..., 8, so as to represent the same utility in a less decomposed form; we computed the exact Pareto set again and recorded the computation time. Then we iterated the process and merged again cliques by pairs. We repeated the process until a single clique of size 17 was obtained. The next table provides computation times (in seconds) as the size of cliques varies from 2 to 17 (a timeout was set to 1 hour); the times represent averages over 20 different instances with different utility tables, for problems involving 2 and 5 objectives respectively. The results show that exploiting utility decompositions makes the multiobjective optimization significantly faster.

The second set of experimentations consists of evaluating the potential of a joint use of utility decomposition and ϵdominance to reduce computation times. To this end we have generated the pathological bi-objective instances of Example 1 with different sizes (from 10 to 20 attributes). For each instance, the covering of the Pareto set is computed with the The next table provides results on randomly generated bi-objective problems of different sizes (from 15 to 30 attributes). We give the cardinality of the output set (# sol) as well as the average computation times (in seconds) over 100 experimentations. Instances are generated as follows: for a given number of attributes, we generate a complete subgraph in the Markov graph containing the node representing the kth variable, and 2 other variables chosen randomly. Each GAI-network is then obtained by triangulation of the generated Markov graph, and each utility table is filled with values between 1 and 100. We get the following results:

Finally, we have investigated how the number of objectives impacts on solution times. The table below provides the running times of the FPTAS for ε = 10%, on problems with between 5 and 15 attributes, and from 2 to 10 objectives.

5 Conclusion

We have shown that GAI models can be used efficiently to generate Pareto sets using utility decompositions. The techniques introduced here bear some similarity with those involved in multiobjective state-space search [Stewart and White III, 1991] or in multiobjective CSPs [Rollon and Larrosa, 2007], with some additional specificities due to the use of junction trees and the aim of generating approximations. Our FPTAS reveals very fast, even on pathological instances, provided the number of objectives (not to be confused with the number of attributes) and the sizes of cliques are not too large (this is usually the case in reality). Besides utility decompositions, our tests confirm the practical efficiency of ε-dominance on multiobjective problems, as in [Laumanns et al., 2002; Bazgan et al., 2007; Perny and Spanjaard, 2008]. Knowing that the size of the Pareto set can be huge in real-world multiobjective combinatorial problems, utility decompositions and ε-coverings appear as key concepts to enhance efficiency of multiobjective optimization procedures while keeping performance guarantees. The approach proposed here also enables to go beyond Pareto optimality, even for non-decomposable preference models, provided they refine Pareto dominance. It can indeed be used to devise preference-based search algorithms where Pareto dominance is used to prune dominated solutions or subsolutions during the search.