Location problems with multiple criteria

Chapter 1 Location Problems with Multiple Criteria S. Nickel, J. Puerto, A.M. Rodr´ıguez-Ch´ıa Abstract This chapter analyzes multicriteria continuous, network, and discrete location problems. In the continuous framework, we provide a complete description of the set of weak Pareto, Pareto, and strict Pareto locations for a general Q-criteria location problem based on the characterization of three criteria problems. In the network case, the set of Pareto locations is characterized for general networks as well as for tree networks using the concavity and convexity properties of the distance function on the edges. In the discrete setting, the entire set of Pareto locations is characterized using rational generating functions of integer points in polytopes. Moreover, we describe algorithms to obtain the solutions sets (the different Pareto locations) using the above characterizations. We also include a detailed complexity analysis. A number of references has been cited throughout the chapter to avoid the inclusion of unnecessary technical details and also to be useful for a deeper analysis. Keywords: Pareto-optimal, Pareto locations, Level curves, Tree networks, Networks, Rational functions. S. Nickel Institute for Operations Research, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany, Fraunhofer Institute for Industrial Mathematics (ITWM), Kaiserslautern, Germany, e-mail: stefan.nick[email protected] J. Puerto IMUS, Universidad de Sevilla, Spain, e-mail: puer[email protected] A.M. Rodr´ıguez-Ch´ıa Universidad de C´adiz, C´adiz, Spain, e-mail: antonio.rodriguezc[email protected] 1 2 Nickel, Puerto, Rodriguez-Ch´ıa 1.1 Introduction Very often, locational decisions involve the investment of a significant amount of money. It will be therefore very probable that a locational decision is made by a group of Qdecision makers (DM). In turn, it is very likely that each DM will choose a median function to evaluate the quality of a new location, but the weights assigned to clients may differ a lot. The same scenario occurs if one location for different types of goods has to be found. Multicriteria analysis of location problems has received considerable attention within the scope of continuous, network, and discrete models in the last years. For an overview of general methods as well as for a more bibliographic overview of the related location literature the reader is referred to ?and ?. Presently, there are several problems that are accepted as classical ones: the point-objective problem (see, e.g., ???), the continuous multicriteria min-sum facility location problem (see, e.g., ??), the network multicriteria median location problem (see, for instance, ??) and the multicriteria discrete location problem (see, e.g., ?), among others. In contrast to problems with only one objective, we do not have a natural ordering in higher dimensional objective spaces. Therefore, in multicriteria optimization one has to decide which concept of “optimality” to choose. The goal in a multicriteria location problem is to optimize simultaneously a set of objective functions ( f1,..., fQ). Therefore, the formulation of the problem is: v−min x∈X⊆IRd(f1(x),..., fQ(x)),(1.1) where v−min stands for vectorial optimization. Observe that we get points in a Q-dimensional objective space where we do not have the canonical order of IR anymore. Accordingly, for this type of problems, different concepts of solution have been proposed in the literature (the reader is referred to ?as a general reference in multicriteria optimization). A point x∈IRdis called a Pareto location (or Pareto-optimal) if there exists no y∈IRdsuch that fq(y)≤fq(x)∀q∈Q:= {1,...,Q}and fp(y)<fp(x)for some p∈Q. We denote the set of Pareto solutions by X∗ Par f1,...,fQor simply by X∗ Par if this is possible without causing confusion. If fq(x)≤fq(x′)∀q∈Qand ∃q∈Q:fq(x)<fq(x′)we say that xdominates x′ in the decision space and f(x)dominates f(x′)in the objective space. Alternative solution concepts are weak Pareto-optimality and strict Pareto-opti- mality. A point x∈IRdis called a weak Pareto location (or weakly Pareto-optimal) if there exists no y∈IRd, such that fq(y)<fq(x)∀q∈Q.We denote the set of weak Pareto solutions by X∗ w−Par f1,..., fQor simply by X∗ w−Par if this is possible without causing confusion. A point x∈IRdis called a strict Pareto location (or strictly Pareto-optimal) if there exists no y∈IRd,y6=x, such that fq(y)≤fq(x)∀q∈Q.Analogously, the set of strict Pareto solutions is denoted by X∗ s−Par f1,...,fQ, or simply by X∗ s−Par if this is possible without causing confusion. Note that X∗ s−Par ⊆X∗ Par ⊆X∗ w−Par and in case we are considering strictly 1 Location Problems with Multiple Criteria 3 convex functions these three sets coincide. Finally, we recall that ?proved the connectedness of the set X∗ Par when the functions are convex. In our proofs we use the concept of level sets. For a function f:IRd→IR the level set for a value ρ ∈IR is given by L≤(f, ρ ):={x∈IRd:f(x)≤ ρ }(the strict level set is L<(f, ρ ):={x∈IRd:f(x)< ρ }) and the level curve for a value ρ ∈IR is given by L=(f, ρ ):={x∈IRd:f(x) = ρ }.For a function fi(·)we use the notation X∗(fi):=arg min x∈IRdfi(x). For two points xand ywe denote the segment defined by xand yas xy. In this chapter we focus on some fundamental results in the continuous, network and discrete cases. We will describe in some detail a complete geometric characterization for the planar 1-facility case, an optimal time algorithm for the 1-facility network problem as well as the computation of the entire set of Pareto-optimal solutions of the discrete multicriteria p-median problem. Although we are concentrating on the median case we will give some outlook to extensions. 1.2 1-Facility Planar/Continuous Location Problems In this section we study Problem (??) where f1(·),..., fQ(·)are convex, infcompact functions, defined in IR2, which represent different criteria or scenarios. Recall that a real function f(·)is said to be inf-compact if its lower level sets {x:f(x)≤ ρ }are compact for any ρ ∈IR. The next result states a useful characterization of the different solution sets defined in the previous section using level sets and level curves which will be used later. Theorem 1.1. The following characterizations hold : x∈X∗ w−Par f1,..., fQ⇔ Q \ q=1 L<(fq,fq(x)) = /0 (1.2) x∈X∗ Par f1,...,fQ⇔ Q \ q=1 L≤(fq,fq(x)) = Q \ q=1 L=(fq,fq(x)) (1.3) x∈X∗ s−Par f1,...,fQ⇔ Q \ q=1 L≤(fq,fq(x)) = {x}.(1.4) Proof. If x6∈ X∗ w−Par f1,..., fQ, there exists z∈IR2such that fq(z)<fq(x)for each q∈Q, that means, z∈ Q \ q=1 L<(fq,fq(x)). Hence, we obtain that 4 Nickel, Puerto, Rodriguez-Ch´ıa Q \ q=1 L<(fq,fq(x)) 6=/0. Since the implications above can be reversed the proof is concluded. The remaining results can be proved analogously.  Remark 1.1. For the case Q=2 the previous result states that the set X∗ w−Par(f1,f2) coincides with tangential cusps between the level curves of functions f1(·)and f2(·) union with X∗(f1)∪X∗(f2)(see Example ??). Corollary 1.1. If f 1,...,fQare strictly convex functions then X∗ w−Par(f1,..., fQ) = X∗ Par f1,..., fQ=X∗ s−Par f1,...,fQ. Example 1.1. (see Figure ??) Let us consider the points a1= (0,0),a2= (8,3),a3= (−3,5)and the functions f1(x) = kx−a1k1,f2(x) = kx−a2k∞,f3(x) = kx−a3k1. By Theorem ??,X∗ w−Par(f1,f2)is the rectilinear thick path joining a1and a2and X∗ w−Par(f1,f3)is the dark rectangle with a1and a3as opposite vertices. a1 a2 a3 X∗ w−Par(f1, f3) X∗ w−Par(f1, f2) Fig. 1.1 Illustration of Example ??. In what follows, since we are dealing with general convex, inf-compact functions, we will focus on providing information about the geometrical structure of X∗ w−Par(f1,f2,f3). This characterization will allow us to obtain a geometrical description of X∗ Par f1,f2,f3and X∗ s−Par f1,f2,f3in the next section for an important family of functions. Actually, we will characterize X∗ w−Par(f1,f2,f3)as a 1 Location Problems with Multiple Criteria 5 kind of hull delimited by the chains of bicriteria solutions of any pair of functions fp,fqp,q=1,2,3. This result enables us to obtain the set X∗ w−Par f1,..., fQby union of three-criteria solution sets already characterized. In order to do that, let C∞(IR+ 0,IR2):=n ϕ | ϕ :IR+ 0→IR2, ϕ continuous,lim t→∞k ϕ (t)k2=∞o, where kxk2is the Euclidean norm of the point x.C∞(IR+ 0,IR2)is the set of continuous curves, which map the set of non-negative numbers IR+ 0:= [0,∞)into the twodimensional space IR2and whose image ϕ (IR+ 0)is unbounded in IR2. These curves are introduced to characterize the geometrical locus of the points surrounded by weak-Pareto and Pareto chains. For a set S⊆IR2we define the enclosure of Sby encl(S):=x∈IR2:∃ ε >0 with B(x, ε )∩S=/0,∃t ϕ ∈[0,∞)with ϕ (t ϕ )∈Sfor all ϕ ∈C∞(IR+ 0,IR2)with ϕ (0) = x, where B(x, ε ) = {y∈IR2:ky−xk2≤ ε }. Note that S∩encl(S) = /0. Informally, encl(S)contains all the points which are surrounded by S, but do not belong themselves to S. We denote the union of the bicriteria chains of weak-Pareto solutions by Xgen w−Par f1,f2,f3:= 2 [ p=1 3 [ q=p+1 X∗ w−Par (fp,fq). We use “gen” since this set will generate the set X∗ w−Par f1,f2,f3. The next theorem provides useful geometric information to build X∗ w−Par f1,f2,f3. Its proof can be found in ?. Theorem 1.2. X∗ w−Par(f1,f2,f3) = enclXgen w−Par f1,f2,f3∪Xgen w−Par f1,f2,f3. Remark 1.2. It is worth noting that the region enclXgen w−Par f1,f2,f3is welldefined because the set Xgen w−Par f1,f2,f3is connected (see ?). As an illustration of the above result we present the following example. Example 1.2. Let us consider three points a1= (0,0),a2= (3,−1)and a3= (3,3), and the functions f1(·),f2(·)and f3(·)such that, L≤(f1,1) = (x1,x2):x2 1 4+x2 2 9≤1 L≤(f2,1) = (x1,x2):(x1−3)2+ (x2+1)2≤1 L≤(f3,1) = (x1,x2):(x1−3)2 9+(x2−3)2 4≤1. 6 Nickel, Puerto, Rodriguez-Ch´ıa We can see that these three functions are convex functions. Therefore by the previous result we obtain the geometrical characterization of the set X∗ w−Par(f1,f2,f3); this set is the shadowed region in Figure ??. a1 a2 a3 X∗ w−Par(f1, f3) X∗ w−Par(f1, f2) X∗ w−Par(f2, f3) X∗ w−Par(f1, f2, f 3) Fig. 1.2 Illustration of Example ??. Now we are in the right position to show the main result about the geometrical structure of X∗ w−Par(f1,...,fQ). Theorem 1.3. X∗ w−Par(f1,...,fQ) = [ p,q,r∈Q p<q<r X∗ w−Par(fp,fq,fr). Proof. By Theorem ??,x∈X∗ w−Par(f1,..., fQ)if and only if \ q∈Q L<(fq,fq(x)) = /0. Furthermore, by Helly’s theorem (see ?), this intersection is empty if and only if there exist p,q,r∈Q(p<q<r)such that L<(fp,fp(x)) ∩L<(fq,fq(x)) ∩ L<(fr,fr(x)) = /0 and this is equivalent to x∈X∗ w−Par(fp,fq,fr). Since in any case we have that [ p,q,r∈Q p<q<r X∗ w−Par(fp,fq,fr)⊂X∗ w−Par(f1,..., fQ), the result follows.  Remark 1.3. This result extends previous characterizations in the literature: 1 Location Problems with Multiple Criteria 7 - Taking fi(x) = kx−aikwith ai∈IR2for i=1,...,Qand k · k being a strictly convex norm or a norm derived from a scalar product, we get Proposition 1.3, Theorem 4.3 and Corollary 4.1 in ?. The set of weakly efficient locations is the convex hull of the points aiwith i=1,...,Q. In Example ??, we illustrate this result. - Taking fi(x) = kx−aikwith ai∈IR2for i=1,...,Qand k·k being a polyhedral gauge we get Theorem 6.1 in ?, where the set of weakly efficient locations is the union of elementary convex sets, (see ?for a definition). In Example ??, we illustrate this result. - Taking fi(x) = maxj∈Mwijkx−ajkwith aj∈IR2,wij>0 for i=1,...,Q,j∈ M:={1,...,m}and k · k being the ℓ∞-norm, we get Theorem 6.1 in ?, where the set of weakly efficient locations is the union of the sets of weakly efficient locations for all pairs of functions. In Example ??, we illustrate the use of this result. Example 1.3. (See Figure ??) Let us consider the points a1= (0,0),a2= (5,−10), a3= (10,0)and the functions fi(x) = kx−aik2for i=1,2,3. By Theorem ??, X∗ w−Par(f1,f2,f3)is the dark region, which in this case is the convex hull of a1,a2 and a3. a1 a2 a3 X∗ w−Par(f1, f2, f3) Fig. 1.3 Illustration of Example ??. Example 1.4. (See Figure ??) Let us consider the points a1= (0,0),a2= (8,3), a3= (−3,5)and the functions f1(x) = kx−a1k1,f2(x) = kx−a2k∞and f3(x) = kx−a3k1. By Theorem ??,X∗ w−Par(f1,f2)is the thick path joining a1and a2, X∗ w−Par(f2,f3)is the thick path joining a2and a3, and X∗ w−Par(f1,f3)is the dark rectangle with a1and a3as opposite extreme points. Therefore, by Theorem ??, X∗ w−Par(f1,f2,f3)is the dark region surrounded by the union of the three previous sets. Note that this region is the union of two full dimensional elementary convex sets. Example 1.5. (See Figure ??) Let us consider the points a1= (4,16),a2= (10,5), a3= (25,12)and the functions fi(x) = kx−aik∞for i=1,2,3. By Theorem ??, 8 Nickel, Puerto, Rodriguez-Ch´ıa a1 a2 a3 X∗ w−Par(f1, f3) X∗ w−Par(f1, f2) X∗ w−Par(f2, f3) X∗ w−Par(f1, f2, f3) Fig. 1.4 Illustration of Example ??. X∗ w−Par(f1,f2) = R1,X∗ w−Par(f1,f3) = R2∪R4,X∗ w−Par(f2,f3) = R3∪R4. By Theorem ??,X∗ w−Par(f1,f2,f3) = R1∪R2∪R3∪R4. Note that in this example X∗ w−Par(f1,f2,f3) = X∗ w−Par(f1,f2)∪X∗ w−Par(f1,f3)∪X∗ w−Par(f2,f3). a1 a2 a3 R4 R1 R2 R3 b b b Fig. 1.5 Illustration of Example ??. 1.2.1 Polyhedral Planar Minisum Location Problems Consider a set of demand points A:={a1,...,aM} ⊆ IR2. Let Bi⊂IR2, for i∈M:= {1,2,...,M}, be a compact, convex set containing the origin in its interior. The 1 Location Problems with Multiple Criteria 9 gauge with respect to Biis defined as γ i:IR2→IR, γ i(x):=inf{r>0 : x∈rBi}. Taking this definition into account, the planar minisum location problem is min x∈IR2 M ∑ i=1 wi γ i(x−ai), where wiis a nonnegative weight associated with the demand point ai(i∈M). In this section we study the particular case where the functions f1,..., fQare minisum location objective functions and the distances are measured with polyhedral gauges, i.e., the unit balls associated with these gauges are convex polytopes. This type of objective function is not strictly convex and for this reason, the three solutions sets (Pareto, weak Pareto and strict Pareto locations) do not coincide. Therefore, in this section we focus on the characterization of the Pareto locations and how it can be extended to the remaining solution sets. b b p1+N(B0, p1) p2+N(B0, p2) (0,0) (0,0) d1 d2 d3 d4 e1 e2 e3 e4 BB0 p1 p2 Fig. 1.6 Illustration of the unit ball for the ℓ1-norm, its dual ball and two normal cones of this dual ball. The polar set Bo iof Biis given by Bo i:={p∈IR2:hp,xi ≤ 1∀x∈Bi}and the normal cone to Biat xis given by N(Bi,x):={p∈IR2:hp,y−xi ≤ 0∀y∈Bi}, where h·,·i denotes the scalar product. In case of polyhedral gauges (i.e., Biis a polytope), the set of extreme points of Biis denoted by Ext(Bi):={ei 1,...,ei Gi}. The maximal number of extreme points is denoted by Gmax :=max{Gi:i∈M}. We define fundamental directions di 1,...,di Gias the half-lines determined by 0 and ei 1,...,ei Gi(see Figure ??). Let π = (pi)i∈Mbe a family of elements of IR2such that pi∈Bo ifor each i∈M and let C π =Ti∈M(ai+N(Bo i,pi)). According to ?, a nonempty convex set C is called an elementary convex set if there exists a family π such that C π =C. If the unit balls are polytopes, then we can obtain the elementary convex sets as intersections of cones generated by fundamental directions of these balls pointed at each demand point (for details, see ?). The 2-dimensional elementary convex sets are called cells. Let Cdenote to the set of these cells. Therefore each cell is a polyhedron whose 16 Nickel, Puerto, Rodriguez-Ch´ıa enclXgen Par f1,f2,f3⊆X∗ Par f1,f2,f3 ⊆Xgen Par f1,f2,f3∪enclXgen Par f1,f2,f3 =X∗ w−Par f1,f2,f3. Proof. Using Lemma ?? and Theorem ?? we have the following chain of inclusions that proves the thesis of the theorem. enclXgen Par f1,f2,f3⊆X∗ s−Par f1,f2,f3 ⊆X∗ Par f1,f2,f3⊆X∗ w−Par f1,f2,f3 ⊆Xgen Par f1,f2,f3∪enclXgen Par f1,f2,f3. Now it remains to consider the Pareto-optimality of the set Xgen Par f1,f2,f3 with respect to the three objective functions f1,f2,f3. For a cell C∈Cwe define the collapsing and the remaining part of Cwith respect to Q-criteria optimality by colQ(C):=x∈C:x/∈X∗ Par f1,...,fQ remQ(C):=x∈C:x∈X∗ Par f1,...,fQ. Summing up the preceding results we get a complete geometric characterization of the set of Pareto solutions for the three criteria case. For each cell C, colQ(C)˙ ∪remQ(C) = Cand, as shown by ?, determining both sets can be done with the gradients of the objective functions with a complexity of O(QlogQ). Theorem 1.6. The set of Pareto solutions satisfies: X∗ Par f1,f2,f3=Xgen Par f1,f2,f3∪enclXgen Par f1,f2,f3 \{x∈IR2:∃C∈C,C⊆Xgen Par f1,f2,f3,x∈col3(C)}. Proof. Let y∈X∗ Par f1,f2,f3. Then we have, by Theorem ??, that y∈Xgen Par f1,f2,f3∪enclXgen Par f1,f2,f3.Moreover for C∈Cwith y∈C we have y∈rem3(C), i. e., y/∈col3(C). This implies y∈Xgen Par f1,f2,f3∪enclXgen Par f1,f2,f3 \{x∈IR2:∃C∈C,C⊆Xgen Par f1,f2,f3,x∈col3(C)}. We distinguish the following cases : Case 1: y∈enclXgen Par f1,f2,f3. Then y∈X∗ Par f1,f2,f3by Theorem ??. Case 2 : y∈Xgen Par f1,f2,f3. Case 2.1 : ∃C∈C,C⊆Xgen Par f1,f2,f3with y∈C ⇒y/∈col3(C)⇒y∈rem3(C)⇒y∈X∗ Par f1,f2,f3. Case 2.2 : 6 ∃C∈C,C⊆Xgen Par f1,f2,f3with y∈C 1 Location Problems with Multiple Criteria 17 ⇒L≤(fp,fp(y))∩L≤(fq,fq(y)) = {y}for some p,q∈ {1,2,3},p<q ⇒T3 q=1L≤(fq,fq(y)) = {y} ⇒ y∈X∗ s−Par f1,f2,f3⊆X∗ Par f1,f2,f3. In the case of median functions the gradients ∇fq(x),q∈ {1,2,3},(in those points where they are well-defined) can be computed in O(Mlog(Gmax)) time (analogous to the evaluation of the function). Therefore, we can test in O(Mlog(Gmax)) time if a cell C∈C,C⊆Xgen Par f1,f2,f3collapses. We obtain the following algorithm for the 3-criteria median problem with time complexity O(M3G2 max log(Gmax)) (see ?for more details). Algorithm 1.2. Step 1. Compute the the subdivision of the plane generated C, the family of elementary convex sets. Compute X∗ w−Par f1,f2,X∗ w−Par f1,f3,X∗ w−Par f2,f3 using Algorithm ??. Step 2. Set Xgen Par f1,f2,f3:=X∗ w−Par f1,f2∪X∗ w−Par f1,f3∪X∗ w−Par f2,f3 and X∗ Par f1,f2,f3:=Xgen Par f1,f2,f3∪enclXgen Par f1,f2,f3. Step 3. For any C∈Cwith C⊆Xgen Par f1,f2,f3compute col3(C)and set X∗ Par f1,f2,f3:=X∗ Par f1,f2,f3\col3(C). Output: X∗ Par f1,f2,f3. Figure ?? illustrates the preceding results using the data introduced in Example ??. The dashed path joining X∗ 1and X∗ 3in the picture represents the set X∗ w−Par f1,f3after removing the col3(C). In the same way, the path joining X∗ 1 and X∗ 2represents the set X∗ w−Par f1,f2after removing the col3(C). Finally, the dotted segment joining X∗ 2and X∗ 3is X∗ w−Par f2,f3(in this case there are not cells to be collapsed). b b b b b b b b b rs rs rs a1a2 a3 a4a5 a6 a7a8 a9 X∗ 1 X∗ 3 X∗ 2 Fig. 1.12 Illustration of Xgen Par f1,f2,f3and X∗ Par f1,f2,f3for the problem introduced in Example ??. 18 Nickel, Puerto, Rodriguez-Ch´ıa 1.2.1.3 Case where Q>3 In this section we consider the general Q-Criteria case (Q>3). We prove that the Pareto solution set can be obtained from the Pareto solution sets of all the three criteria problems. This construction requires the removal of the dominated points from the union of all the three criteria Pareto solution sets. The reader may notice that all this process reduces to obtaining the bicriteria Pareto chains as proved in Theorem ??. Theorem 1.7. The following inclusions hold: 1. [ p,q,r∈Q p<q<r clenclXgen Par (fp,fq,fr)⊆X∗ Par f1,...,fQ. 2. X∗ Par f1,...,fQ⊆[ p,q,r∈Q p<q<r Xgen Par (fp,fq,fr)∪[ p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr)= X∗ w−Par f1,..., fQ. Proof. (1) Let x∈S p,q,r∈Q p<q<r clenclXgen Par (fp,fq,fr). This is equivalent to x∈clenclXgen Par (fp,fq,fr) for some p,q,r∈Q,p<q<r. Then, by Lemma ??,x∈X∗ s−Par (fp,fq,fr)for some p,q,r∈Q,p<q<r. Applying characterization (??), this is equivalent to L≤(fp,fp(x)) ∩L≤(fq,fq(x)) ∩ L≤(fr,fr(x)) = {x}for some p,q,r∈Q,p<q<rand since x∈L≤(fq,fq(x)) for all q∈Qit follows that TQ q=1L≤(fq,fq(x)) = {x}. Finally, again by (??), x∈X∗ s−Par f1,...,fQ, which implies that x∈X∗ Par f1,...,fQ. (2) Let x∈X∗ Par f1,...,fQthen x∈X∗ w−Par f1,..., fQand, by (??), this is equivalent to TQ q=1L<(fq,fq(x)) = /0. By Helly’s theorem, there exists p,q,r∈ Q,p<q<r, such that, L<(fp,fp(x)) ∩L<(fq,fq(x)) ∩L<(fr,fr(x)) = /0. By characterization (??), this is equivalent to x∈X∗ w−Par (fp,fq,fr)for some p,q,r∈ Q,p<q<rand, by Theorem 3.2 in ?, this implies that x∈Xgen Par (fp,fq,fr)∪ enclXgen Par (fp,fq,fr)for some p,q,r∈Q,p<q<r. Finally, this can be equivalently written as x∈[ p,q,r∈Q p<q<r Xgen Par (fp,fq,fr)∪[ p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr).  In the Q-criteria case the crucial region is now given by the cells C∈Cwith C⊆[ p,q,r∈Q p<q<r Xgen Par (fp,fq,fr)\[ p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr) 1 Location Problems with Multiple Criteria 19 =[ p,q∈Q p<q X∗ w−Par (fp,fq)\[ p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr). Similar to the situation in the previous section one can test whether the cell C∈C collapses with respect to f1,..., fQby comparing the gradients of the objective functions in int(C). Finally we obtain the following theorem, which can be proven using the same reasoning as in the 3-criteria case (see proof of Theorem ??). Theorem 1.8. X∗ Par f1,...,fQ= S p,q,r∈Q p<q<r Xgen Par (fp,fq,fr)∪S p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr)  \    x∈IR2:∃C∈C,C⊆S p,q∈Q p<q X∗ w−Par (fp,fq)\S p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr),x∈colQ(C)   For the Q-criteria median problem we obtain the following algorithm. Algorithm 1.3. Step 1. Compute the the subdivision of the plane generated C, the family of elementary convex sets. Compute X∗ w−Par (fp,fq),p,q∈Q,p<q,using Algorithm ??. Step 2. Set for any p,qand rwith p<q<r Xgen Par (fp,fq,fr):=X∗ w−Par (fp,fq)∪X∗ w−Par (fp,fr)∪X∗ w−Par (fq,fr), and X∗ Par f1,...,fQ:=S p,q,r∈Q p<q<r Xgen Par (fp,fq,fr)∪S p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr). Step 3. For every cell C⊆S p,q∈Q p<q X∗ w−Par (fp,fq)\S p,q,r∈Q p<q<r enclXgen Par (fp,fq,fr) compute colQ(C)and set X∗ Par f1,...,fQ:=X∗ Par f1,...,fQ\colQ(C). Output: X∗ Par f1,..., fQ. The complexity of Algorithm ?? can be determined as follows. For each cell C,colQ(C)can be computed in O(Qlog(Q)) time. Algorithm ?? needs to solve O(Q3)three-criteria problems which dominates all other elementary operations of the algorithm. Each one of them has the same complexity as the two-criteria problem. Thus, the overall complexity is O(M3G2 maxQ3(logGmax) + M2G2 maxQlogQ) = O(M3G2 maxQ3(logGmax). We would like to conclude this section pointing that the multi-facility versions of the problems analyzed in this section have been hardly studied in the literature, although an exception is the paper by ?. 20 Nickel, Puerto, Rodriguez-Ch´ıa 1.3 Network Location Problems 1.3.1 1-Facility Median Problems 1.3.1.1 Pareto Locations in General Networks Let G= (V,E)be a connected graph with node set V={v1,...,vn}and edge set E={e1,...,em}. Each edge e∈Ehas a positive length ℓ(e), and is assumed to be rectifiable. Let P(G)denote the continuum set of points on edges of G. We denote a point x∈e={u,v}as a pair x= (e,t), where t(0 ≤t≤1) gives the relative distance of xfrom node ualong edge e. For the sake of readability, we identify P(G)with Gand P(e)with efor e∈E. We also define (e,(t1,t2)) :={x= (e,t):t∈(t1,t2)}; (e,[t1,t2]),(e,(t1,t2]), and (e,[t1,t2)) are used in an analogous way. We denote by d(x,y)the length of the shortest path connecting two points x,y∈ G. Let vi∈Vand x= ({vr,vs},t)∈G. The distance from vito xentering the edge {vr,vs}through vr(vs) is given as D+ i(x) = d(vr,x) + d(vr,vi)(D− i(x) = d(vs,x)+ d(vs,vi)). Hence, the length of a shortest path from vito xis given by Di(x) = min{D+ i(x),D− i(x)}. As d(vr,x) = t·ℓ(e)and d(vs,x) = (1−t)·ℓ(e), the functions D+ i(x)and D− i(x)are linear in xand Di(x)is piecewise linear and concave in x (cf. ?). The distance from vito a facility located at xis finally defined as d(vi,x) = Di(x) = min{D+ i(x),D− i(x)}. We consider the objective function f(x) = ( f1(x),..., fQ(x)), where each fq(x), q∈Q, is a median function defined as: fq(x) = ∑ vi∈V wq id(vi,x). More formally, we assign a vector of weights wi=   w1 i . . . wQ i   6=0 to every vertex vi∈V,with wq i≥0,q∈Q:={1,...,Q}. The quality of a point x∈P(G)in this multicriteria setting is defined by f(x):=   f1(x) . . . fQ(x)   :=   ∑vi∈Vw1 id(x,vi) . . . ∑vi∈VwQ id(x,vi)    in the undirected case and f(x):=   f1(x) . . . fQ(x)   :=   ∑vi∈Vw1 i(d(x,vi) + d(vi,x)) . . . ∑vi∈VwQ i(d(x,vi) + d(vi,x))    1 Location Problems with Multiple Criteria 21 in the directed case. Let S⊆P(G)and W⊆IRQ. We define Wpar ={f(x)∈W:∄f(y)∈Wsuch that f(y)dominates f(x)in the objective space}and X∗ par :={x∈S:f(x)∈Wpar}. If S=P(G)we simply write X∗ par. A point x∈X∗ par(S)is called a Pareto location with respect to S, and the elements of X∗ par(V)are called Pareto nodes or Pareto vertices. Computing X∗ par(V)can simply be done by pairwise comparision of the nodes. For X∗ par we first have to check if a multicriteria version of Hakimi’s node dominance result holds (?). For the directed case we even have X∗ par(V) = X∗ par. The proof relies on the concavity of the distance functions among the edges and also on the fact that in the directed case we have no choice on which side to exit or enter an edge. This implies that the objective function is strictly concave and therefore the nodes always dominate the edges. For the technical details and the proofs the reader is referred to ?. In the case of undirected networks, this aspect is slightly more complicated as shown in the next example. Example 1.7. Consider the following network N= (G,ℓ)with n=6 nodes and a distance matrix D= (di j)i,j=1,...,6given by D=         0 1 1 4 3 2 1 0 2 3 4 1 1 2 0 3 2 3 4 3 3 0 5 2 3 4 2 5 0 3 2 1 3 2 3 0         . v1v2 v3v4 v5v6 1 3 3 1 3 3 1 22 Fig. 1.13 Network of Example ??. Assume that the weight vectors are w1=1 2,w2=2 1,w3=1 2,w4=2 2,w5=2 2,w6=2 1. Using this information we get 22 Nickel, Puerto, Rodriguez-Ch´ıa v1v2v3v4v5v6 f(·)21 1919 2121 1727 2929 2717 21 By pairwise comparison we get X∗ par(V) = {v3} ∪ {v6}=X∗f1(V)∪X∗f2(V). Now we look at the points on the edges and get (by using concavity in the objective functions): •v3dominates all points on the edges {v3,v5},{v3,v4},{v3,v1} •v6dominates all points on the edges {v6,v2},{v6,v5},{v6,v4} •v2dominates all points on the edge {v2,v4} •v1dominates all points on the edge {v1,v5} We also observe that no vertex can dominate a point with both objective functions smaller than 21. The only edge left is now {v1,v2}. 19 20 21 22 19 20 21 22 0 1 f2 f1 Fig. 1.14 Objective functions on the edge {v1,v2}in Example ??. We see that 1. For all points x∈P({v1,v2})with x6=v1,x6=v2we have f1(x)<21,f2(x)<21. 2. No point on {v1,v2}dominates another point on {v1,v2} ⇒X∗ par ={v3} ∪ {v6} ∪ ({v1,v2},(0,1)). We conclude that we have no node dominance and that even on edges with endnodes not in X∗ par(V)we can find elements of X∗ par. Since we do not have node dominance in the undirected case, we have to explicitly solve a multicriteria global optimization problem. First we will identify local Pareto locations with respect to an edge e={vi,vj}for all edges of the network. In a second step we will compare all local Pareto locations to get X∗ par. Due to the limited space and a possible overload of technicalities, we will describe the main ideas which allow the reader to understand the final algorithm. For the technical details and the proofs the reader is referred to ?. 1 Location Problems with Multiple Criteria 23 1.3.1.2 Bi-criteria Case We will first deal with the bi-criteria case, since here we can derive a geometrical solution method. The main property of the objective functions we are using is the concavity on an edge e={vi,vj}. In addition we have also piecewise linearity but this is not really needed. Suppose that f(vi)>f(vj)or f(vj)>f(vi). In the first situation we say that vjdominates viand in the latter vidominates vj. Both situations do not allow any location on the edge, which is not dominated by an endnode due to concavity. Now assume that for an edge e={vi,vj}with viand vjnot dominating each other one of the functions f1or f2is constant. It is easy to see that this is only the case if f(vi) = f(vj). If for an edge eonly one of the objective functions is constant then X∗ par(e) = {vi}∪{vj}. If both objective functions are constant then X∗ par(e) = ({vi,vj},[0,1]). Again this is due to the concavity of the objective functions and can be seen in Figure ??. 0 1 f2 f1 Fig. 1.15 Concavity on an edge with one objective function constant. Now we have only one situation left (the most typical one), where the endnodes do not dominate each other and none of the two objective functions is constant. Without loss of generality we can assume f1(vi)>f1(vj)and f2(vi)<f2(vj)(otherwise exchange the roles of viand vj). The behaviour of the objective functions can be seen in Figure ??. First, both objectives functions are increasing (maybe for a small or zero intervall only) and all points are dominated by the left endnode. Only after the first objective function is already decreasing and smaller than the left endnode value, the endnode cannot dominate the points of the edge. The same argument can be applied by starting from the right endnode. More formally we can define t1:=max{t∈[0,1]:f1(vi) = f1(({vi,vj},t))} and t2:=min{t∈[0,1]:f2(vj) = f2(({vi,vj},t))} 24 Nickel, Puerto, Rodriguez-Ch´ıa Then X∗ par(e) = {vi} ∪ {vj} ∪ {vi,vj},t1,t2. 0 1 t1t2 f1 f2 Fig. 1.16 Derivation of t1and t2. Overall we have that for each e∈Ein (G,ℓ),X∗ par(e)is a (possibly empty) single subedge of eplus one or both endnodes. Now we can combine these results to get an efficient algorithm for determining X∗ par(e). Algorithm 1.4. (Computation of X∗ par(e)) Input: edge e={vi,vj} ∈ E, undirected network (G,l), distance matrix D Step 1. IF vidominates vjthen X∗ par(e):={vi}, go to Step 7 Step 2. IF vjdominates vithen X∗ par(e):={vj}, go to Step 7 Step 3. IF f(vi) = f(vj)then a. IF f{vi,vj},1 2=f(vi)then X∗ par(e):=P({vi,vj}), go to Step 7 b. IF f{vi,vj},1 26=f(vi)then X∗ par(e):={vi} ∪ {vj}, go to Step 7 Step 4. IF f1(vi)<f1(vj)and f2(vi)>f2(vj)then exchange viand vj Step 5. Compute t1and t2as defined above Step 6. IF t1<t2 THEN X∗ par(e):={vi} ∪ {vj} ∪ {vi,vj},(t1,t2) ELSE X∗ par(e):={vi} ∪ {vj} Output: X∗ par(e) To analyze the complexity of this algorithm, we need the following definition: A point x= ({vi,vj},t),t∈[0,1]on one edge e={vi,vj}is called a bottleneck point for fqif there exists a vertex vkwith wq k>0, such that d(vk,x) = d(vk,vi) + d(vi,x) = d(vk,vj)+ d(vj,x). 1 Location Problems with Multiple Criteria 25 Let Bi j denote the set of bottleneck points on the edge {vi,vj}. Note that |Bi j| ≤ |V|. If Dis given, the only non constant operation in Algorithm ?? is the computation of t1and t2. To plot fqwe have to determine the breakpoints of fqwhich is piecewise linear on an edge. Since these breakpoints correspond to the bottleneck points on this edge we have to compute Bi j for e={vi,vj}. This can be done in O(|V|log|V|)(see ?). Then t1and t2can be determined by exploring the sorted list of bottleneck points two times. The total complexity for finding X∗ par(e)is O(|V|log|V|)and the total complexity for finding Se∈EX∗ par(e)is O(|E||V|log|V|). Example 1.8. Consider the following network: v1v2 v3v4 1 1 1 2 1 3 2 1 2 12 2 Fig. 1.17 Network of Example ??. with distance matrix D=    0 1 2 2 1 0 2 1 2 2 0 1 2 1 1 0    . We first compute v1v2v3v4 f110 7 8 6 f27 8 9 9 and obtain X∗ par(V) = {v1,v2,v4}. Now we have to determine the set X∗ par(e)for every e∈E: •e={v1,v2}.v1and v2do not dominate each other and f1,f2are not constant, i.e., we need to plot f1,f2and therefore we have to find B12 B12 =b1 12 ={v1,v2},1 2 f1b1 12=9.5 and f2b1 12=8.5 So the objective function can be drawn as shown in Figure ??. 32 Nickel, Puerto, Rodriguez-Ch´ıa Theorem 1.9. Let a,b∈P(T)and h := (h1,...,hQ)be a vector of Q objective functions, with hqconvex on T , for all q ∈Q={1,...,Q}. Then the following holds: {a,b} ⊆ X∗ par if and only if L[a,b]⊆X∗ par . For T= (V,E)and V′⊆Vlet W(V′):=     w1(V′) w2(V′) . . . wQ(V′)      , where wq(V′):=∑vi∈V′wq i,∀q∈Q. Proposition 1.1. Let T be partitioned in such a way that T =T1∪T2∪ {e}(and T1∩T2=/0). Then W(V(T1)) dominates W (V(T2)) if and only if for all x ∈P(T1) there exists some y ∈P(T2)which dominates x. Now we can state a multicriteria version of Goldman’s dominance algorithm (see ?). We start with a subtree containing only one leaf of the tree (check for dominance) and enlarge this subtree until we get a Pareto location using the criterion established in Proposition ??. This procedure is then repeated for all leaves and we end up with a subtree of all Pareto locations by using Theorem ??. Algorithm 1.7. (Solving Q-criteria median problems on a tree) Input: T= (V,E), with length function ℓand node weight vectors wq,q∈Q. Step 0. Set W:=W(V) Step 1. Choose a leaf vkof T, which was not yet considered and give it the status “considered”. Step 2. IF V={vk} Set X∗ par(f(V)) :=X∗ par(f(T)) :={vk}and go to Step 6 Step 3. Let vlbe the only node adjacent to vk IF (w1 k...wQ k)T<1 2W THEN •wq l:=wq l+wq k,q=1,...,Q •T:=T\ {vk} Step 4. IF there are any leaves left in Tgive them status “not considered” and go to Step 1 Step 5. Set X∗ par(f(V)) :=V(T),X∗ par(f(T)) :=T Step 6. STOP Output: X∗ par(f(V)) and X∗ par(f(T)) The complexity of this algorithm is O(Q|V|). To illustrate the algorithm consider the following example: 1 Location Problems with Multiple Criteria 33 Example 1.10. Consider the tree depicted in Figure ??. We solve the following instance of a 3-criteria median problem. Let l(e):=1, ∀e∈E. The weights of the nodes are given in the following table: v1v2v3v4v5v6v7v8v9v10 v11 w114 6 8 4 1 2 1 3 2 2 7 w211 3 3 24 5 2 2 3 2 2 5 w316 2 1 1 2 3 3 1 6 4 21 Therefore W=  50 62 60  and 1 2W=  25 31 30  . The adjacency structure of the tree is also given in Figure ??. Now we check every leaf till there is none left with status “not considered”. v1 v2 v3v4 v5 v6 v7 v8 v9 v10 v11 Fig. 1.24 Tree of Example ??. The bold edges and nodes indicate the set of Pareto locations. •Take v1:w1=  14 11 16  dominates W 2=  25 31 30  . Therefore w2:=  6+14 3+11 2+16 =  20 14 18  . By following the algorithm we delete v8,v7,v6,v5and v4. The actual value of w3is   13 32 4 . 34 Nickel, Puerto, Rodriguez-Ch´ıa •Take v3:w3=  13 32 4 does not dominate W 2. •Take v11:w11 =  7 5 21  dominates W 2. Therefore w9:=  9 7 27  . •Take v10:w10 =  2 2 4 dominates W 2. Therefore w9:=  11 9 31  . •Take v9:w9=  11 9 31  does not dominate W 2. Since we delete after every domination step the corresponding node from the tree according to Algorithm ?? and no leaf with status not considered is left we end up with X∗ par =L[v9,v3]. 1.3.2 Other Multicriteria Location Problems on Networks In the previous two subsections we presented optimal time algorithms for one facility median problems when looking for Pareto locations. We chose these two problems because the reader gets some insight into the needed properties. In addition, the simplification on trees caused by the uniqueness of paths can be seen. In the recent survey ?an overview on other location problems can be found. In ?an extension to 1-facility center problems as well as to positive and negative weight vectors on the nodes is developed. Those ideas have been further extended to problems with criteria dependent lengths in ?. A unified framework for multicriteria ordered median functions can be found in ?. In ?the location of undesirable facilities on multicriteria networks is looked at by using convex combinations of two objective functions. Some complexity analysis for the cent-dian location problem has been developped by ?. Most approaches to the (in general NP-hard) multi-facilty case are treated as discrete location problems (see Section ??). Only recently ?started looking into polynomial cases of multi-facility multicriteria location problems on networks. 1.4 Discrete Location Problems The previous sections show that planar and network multicriteria location problems have been widely developed from a methodological point of view so that important structural results and algorithms are known to determine solution sets. On the 1 Location Problems with Multiple Criteria 35 contrary, multicriteria analysis of discrete location problems has attracted less attention. In spite of that, several authors have dealt with problems and applications of multicriteria decision analysis in this field. An annotated bibliography with many references up to 2005 can be found in ?. In general, very few papers focus in the complete determination of the whole set of Pareto-optimal solutions. Nevertheless, there are some exceptions, such as the paper by ?that gives a theoretical characterization but does not exploit its algorithmic possibilities, as well as the work by ?that addresses the computation of the entire set of Pareto-optimal solutions of the multiobjective uncapacitated plant location problem. Nowadays, Multi-Objective Combinatorial Optimization (MOCO) (see ??) provides an adequate framework to tackle various types of discrete multicriteria problems as, for instance, the p-Median Problem (p-MP). Within this emergent research area, several methods are known to handle different problems. It is worth noting that most of MOCO problems are NP-hard and intractable (see ?, for further details). Even in most of the cases where the single objective problem is polynomially solvable the multiobjective version becomes NP-hard. This is the case of spanning tree problems and min-cost flow problems, among others. In the case of the p-MP, the single objective version is already NP-hard. This ensures that the multiobjective formulation is not solvable in polynomial time unless P=NP. In this context, when time and efficiency become a real issue, different alternatives can be used to approximate the Pareto-optimal set. One of them is the use of general-purpose MOCO heuristics (?). Another possibility is the design of “ad hoc” methods based on one of the following strategies: 1) computing supported non-dominated solutions; and 2) performing partial enumerations of the solutions space. Obviously, the second strategy does not guarantee the non-dominated character of all the generated solutions although the reduction in computation time can be remarkable. The aim of this section is to present methods to obtain the Pareto-optimal set for the multiobjective p-median problem (p-MP). In all cases, our approach to solve the multicriteria p-MP takes advantage of the problem’s structure. The first method is exact and it determines the whole set of Pareto-optimal solutions based on new tools borrowed from the theory of short rational generating functions. The second method is an “ad hoc” approximate method that generates supported Pareto locations. 1.4.1 Model and Notation Let I={1,...,M}and J={1,...,N}respectively denote the sets of indices for demand points and for plants, and Q={1,...,Q}denote the set of indices for the considered criteria. For each criterion q∈Q, let (cq i j)i∈I,j∈J∈QM×Nbe the allocation costs of demand points to plants. The multicriteria p-median location problem is: 36 Nickel, Puerto, Rodriguez-Ch´ıa v-Minimize M ∑ i=1 N ∑ j=1 c1 i jxi j,..., M ∑ i=1 N ∑ j=1 cq i jxi j!(1.6) subject to N ∑ j=1 xi j =1,i∈I,(1.7) xi j ≤yj,i∈I,j∈J,(1.8) N ∑ j=1 yj=p,(1.9) xi j ∈ {0,1},yj∈ {0,1},i∈I,j∈J.(1.10) As it is usual, v-min stands for vector minimum of the considered objective functions. Here variable yjtakes the value 1 if plant jis open and 0 otherwise. The binary variable xi j is 1 if the demand point iis assigned to plant jand 0 otherwise. Constraints (??), together with integrality conditions on the xvariables, ensure that each demand point is assigned to exactly one plant, while constraints (??) guarantee that no demand point is assigned to a non-open plant. Finally, constraint (??) ensures that exactly pplants are opened. Recall that in the single criterion case the integrality conditions on the xvariables need not be explicitly stated. The reason is that when the xi j represent the proportion of demand of client isatisfied by plant j(i.e. 0 ≤xi j ≤1), there exists an optimal solution with xi j =0,1, i∈I,j∈JThis property is not necessarily true when multiple criteria are considered because, in general, there might be undominated solutions with non-integer values and even non-supported undominated integer solutions. 1.4.2 Determining the Entire Set of Pareto-optimal Solutions In order to characterize the set of Pareto locations of the p-MP we shall use rational generating functions. Short rational generating functions were used by ?as a tool to develop an algorithm for counting the number of integer points inside convex polytopes, based on the previous geometrical paper by ?. The main idea is to encode those integer points in a rational function of as many variables as the dimension of the space where the polytope is defined. Let P⊂IRn +be a given convex bounded polyhedron. Its integer points may be expressed in a formal sum f(P,z) = ∑ α z α with α = ( α 1,..., α n)∈P∩Zn, where z α =z α 1 1···z α n nBarvinok’s goal was to represent that formal sum of monomials in the multivariate polynomial ring Z[z1,...,zn], as a “short” sum of rational functions with the same variables. Actually, ?developed a polynomial-time algorithm when the dimension, n, is fixed, to compute those functions. A clear example is the polytope P= [0,T]⊂IR with T∈N: the long expression of the generating function of the integer points inside Pis f(P,z) = ∑T i=0zi, and it is easy to see that its representation as sum of rational functions is the well known formula (1−zT+1)/(1−z). 1 Location Problems with Multiple Criteria 37 The above approach, apart from counting lattice points, has been used to develop some algorithms to solve integer programming problems exactly. Specifically, ?,?, and ?presented different methods to solve this family of problems using Barvinok’s rational function of the polytope defined by the feasible set of the given problem. First of all, for the sake of readability, we recall some results on short rational functions for polytopes that shall be later used in our presentation. For further details the interested reader is referred to ??. Let P={x∈IRn:Ax ≤b,x≥0}be a rational polytope in IRn. The main idea of Barvinok’s Theory was to encode the integer points inside a rational polytope in a “long” sum of monomials: f(P,z) = ∑ α ∈P∩Zn z α , where z α =z α 1 1···z α n n, and then to re-encode, in polynomial-time for fixed dimension, these integer points in a “short” sum of rational functions in the form f(P;z) = ∑ i∈I ε i zui n ∏ j=1 (1−zvi j ) , where Iis a polynomial-size indexing set, ε i∈ {1,−1}, and ui,vi j ∈Znfor all iand j(Theorem 5.4 in ?). It is well-known that enumerating the entire set of Pareto-optimal solutions of general multiobjective integer linear problems is #P-hard even in fixed dimension (see, e.g., ?and ?). Therefore listing these solutions, in general, is hopeless. Nevertheless, one can try to represent these sets in polynomial time using a different strategy by simply encoding their elements in an efficient way. This strategy has been recently applied by ?. In that paper, it is proved that using short generating functions of rational polytopes, one can encode the whole set of Pareto-optimal solutions of MOILP in polynomial time, fixing only the dimension of the space of variables. As an application of this result we can state the following theorem. Theorem 1.10. Assume that the number of facilities M and plants N is fixed. Then, in polynomial time, we can encode the entire set of Pareto-optimal solutions for (??)–(??)in a short sum of rational functions. Proof. Apply Theorem 1 in ?to the polytope of Problem (??)–(??). ⊓⊔ The combination of Theorem ?? and Theorem 7 in ?results in the following theorem. Theorem 1.11. Assume M and N are constant. There exists a polynomial-delay polynomial-space procedure to enumerate the entire set of Pareto-optimal solutions of (??)–(??). This construction can be implemented for problems of small to medium size dimension using the open source software barvinok, see ?. 38 Nickel, Puerto, Rodriguez-Ch´ıa 1.4.3 Determining Supported Pareto-optimal Solutions In some situations it suffices to generate the set of supported Pareto-optimal points. It is well-known that the set of supported Pareto-optimal solutions to a problem can be obtained by solving the scalarized problem for all possible values of the scalar weights in the standard Q-dimensional simplex Λ Q={ λ ∈RQ:∑Q q=1 λ q=1, λ q≥ 0,∀q=1,...,Q}. In order to describe how to obtain these solutions in problem (??)–(??) we need to introduce some additional notation. We denote by Bany feasible basis of the linear relaxation of Problem (??)–(??); and by Nall the columns that are not in B. Also, abusing notation, as usual in linear programming, we shall refer to the indices determining the basis B(N) in the variables and the objective function by (x,y)B ((x,y)N) and cB(cN), respectively. For any λ ∈ Λ Q, we shall denote by c( λ ) = (ci j( λ ))i j, where ci j( λ ) = ∑Q q=1 λ qcq i j. For each feasible basis B, consider the subdivision of the space Λ Qinduced by the hyperplanes: λ qcq BB−1N− λ qcq N=0,q∈Q. Next, let λ Q B∈ Λ Qbe a parameter such that it belongs to the relative interior of one of the elements in the above subdivision and satisfies cB( λ Q)B−1N−cN( λ Q)≤ 0. This choice of λ Qensures that the problem: Minimize M ∑ i=1 N ∑ j=1 ci j( λ Q B)xi j (1.11) subject to N ∑ j=1 xi j =1,i∈I,(1.12) xi j ≤yj,i∈I,j∈J,(1.13) N ∑ j=1 yj=p,(1.14) xi j ≥0,yj≥0,i∈I,j∈J.(1.15) will identify supported Pareto-optimal solutions of the linear relaxation of Problem (??)–(??). However, these Pareto-optimal solutions may result in fractional location variables since Problem (??)–(??) is a scalarization of the continuous version of our original multiobjective location problem. To avoid this inconvenience we shall solve the binary version of (??)–(??), namely 1 Location Problems with Multiple Criteria 39 Minimize M ∑ i=1 N ∑ j=1 ci j( λ B)xi j (1.16) subject to N ∑ j=1 xi j =1,i∈I,(1.17) xi j ≤yj,i∈I,j∈J,(1.18) N ∑ j=1 yj=p,(1.19) xi j ∈ {0,1},yj∈ {0,1},i∈I,j∈J.(1.20) Any optimal binary solution of (??)-(??) gives a supported Pareto-optimal solution of our original multiobjective location problem. Repeating the above process for all feasible basis of Problem (??)-(??) will result in a set of supported Pareto-optimal solutions for the problem. 1.5 Conclusions In this chapter we have presented and analyzed some of the most important models of multicriteria location problems considering three different decision spaces: continuous, networks and discrete. This material provides a general overview of the state-of-the-art of the field as well as a number of references that can be used by the interested readers to go for a further analysis of the topic. Emphasis was put on an efficient (if possible) description of the whole set of Pareto locations. Acknowledgements The authors were partially supported by projects FQM-5849 (Junta de Andaluc´ıa\FEDER), Fundaci´on S´eneca, grant number 08716/PI/08, the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office and MTM2010-19576-C02-01/02 (Ministry of Economy and Competitiveness\FEDER, Spain)