Continuous multifacility ordered median location problems

arXiv:1401.0817v1 [math.OC] 4 Jan 2014 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS V´ ICTOR BLANCO Dep. of Quantitative Methods for Economics & Business, Universidad de Granada SAFAE EL-HAJ BEN-ALI AND JUSTO PUERTO Dep. de Estad´ıstica e Investigaci´on Operativa, Universidad de Sevilla Abstract. In this paper we propose a general methodology for solving a broad class of continuous, multifacility location problems, in any dimension and with ℓτ-norms proposing two different methodologies: 1) by a new second order cone mixed integer programming formulation and 2) by formulating a sequence of semidefinite programs that converges to the solution of the problem; each of these relaxed problems solvable with SDP solvers in polynomial time. We apply dimensionality reductions of the problems by sparsity and symmetry in order to be able to solve larger problems. Continuous multifacility location and Ordered median problems and Semidefinite programming and Moment problem. 1. Introduction Multifacility location problems are among the most interesting and difficult problems in Location Analysis. It is well-known that even in their discrete version the p-median and p-center problems are already NP-hard (see Kariv and Hakimi [11].) A lot of attention has been paid in the last decades to these classes of problems, namely location-allocation problems, since they are easy to describe and to understand and they still capture the essence of difficult problems in combinatorial optimization. A comprehensive overview over existing models and their applications is given in [7] and the references therein. On the other hand, also in the last two decades locators have devoted much effort to solve continuous location problems that fall within the general class of global optimization, i.e. convexity properties are lost. Given a set of demand points (existing facilities) the goal is to locate several facilities to provide service to the existing ones (demand points) minimizing some globalizing function of the travel distances. Assuming that each demand point will be served by its closest facility we are faced with another location-allocation problem but now the new facilities can be located anywhere in the framework space and therefore they are not confined to be in an ”a priori” given set of locations. Obviously, these problems are much harder than the discrete ones and not much has been obtained regarding algorithms, and general convergence results, although some exceptions can be found in the literature [6] and the references therein. Since the nineties a new family of objective functions has started to be considered in the area of Location Analysis: the ordered median problem [21]. Ordered median problems represent as special cases nearly all classical objective functions in location theory, including the Median, CentDian, Center and k-Centra. Hence, handling the most important objective functions in location analysis is possible with one unique model and also new ones may be created by adapting adequately the parameters. More precisely, the p-facility ordered median problem can be formulated as follows: A vector of weights E-mail addresses:[email protected], [email protected], [email protected]. 1 2 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS (λ1,...,λn) is given. The problem is to find locations for the facilities that minimize the weighted sum of distances to the facilities where the distance to the closest point to its allocated facility is multiplied by the weight λn, the distance to the second closest, by λn−1, and so on. The distance to the farthest point is multiplied by λ1. As mentioned above, many location problems can be formulated as the ordered 1-median problem by selecting appropriate weights. For example, the vector for which all λi= 1 is the p-median problem, the problem where λ1= 1 and all others are equal to zero is the p-center problem, the problem where λ1=... =λk= 1 and all others are equal to zero is the p-k-centrum. Minimizing the range of distances is achieved by λ1= 1, λn=−1 and all others are zero. Lots of results have been obtained for these problems in discrete settings, on networks and even in the continuous single facility case (see the book [21], [4], [20] and the recent paper [2] ). However, very little is known in the continuous multifacility counterpart. In this paper, we address the multifacility continuous ordered median problem in finite dimension dand for general ℓτ-norm for measuring the distances between points. We show how these problems can be cast within a general family of polynomial optimization problems. Then, we show how these problems can be formulated as second order cone mixed integer programs or, using tools borrowed from the Theory of Moments [18], they can be solve (approximated up to any degree of accuracy) by a series of relaxed problems each one of them is a simple SDP that can be solved in polynomial time. We present preliminary computational results and show how the sizes and accuracy of the results can be improved by exploiting some specific characteristic of these models, namely sparsity in the representing variables and symmetry [14, 23, 31]. 2. Preliminaries In this section we recall the main definitions and results on Semidefinite Programming and the Theory of Moments that will be useful for the development through this paper. We use standard notation in those fields (see e.g. [18, 32]). Semidefinite programming (SDP) is relatively a new subfield of convex optimization and probably one of the most exciting development in mathematical programming, it is a particular case of conic programming when one considers the convex cone of positive semidefinite matrices, whereas linear programming considers the positive orthant, a polyhedral convex cone. SDP theoretically includes a large number of convex programming such as convex quadratic programming (QP), or second-order cone programming (SOCP). After polynomial time interior point methods for linear optimization were extended to solve SDP problems it has seen a great growth during the 1990s. The handbook [32] provides an excellent coverage of SDP as well as an extensive bibliography covering the literature up to year 2000. Let Snbe the space of real n×nsymmetric matrices. Whenever P, Q ∈Sn, the notation PQ (resp. P≻Q) stands for P−Qpositive semidefinite (resp. positive definite). Also, the notation hP, Qistands for trace(PQ). In canonical form, a primal semidefinite program reads: (SDP-P)    min hC, Xi s.t. hAi, Xi=bi,for i= 1,...,m, X0. where C, Ai∈Snfor i= 1,...,m, and b∈Rm. Its dual can be defined to be (SDP-D)          min bty s.t. m X i=1 yiAi−C0, y∈Rm. SDP duality is not always strong because of the nonlinear positive semidefinite constraint. To avoid duality gaps, we can require the problem and its dual to satisfy some qualification constraint. The CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 3 purpose of a constraint qualification is to ensure the existence of Lagrange multipliers at optimality in nonlinear problems. These multipliers are an optimal solution for the dual problem, and thus the constraint qualification ensures that strong duality holds: it is possible to achieve primal and dual feasibility with no duality gap. One common choice of constraint qualification is Slater’s constraint qualification [5]. It is usually easy to verify that it holds for an SDP problem; indeed, it suffices to exhibit an interior point for the nonlinear domain of the problem. Next, we describe the basic elements of the Theory of Moments to be used to approximate hard global optimization problems [18]. We denote by R[x] the ring of real polynomials in the variables x= (x1,...,xd), for d∈N(d≥1), and by R[x]r⊂R[x] the space of polynomials of degree at most r∈N(here Ndenotes the set of non-negative integers). We also denote by B={xα:α∈Nd}a canonical basis of monomials for R[x], where xα=xα1 1···xαd d, for any α∈Nd. Note that Br={xα∈ B: d X i=1 αi≤r}is a basis for R[x]r. For any sequence indexed in the canonical monomial basis B,y= (yα)α∈Nd⊂R, let Ly:R[x]→R be the linear functional defined, for any f=X α∈Nd fαxα∈R[x], as Ly(f) := X α∈Nd fαyα. The moment matrix Mr(y) of order rassociated with y, has its rows and columns indexed by the elements in the basis B={xα:α∈Nd}and for two elements in such a basis, b1=xα, b2=xβ, Mr(y)(b1, b2) = Mr(y)(α, β) := Ly(xα+β) = yα+β, for |α|,|β| ≤ r(here |a|stands for the sum of the coordinates of a∈Nd). Note that the moment matrix of order rhas dimension d+r d×d+r dand that there are d+2r dyαvariables. For g∈R[x] (= X γ∈Nd gγxγ), the localizing matrix Mr(gy) of order rassociated with yand g, has its rows and columns indexed by the elements in Band for b1=xα,b2=xβ, Mr(gy)(b1, b2) = Mr(gy)(α, β) := Ly(xα+βg(x)) = X γ gγyγ+α+β, for |α|,|β| ≤ r. Observe that a different choice for the basis of R[x], instead of the standard monomial basis, would give different moment and localizing matrices, although the results would be also valid. The main assumption to be imposed when one wants to assure convergence of some SDP relaxations for solving polynomial optimization problems (see for instance [17, 18]) is a consequence of Putinar’s results [22] and it is stated as follows. Archimedean Property. Let {g1,...,gm} ⊂ R[x]and K:= {x∈Rd:gj(x)≥0, j = 1,...,m}a basic closed semi-algebraic set. Then, Ksatisfies Archimedean property if there exists u∈R[x]such that: (1) {x:u(x)≥0} ⊂ Rdis compact, and (2) u=σ0+ m X j=1 σjgj, for some σ1,...,σm∈Σ[x]. (This expression is usually called a Putinar’s representation of uover K). Being Σ[x]⊂R[x]the subset of polynomials that are sums of squares. Note that Archimedean property is equivalent to impose that the quadratic polynomial u(x) = M− d X i=1 x2 ihas a Putinar’s representation over Kfor some M > 0. We observe that Archimedean property implies compactness of K. It is easy to see that Archimedean property holds if either {x:gj(x)≥0}is compact for some j, or all gjare affine and Kis compact. Furthermore, Archimedean property is not restrictive at all, since any semi-algebraic set K⊆Rdfor which is known that d X i=1 x2 i≤Mholds for some M > 0 and for all x∈K, admits a new representation 4 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS K′=K∪ {x∈Rd:gm+1(x) := M− d X i=1 x2 i≥0}that verifies Archimedean property (see Section 2 in [18]). The importance of Archimedean property stems from the link between such a condition with the semidefiniteness of the moment and localizing matrices (see [22] ). The use of this property for the particular problems that we deal with through this paper will be given in the next sections. A detailed presentation and an account of its implications can be found in [13]. Theorem 1 (Putinar [22]).Let {g1,...,gm} ⊂ R[x]and K:= {x∈Rd:gj(x)≥0, j = 1,...,m} satisfying Archimedean property. Then: (1) Any f∈R[x]which is strictly positive on Khas a Putinar’s representation over K. (2) y= (yα)has a representing measure on Kif and only if Mr(y)0, and Mr(gjy)0, for all j= 1,...,m and r∈N. Proposition 2 (Lasserre [13]).Let K:= {x∈Rd:gj(x)≥0, j = 1,...,ℓ} ⊂ Rdsatisfy the Archimedean Property and let p∈R[X]be a polynomial. Let r≥r0:= max{⌈deg p 2⌉,⌈deg g1 2⌉,...,⌈deg gl 2⌉}, and consider the hierarchy of semidefinite relaxations (1) Qr: infyLy(p) Mr(y)0, Mr−⌈deg gj/2⌉(gjy)0,1≤j≤ℓ Ly(y0) = 1 with optimal value denoted by inf Qr. Then, the hierarchy of SDP-relaxations {(Qr)r≥r0}is monotone non-decreasing and converges to ρ∗:= minx∈Kp(x). 3. The multiple allocation multifacility ordered median location problem This section deals with multifacility location models where more than one new facility have to be located to improve the service for the demand points. Several results obtained in previous papers are extended or reformulated with great generality giving a panorama view of the geometric insights of location theory. In this section we start by considering some multifacility ordered median problems already introduced in [21] and [24]. We shall extend these models, originally considered only in dimension 2 and with polyhedral norms to the more general case of dimension dand any ℓτ-norm being τ∈Q, τ ≥1 (here ℓτstands for the norm kxkτ=Pd i=1 |xi|τ1 τ, for all x∈Rd). Unlike the original approaches in [21, 24] where even for polyhedral norms there are proposed iterative algorithms for which polynomiality results can not be proven we shall follow on a different approach. In this section, we provide efficient reformulations of these classes of multifacility continuous location models and apply tools borrowed from conic programming to prove that these problems can be polynomially solved in the above mentioned cases, namely in dimension dand under polyhedral or ℓτ-norm to measure distances. We are given a set of demand points {a1, ..., an}and three sets of scalars {ω1, ..., ωn},ωi≥0,∀i∈ {1,...,n},{λ1, ..., λn}where λ1≥... ≥λn≥0 and {µ12, µ13,...,µp−1p}with µjj′≥0 for j, j′∈ {1,...,p}and j′> j. The elements ωiare weights corresponding to the importance given to the existing facilities ai, i ∈ {1, ..., n}and depending on the choice of the λ-weights we get different classes of problems. The µweights represent the penalty per distance unit given when locating two different facilities. We denote by Pnthe set of permutations of the first nnatural numbers. Natural extensions of the multifacility models considered in [21, 24] assume that one is looking for the location of pnew facilities rather than only one. In this formulation the new facilities are chosen to provide service to all the existing facilities minimizing an ordered objective function. These ordered problems are of course harder to handle than the classical ones not considering ordered distances. To CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 5 simplify the presentation we consider that the different demand points use the same norm to measure distances, although all our results extend further to the case of mixed norms. Let us consider a set of demand points {a1, a2,...,an} ⊂ Rd. We want to locate pnew facilities X={x1, x2,...,xp}which minimize the following expression: (2) fNI λ(x1, x2,...,xp) = n X i=1 p X j=1 λijd(i)(xj) + p−1 X j=1 p X j′=j+1 µjj′kxj−xj′kτ, where for any x∈Rd,di(x) = kai−xkτand d(i)(x) is the i-th element in the permutation of (d1(x),...,dn(x)) such that d(1)(x)≥d(2)(x)≥i |{z} ...≥d(i)(x)≥... ≥d(n)(x). In this model, it is assumed that (see [24]) (3) λ11 ≥λ21 ≥...≥λn1≥0 λ12 ≥λ22 ≥...≥λn2≥0 ... λ1p≥λ2p≥...≥λnp ≥0; µjj′≥0 for any j, j′= 1, . . . , p and, as mention above, d(i)(xj) is the expression, which appears at the i-th position in the ordered version of the list (4) LNI j:= (w1kxj−a1kτ,...,wnkxj−ankτ) for j= 1,2,...,p. Note that in this formulation we assign the lambda parameters with respect to each new facility, i.e., xjis considered to be non-interchangeable with xiwhenever i6=j. For this reason we say that this model has non-interchangeable facilities. The problem consists of: (LOCOMF −NI)ρNI λ:= min x{fNI λ(x) : x= (x1,...,xp), xj∈Rd,∀j= 1,...,p}, The reader should observe that this is the extension of Problem (3) in [24, Section 4.1]. Theorem 3. The problem LOCOMF −NI admits at least one solution. Proof. We know that n X i=1 p X j=1 λijd(i)(xj) = n X i=1 max σ p X j=1 λijwσ(i)kxj−aσ(i)kτ, where σis a permutation of the set {1,2, ..., p}. Therefore, the first part of the objective function is a sum of maxima of convex functions. Hence, it is a convex function. Thus, fNI λis a convex function as a sum of convex functions. Next, suppose that we restrict to consider the problem where xj=xfor all j= 1, ..., p. Assume that x∗is a solution. Then, for any xnot optimal it must exist ix∈ {1, ..., n}such that kx−aixkτ≥ kx∗−aixkτ. Thus taking x= 0, we get kx∗−ai0kτ≤ kai0kτ, =⇒ kx∗kτ−max i=1,...,n kaikτ≤max i=1,...,n kaikτ, =⇒ kx∗kτ≤2 max i=1,...,n kaikτ=M.(5) We denote by Xthe set {x∈Rp×d:kxjkτ≤M, ∀j= 1, ..., p}. Our problem consists of minimizing the convex function fNI λ, thus it is continuous over Xwhich is compact in Rp×dand consequently by Weierstrass theorem, problem LOCOMF −NI admits at least one solution.   6 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS Remark 4. Unlike the single facility problem, a solution of the multifacility problem is not unique in general. The following example shows what may happen. Consider the two-facility problem with set of demand point A={(0,0),(0,1),(1,1),(0,1)}. Then, any point (x1, x2)∈[(0,0),(0,1)],[(1,1),(0,1)] is an optimal solution. Next we prove that Problem LOCOMF −NI can be equivalently written as the following problem what will allow us the development of an efficient algorithm based on the theory of semidefinite programming. Theorem 5. Let τ=r sbe such that r, s ∈N\ {0},r≥sand gcd(r, s) = 1. For any set of lambda weights satisfying λ1j≥... ≥λnj ≥0for all j= 1,...,p, Problem (LOCOMF −NI)is equivalent to ρNI λ= min n X i=1 p X j=1 vij + n X ℓ=1 p X j=1 wℓj + p−1 X j=1 p X j′=j+1 tjj′ (6) s.t vij +wℓj ≥λℓjuij,∀i, ℓ = 1, ..., n, j = 1,...,p(7) yijk −xjk +aik ≥0, i = 1, . . . , n, j = 1, ..., p, k = 1,...,d(8) yijk +xjk −aik ≥0, i = 1, . . . , n, j = 1, ..., p, k = 1,...,d,(9) yr ijk ≤ςs ijkur−s ij , i = 1, . . . , n, j = 1, ..., p, k = 1,...,d,(10) ωr s i d X k=1 ςijk ≤uij, i = 1, . . . , n, j = 1,...,p(11) zjj′k−xjk +xj′k≥0, j, j′= 1, . . . , p, k = 1, ..., d,(12) zjj′k+xjk −xj′k≥0, j, j′= 1, . . . , p, k = 1, ..., d,(13) zr jj′k≤ξs jj′ktr−s jj′, j, j′= 1, . . . , p, k = 1,...,d,(14) µr s jj′ d X k=1 ξjj′k≤tjj′, j, j′= 1,...,p,(15) ςijk ≥0, i = 1, . . . , n, j = 1, . . . , p, k = 1,...,d,(16) ξjj′k≥0j, j′= 1, . . . , p, k = 1,...,d.(17) Moreover, Problem (6) satisfies Slater condition and it can be represented as a semidefinite program with (np +p2)(2d+ 1) + p2linear inequalities and at most 4(p2d+npd) log rlinear matrix inequalities. Proof. Note that the condition λ1j≥... ≥λnj for all j= 1, ..., p, allows us to write Problem (LOCOMF −NI) as (18) min x∈Rdp max σ∈Pn n X i=1 p X j=1 λijωσ(i)kxj−aσ(i)kτ+ p−1 X j=1 p X j′=j+1 µjj′kxj−xj′kτ, Let us introduce the auxiliary variables uij and tjj′,i= 1,...,n and j, j′= 1,...,p to which we impose that uij ≥ωikxj−aikτand tjj′≥µjj′kxj−xj′kτ, to model the problem in a convenient form. Now, for any permutation σ∈ Pn, let uσj = (uσ(1)j,...,uσ(n)j) for j= 1, ..., p. Moreover, let us denote by (·) the permutation that sorts any vector in nonincreasing sequence, i.e. u(1)j≥u(2)j≥ ...≥u(n)j. Using that λ1j≥... ≥λnj and since uij ≥0, for all i= 1,...,n and j= 1,...,p then n X i=1 p X j=1 λiju(i)j= max σ∈Pn n X i=1 p X j=1 λijuσ(i)j. The permutations in Pncan be represented by the following binary variables pijk =1,if uij goes in position k, 0,otherwise, CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 7 imposing that they verify the following constraints: (19)          n X i=1 pijk = 1,∀j= 1, ..., p, k = 1, ..., n, n X k=1 pijk = 1,∀i= 1, ..., n, j = 1, ..., p. Next, combining the two sets of variables we obtain that the objective function of (18) can be equivalently written as (20)                          n X i=1 p X j=1 λiju(i)j= max n X i=1 p X j=1 n X k=1 λijuijpik s.t n X i=1 pijk = 1,∀j= 1, ..., p, k = 1, ..., n, n X k=1 pijk = 1,∀i= 1, ..., n, j = 1, ..., p, pijk ∈ {0,1}. Now, we point out that for fixed ji.e. u1j, ..., unj , we have (21)                        n X i=1 λiju(i)j= max n X i=1 n X k=1 λijuijpijk s.t n X i=1 pijk = 1,∀k= 1, ..., n, n X k=1 pijk = 1,∀i= 1, ..., n, pijk ∈ {0,1}. The problem below is an assignment problem and its constraint matrix is totally unimodular, so that solving a continuous relaxation of the problem always yields an integral solution vector [1], and thus a valid permutation. Moreover, the dual of the linear programming relaxation of (21) is strong and also gives the value of the original binary formulation of (21). Hence, for fixed j∈ {1, ..., p}and for any vector u·j∈Rn, by using the dual of the assignment problem (21) we obtain the following expression (22)      n X i=1 λiju(i)j= min n X i=1 vij + n X l=1 wlj s.t vij +wlj ≥λljuij,∀i, l = 1, ..., n. Finally, we replace (22) in (18) and we get (23)              min n X i=1 p X j=1 vij + n X l=1 p X j=1 wlj + p−1 X j=1 p X j′=j+1 tjj′ s.t vij +wlj ≥λljuij,∀i, l = 1, ..., n, j = 1, ..., p, uij ≥ωikxj−aikτ, i = 1, ..., n, j = 1, ..., p, tjj′≥µjj′kxj−xj′kτ, j, j′= 1, ..., p. 8 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS It remains to prove that each inequality uij ≥ωikxj−aikτ, i = 1, ..., n, j = 1, ..., p can be replaced by the system yijk −xjk +aik ≥0, k = 1, ..., d, yijk +xjk −aik ≥0, k = 1, ..., d, yr ijk ≤ςs ijkur−s ij , k = 1, ..., d, ωr s i d X k=1 ςijk ≤uij, ςijk ≥0,∀k= 1,...,d. Indeed, set ρ=r r−s, then 1 ρ+s r= 1. Let (¯xj,¯uij) fulfill the inequality uij ≥ωikxj−aikτ. Then we have ωik¯xj−aikτ≤¯uij ⇐⇒ ωi d X k=1 |¯xjk −aik|r s!s r ≤¯us r ij ¯u 1 ρ ij ⇐⇒ ωi d X k=1 |¯xjk −aik|r s¯ur s(−r−s r) ij !s r ≤¯us r ij ⇐⇒ ωr s i d X k=1 |¯xjk −aik|r s¯u−r−s s ij ≤¯uij (24) Then (24) holds if and only if ∃ςij ∈Rd,ςijk ≥0,∀k= 1, ..., d such that |¯xjk −aik|r s¯u−r−s s ij ≤ςijk,satisfying ωr s i d X k=1 ςijk ≤¯uij, or equivalently, (25) |¯xjk −aik|r≤ςs ijk ¯ur−s ij , ω r s i d X k=1 ςijk ≤¯uij. Set ¯yijk =|¯xjk −aik|and ¯ςijk =|¯xjk −aik|τ¯u−1/ρ ij . Then, clearly (¯xj,¯uij,¯yij,¯ςij ) satisfies (8)-(11) and (16). Conversely, let (¯xj,¯uij,¯yij,¯ςij ) be a feasible solution of (8)-(11) and (16). Then, ¯yijk ≥ |¯xjk −aik| for all i, j and by (10) ¯ςijk ≥¯y(r s) ijk u−r−s s ij ≥ |¯xjk −ajk|τ¯u−r−s s ij . Thus, ωr s i d X k=1 |¯xjk −ajk|r s¯u−r−s s ij ≤ωr s i d X k=1 ¯ςijk ≤¯uij, which in turns implies that ωr s i d X k=1 |¯xjk −ajk|r s≤¯uij ¯u r−s s ij and hence, ωik¯xj−aikτ≤¯uij. In the same way we prove that each inequality tjj′≥µjj′kxj−xj′kτ, j, j′= 1, ..., p can be replaced by the system zjj′k−xjk +xj′k≥0, k = 1, ..., d, zjj′k+xjk −xj′k≥0, k = 1, ..., d, zr jj′k≤ξs jj′ktr−s jj′, k = 1,...,d, µr s jj′ d X k=1 ξjj′k≤tjj′, ξijk ≥0,∀k= 1,...,d. CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 9 Next, we observe that each one of the inequalities yr ijk ≤ςs ijkur−s ij , k = 1,...,d (respectively zr jj′k≤ ξs jj′ktr−s jj′, k = 1,...,d) can be transformed, according to [3, Lemma 3], into 4 log rlinear matrix inequalities (respectively 4 log rlinear matrix inequalities), being then exactly representable as second order cone constraints or semidefinite constraints. Finally, it is straightforward to check Slater condition, for instance, for the system (23). Set vij = 1, wlj =3 2Mλlj max iωi,uij =3 2Mωi+2 with M >> 0 large enough and tjj′= 2Mµjj′+1 for i, l = 1, ..., n and j, j′= 1, ..., p.  In the particular case where τ= 1 (namely r=s= 1) or the considered norm is polyhedral, the above problem reduces to a standard linear problem and the number of variables and inequalities is reduced. As a consequence of Theorem 5, Problem (LOCOMF −NI) can be solved in polynomial time for any dimension d, by solving its reformulation as the SDP problem (6)-(15). The reader may note that this is an important step forward with respect to the already stated complexity results (see e.g. [24]). There, it is proven that these problems are polynomial in R2and polyhedral norms. Here we extend this complexity result for any polyhedral or ℓτ-norm and in any finite dimension. Example 6. Consider the two-facility problem with set of four demand points A={(9.46,9.36),(8.93,7.00),(2.20,1.12),(1.33,8.89)} (a subset of the 50-cities data set from [8]), and (randomly generated-) lambda weights: λ11 = 147.31,λ12 = 119.08 λ21 = 24.44,λ22 = 0.56 λ31 = 24.16,λ32 = 0.00 λ41 = 10.77,λ42 = 0.00 µ12 = 0.56 and norm ℓ2. Therefore, the problem to be solved can be written as: min x1,x2∈R2147.31d(1)(x1) + 24.44d(2)(x1) + 24.16d(3)(x1) + 10.77d(4)(x1) + 119.08d(1)(x2) + +0.56d(2)(x2) + 0.00d(3)(x2) + 0.00d(4)(x2) + 0.56kx1−x2k2 Then we get as solution: x∗ 1= (5.24,6.41) and x∗ 2= (5.61,5.44), with objective value f∗= 1704.55. Figure 6 shows the points and the solutions of the problem. 4. Single Allocation Multifacility Location Problems with ordered median objective functions The difference of the single allocation multifacility problems with those considered in the previous section rests on the fact that now each demand point shall be directed to a unique serving facility by means of a predetermined allocation rule (usually closest distance). This little difference makes the problem much more difficult since the convexity properties exhibited in the previous models are no longer valid and more sophisticated tools must be used to solve these problems. In this framework, we are given a set {a1,...,an} ⊂ Rdendowed with a ℓτ-norm; and a feasible domain K={x∈Rd:gj(x)≥0, j = 1,...,m} ⊂ Rd, closed and semi-algebraic. The goal is to find p points x1,...,xp∈K⊂Rdminimizing some globalizing function of the shortest distances to the set of demand points. The main feature and what distinguishes multifacility location problems from other general purpose optimization problems, is that the dependence of the decision variables is given throughout the norms to the demand points, i.e. kx−aikτ. For the ease of presentation we have restricted ourselves to the particular case of pure location problem, namely ˜ fi(x) := min j=1...p kxj−aikτwhich has attracted a lot of attention in the literature of 16 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS Problem p τ CPUTime f∗Problem p τ CPUTime f∗Problem p τ CPUTime f∗ p-median 2 1.5 22.31 150.955 p-center 2 1.5 1.03 4.9452 p-25-centrum 2 1.5 10.08 100.8474 2 1.13 135.5222 2 0.28 4.8209 2 0.38 95.0892 3 23.68 130.856 3 13.51 4.788 3 139.03 89.0238 5 1.5 55.28 78.6074 5 1.5 3.73 2.8831 5 1.5 33.09 53.4995 2 12.49 72.2369 2 5.37 2.661 2 7.61 49.6932 3 125.1 68.1791 3 2.87 2.5094 3 18.23 46.9844 10 1.5 5.36 45.0525 10 1.5 2.66 1.6929 10 1.5 68.36 30.7137 2 2.31 41.6851 2 5.3 1.6113 2 17.93 28.9017 3 4.76 39.7222 3 55.76 1.595 3 225.64 27.5376 15 1.5 6.7 30.0543 15 1.5 9.44 1.1139 15 1.5 49.92 22.4165 2 43.91 27.6282 2 0.62 1.0717 2 11.26 20.6536 3 150.99 26.6047 3 50.08 1.053 3 244.59 20.8544 30 1.5 14.45 9.9488 30 1.5 74.43 1.008 30 1.5 202.54 9.0806 2 4.81 8.7963 2 1.53 0.9192 2 5.29 8.521662 3 198.78 8.6995 3 57.37 0.8508 3 287.90 8.001695 Table 2. Computational results for p-median, p-center and p-25-centrum problems for the 50-points data set in [8]. CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 17 6. Reduction of dimensionality of the SDP relaxations for multifacility location problems One of the drawbacks of using hierarchies of SDP problems to approximate the solution of our original multifacility location problem is the dimension of the SDP objects that must be used when the relaxation order increases. The size of the matrices to be considered in the SDP problems that have to be solved grows exponentially with the relaxation order. For this reason, it is important to find low rank solutions, that is to identify properties of solutions that ensure significant reduction in the sizes of the problems to be solved. In the following, we address two types of properties that ensure such dimensionality reduction: sparsity and symmetry. 6.1. Sparsity. At times the number of variables that appear in the polynomial constraints of a polynomial optimization problem can be separated in blocks so that only some of them appear together in some constraints. In those cases the SDP variables to be used can be simplified and thus, the sizes of the moment and localizing matrices are dramatically reduced. The application of this result requires the so call running intersection property [14]. Let y= (yα) be a real sequence indexed in the monomial basis Υα= (xβzηuγvδζκwψtτ, θϑ) of R[x, z, u, v, ζ, w, t, θ] (with α= (β, η, γ, δ, κ, ψ, τ, ϑ)∈Npd ×Nnp ×Nnp ×Nnpd ×Nnpd ×Nn2×Nn×Nn). Let h0(θ) := n X ℓ=1 λℓθℓ, and denote ξj:= ⌈(deg gj)/2⌉,j= 1,...,nK,νj ℓ:= ⌈(deg hj)/2⌉,j= 0,...,10; where {g1,...,gnK}are the polynomial constraints that define Kand {h1,...,h10}are, respectively, the polynomial constraints (26) - (35) in MFOMPλ. Let us denote by Ix={(j, k) : j= 1, . . . , p, k = 1,...,d},Iz={(i, j) : i= 1, . . . , n, j = 1,...,p}, It={i:i= 1,...,n},Iu={(i, j) : i= 1, . . . , n, j = 1,...,p},Iv=Iζ={(i, j, k) : i= 1, . . . , n, j = 1, . . . , p, k = 1,...,d}and Iw={(i, ℓ) : i= 1, . . . , n, i = 1,...,n}. With the above notation we can represent the index multiset that defines the set of variables of Problem MFOMPλas I=Ix∪Iz∪Iu∪Iv∪Iζ∪Iw∪It∪Iθ. Next, for a givenj, we shall refer to Ix(j) = {(j, k) : k= 1,...,d}, Iz(j) = Iu(j) = {(i′, j) : i′= 1,...,n},Iv(j) = Iζ(j) = {(i′, j, k) : i′= 1, . . . , n, k = 1,...,d}; and for a position ℓ= 1,...,n−1, Iw(ℓ) = {(i′, ℓ) : i′= 1,...,n}and Iθ(ℓ) = {ℓ, ℓ + 1}. Now, with x(Ix), z(Iz(j)), u(Iu(j)), v(Iv(j)), ζ(Iζ(j)), w(Iw), t(It) and θ(Iθ(ℓ)) we refer, respectively, to the monomials x,z,u,v,ζ,w,tand θindexed only by subsets of elements in the former sets of indices. Analogously, by Υ(˜ I), we refer to the monomials extracted from Υ only indexed by the elements in the set ˜ I. (Recall that Υ = (x, z, u, v, ζ, w, t, θ) is the set of indeterminates, as defined in Section 4.) Then, for gk, with k= 1,...,nK, let Mr(y;Ix) (respectively Mr(gky;Ix)) be the moment (resp. localizing) submatrix obtained from Mr(y) (resp. Mr(gky)) retaining only those rows and columns indexed in the canonical basis of R[x(Ix)] (resp. R[x(Ix)]). Analogously, for hs,j= 1,...,10 as defined in (26) - (35) , respectively, let Mr(y;˜ I) (respectively Mr(hjy;˜ I), be the moment (resp. localizing) submatrix obtained from Mr(y) (resp. Mr(hjy)) retaining only those rows and columns indexed in the canonical basis of R[Υ(˜ I))]. Let ˜ I(0) = Ix∪Iθ∪Itand ˜ I(j) = Ix(j)∪Iz(j)∪Iu(j)∪Iv(j)∪Iζ(j)∪Itfor j= 1,...,p and ˜ I(p+ℓ) = Iw(ℓ)∪Iθ(ℓ). Observe that (40) ˜ I(j+ 1) ∩[ j′≤j ˜ I(j′)⊆˜ I(0),∀j= 1,...,p+n−1. The above subdivision of variables allows us to partition the polynomial constraints of MFOMPλ (except those representing binary variables) into p+n+ 1 groups, F(j) and F(p+ℓ), one for each ˜ I(j) and each ˜ I(p+ℓ) for j= 0,...,p and ℓ= 1,...,n so that within each group the constraints only depend of the variables in ˜ I(j) for j= 0,...,p and ˜ I(p+ℓ) for ℓ= 1,...,n. Specifically, let F(0) = {gr(x)≥0 : r= 1,...,nK}, 18 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS and for fixed j= 1,...,p: (41) (F(j))            h3 j:= uij ≤ti+UBi(1 −zij), i = 1,...,n, h4 j:= vijk −xjk +aik ≥0, i = 1,...,n,k= 1,...,d, h5 j:= vijk +xjk −aik ≥0, i = 1, . . . , n, k = 1, .., d, h6 j:= vr ijk ≤ζs ijkur−s ij , i = 1, . . . , n, k = 1,...,d, h7 j:= Pd k=1 ζijk ≤uij, i = 1,...,n. Next, for fixed ℓ= 1,...,n−1: (42) (F(p+ℓ)) h1 ℓ:= ti≤θℓ+UBi(1 −wiℓ), i = 1,...,n, h2 ℓ:= θℓ≥θℓ+1, and (43) (F(p+n)) h1 n:= ti≤θn+UBi(1 −win), i = 1,...,n. For r≥max{r0, ν0}where r0:= max k=1,...,ℓ ξkand ν0:= max j=0,...,10 νj ℓ, we introduce the following hierarchy of semidefinite programs: (Q1sp r) inf yLy( n X ℓ=1 λℓθℓ) s.t.Mr(y;˜ I(0)) 0, Mr−ξk(gky;˜ I(0)) 0, k = 1,...,nK, Mr(y;˜ I(j)) 0, j = 1,...,p Mr(y;˜ I(p+ℓ)) 0, ℓ = 1,...,n−1, Mr−ν1 ℓ(h1 jy;˜ I(p+ℓ)) 0, ℓ = 1,...,n, Mr−ν2 ℓ(h2 jy;˜ I(p+ℓ)) 0, ℓ = 1,...,n−1, Mr−ν3 j(h3 jy;˜ I(j)) 0, j = 1,...,p, Mr−ν4 j(h4 jy;˜ I(j)) 0, j = 1,...,p, Mr−ν5 j(h5 jy;˜ I(j)) 0, j = 1,...,p, Mr−ν6 j(h6 jy;˜ I(j)) 0, j = 1,...,p, Mr−ν7 j(h7 jy;˜ I(j)) 0, j = 1,...,p, Ly( p X j=1 zij −1) = 0, i = 1,...,n, Ly( n X i=1 wiℓ −1) = 0, ℓ = 1,...,n, Ly( n X ℓ=1 wiℓ −1) = 0, i = 1,...,n, Ly(w2 iℓ −wiℓ) = 0, i, ℓ = 1,...,n, Ly(z2 ij −zij) = 0, i = 1, . . . , n, j = 1,...,p, with optimal value denoted inf Q1sp r. Theorem 10. Let K⊂Rnv1be the feasible domain of MFOMPλ. Then, with the notation above: (a) inf Q1sp r↑ρλas r→ ∞. (b) Let yr,be an optimal solution of the SDP relaxation Q1sp r. If rank Mr(yr;Ix∩It∩Iθ) = rank Mr−r0(yr;Ix∩It∩Iθ) rank Mr(yr;˜ I(j)) = rank Mr−ν0(yr;˜ I(j)) j= 1,...,p(44) rank Mr(yr;˜ I(p+ℓ)) = rank Mr−ν0(yr;˜ I(p+ℓ)) ℓ= 1,...,n(45) and if rank(Mr(yr;It)) = rank(Mr(yr;Iθ(ℓ)∩Iθ(ℓ+1))) = rank(Mr(yr;It∩Ix(j))) = rank(Mr(yr;Iθ(ℓ))) = 1for all j= 1,...,p,ℓ= 1,...,n−1. Moreover, let ∆j,ℓ := {(x(Ix(j))∗, z(Iz(j))∗, u(Iu(j))∗, v(Iv(j))∗, ζ(Iζ(j))∗, w(Iw(ℓ))∗, t(It)∗, θ(Iθ(ℓ))∗} be the set of solutions obtained by the application of the condition (44) and (45). Then, every CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 19 (x∗, z∗, u∗, v∗, ζ∗, w∗, t∗, θ∗)such that (x∗ jk , z∗ ij, u∗ ij, v∗ ijk, ζ∗ ijk, wiℓ, t∗ i, θ∗ ℓ)has indices in ˜ I(j), for j= 1,...,n+p, is an optimal solution of Problem MOMRFλ. Proof. The convergence of the semidefinite relaxation Q1sp rwas proved by Jibetean and De Klerk [9, Theorem 9] for a general rational function over a basic, closed semi-algebraic set that satisfies Archimedean Property. Here, we use that result applied to Problem MFOMPλ. Moreover, the index set of the indeterminates in the feasible set that generate localizing constraints, namely constraints (26) - (35) admits the decomposition ˜ I(0),˜ I(1),...,˜ I(p+n) that satisfies the running intersection property [14]. Indeed, the index sets I={1,...,nv1}and J={1,...,nK+nc1}are partitioned into sets {˜ I(j)}p j=0 ∪ {˜ I(p+ℓ)}n ℓ=1 and {F(j)}p j=0 ∪ {F(p+ℓ)}n ℓ=1, respectively, satisfying: (1) {F(·)}are disjoint sets for all jand ℓ. (2) For every j= 0, . . . , p, the constraints in the set F(j) only involve variables in the set ˜ I(j) and for every ℓ= 1,...,n, the constraints in the set F(p+ℓ) only involve variables in the set ˜ I(p+ℓ). (3) The objective function fcan be written as f= n X ℓ=1 λℓθℓwhere λℓθℓ∈R[Υ(˜ I(p+ℓ)] for ℓ= 1,...,n. (4) The decomposition of the index set of variables satisfies: •˜ I(j)∩˜ I(j′) = Itfor j, j′= 1,...,p with j6=j′. •˜ I(j)∩˜ I(p+ℓ) = ∅for j, 1,...,p,ℓ= 1,...,n. •˜ I(p+ℓ)∩˜ I(p+ℓ′) = ∅for ℓ, ℓ′= 1,...,p with ℓ6=ℓ′−1, ℓ′, ℓ′+ 1. •˜ I(p+ℓ)∩˜ I(p+ℓ+ 1) = Iθ(ℓ)∩Iθ(ℓ+ 1) for ℓ= 1,...,n−1. •˜ I(0) ∩˜ I(j) = It∪Ix(j) for j= 1,...,p. •˜ I(0) ∩˜ I(p+ℓ) = Iθ(ℓ) for ℓ= 1,...,n−1. Hence, it is clear that: ˜ I(j+ 1) ∩Sj′≤j˜ I(j′)⊆˜ I(0),∀j= 1,...,p+n−1. Therefore, the result follows by combining [14, Theorem 3.2] and [9, Theorem 9] .   The above theorem allows us to approximate and solve the original problem MOMRF0 λby its relaxation Q1sp rup to any degree of accuracy by solving block diagonal (sparse) SDP programs which are convex programs for each fixed relaxation order rand that can be solved, up to any given accuracy, in polynomial time with available open source solvers as SeDuMi, SDPA, SDPT3, etc. Observe that the reduction in the number of variables of the semidefinite programs is remarkable. For instance, for the relaxation of order rfrom O(nv2r 1) to O((p+n+ 1) nv1 p+n+1 2r). 6.2. Symmetry. In this section, we describe how to exploit the symmetry of Problem MFOMPλto construct another much simpler SDP relaxation. This relaxation is based on the invariance of this problem under the action of the symmetric group applied to the indices of the facilities. The general framework and theoretical details about the reduction of dimensionality of polynomial optimization problems based on the invariance under general compact groups are given in [23]. In this section we are interested in applying particular reductions to Problem MFOMPλbased on the invariance of such a problem under the symmetric group. We denote by Spthe symmetric group on pvariables that represent the pfacilities that want to be located. Note that the jlabel established in our formulation for the facilities is arbitrary and that several optimal solutions appear when the facilities are re-labeled using a different number for them. Hence, if x∗ 1,...,x∗ pis a set of optimal facilities for our problem, x∗ σ(1),...,x∗ σ(p)is also a set of optimal facilities for any σ∈ Sp. In what follows we want to use this symmetry of the decision variables to reduce the sizes of the matrices 20 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS involved in the hierarchy of semidefinite programs that converge to the optimal solution when the moment approach is applied. Recall that the complete set of variables of MFOMPλis (x, z, u, v, ζ, w, t, θ). We also denote by N=d+ 2n+ 2nd and M=n(n+ 2). Note that the overall number of variables is nv1=Np +M. We will apply symmetry results when permuting the j-indices in the set of variables Υ = {x, z, u, v, ζ} and keeping w,tand θinvariant. Hence, we consider the following action ϕover Rp: ϕ:Sp×Rp→Rp defined as ϕ(σ, (y1,...,yp)) = (yσ(1),...,yσ(p)) for any σ∈ Spand y∈Rp. With this action, we can define the following action over the overall set of variables of our problem: ϕΥ:Sp×RNp+M→RNp+M defined such that ϕΥmaps (σ, (x, z, u, v, ζ, w, t, θ)) into (ϕ(σ, x(Ix(1))),...,ϕ(σ, v(Iv(i, k))), ϕ(σ, ζ(Iζ(i, k))), w(Iw), t(It), θ(Iθ)), i.e., permuting the indices associated with facilities in the decision variables (the j-index). Hence, from the definition of ϕ, and denoting for each pair of actions ϕand ψof the symmetric group Spover Rp,ϕ⊕ψ:Sp×Rp+p→Rp+pas ϕ⊕ψ(σ, (y, y′)) = (ϕ(σ, y), ψ(σ, y′)), we get the following result: Lemma 11. ϕΥ=ϕ⊕N · · · ⊕ϕ⊕1M. We say that a polynomial p(x) is invariant under an action ϕ:Sp×Rn→Rnif p(ϕ(σ, x)) = p(x), for all σ∈G. A polynomial optimization problem is said invariant under ϕif both the objective function and the constraints are invariant under the action. Hence, it is straightforward to check that the objective function and constraints that define Problem MFOMPλare invariant under the action of ϕΥover the set of variables. Lemma 12. Let Spbe the symmetric group on the set {1,...,p}. Then, (MFOMPλ)is invariant under ϕΥ. Furthermore, in practice we are interested in applying not only the symmetry results but also the sparsity results given in Section 6.1. In this point, note that the sparsity results are not affected by the symmetry reduction presented in this section since the action ϕΥmaps the blocks F(0), F(p+ℓ) for all ℓ= 1,...,n into themselves and the block F(j) for j= 1,...,pis permuted with F(σ(j), l) when a fixed permutation σis given. Hence, both reductions can be applied to our problem. The results on the reduction of dimensionality by symmetry are based on the Theory of Representations, in particular on the decompositions of the symmetric group Spinto irreducible Sp-modules (the interested reader is refereed to [28] fur further details about the general theory for finite groups). Note that our action is somehow special because of its construction as a direct sum of actions. We show in the following result that once a decomposition into irreducible representations is computed, we can easily compute the decomposition of convenient modifications of the original representation. Lemma 13. Let p, K, N ∈N, and ρ:Sp→GL(V)a representation of Sp. Consider ρ=ρ1⊕ · · ·⊕ ρk a decomposition into irreducible representations of Sp. Then, the representation ˜ρ= 1K⊕Nρ :G→ GL(VK+Np),˜ρ(σ) = Diag(IK, ρ(g),N ···, ρ(g)) can be decomposed into irreducible representations as: ˜ρ= 1K⊕Nρ1⊕ · · · ⊕ Nρk where Nρi=ρi⊕N · · · ⊕ρi, for all i. Proof. Clearly, each representation in the decomposition of ˜ρis irreducible by hypothesis. Furthermore, since ρ=ρ1⊕ · · · ⊕ ρk, 1K⊕Nρ1⊕ · · · ⊕ Nρk= 1K⊕N(ρ1⊕ · · · ⊕ ρk) = 1K⊕Nρ = ˜ρ.  CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 21 By Maschke’s Theorem (see [25, Thm 1.5.3]) applied to the symmetric group, every Sp-module V is a direct sum of irreducible G-submodules of V, i.e., (46) V∼ = s M i=1 Viwith irreducible Sp-submodules Vi. Each irreducible Sp-submodule might occur several times in the direct sum. Recall that a scalar product h·,·i on R[X] is Sp-invariant if hg, fi=hgσ, fσifor every f, g ∈R[X] and every σ∈ Sp. Assume a decomposition of R[X] like in (46), consider Vi=Wi1⊕ · · · ⊕ Wiηiand pick any bi,1,1∈ Wi1. Then using the fact that the Wij are isomorphic we can find a vector bi,j,1∈Wij such that φi,j(bi,j,1) = bi,j+1,1, where φi,j is a Sp-isomorphism that maps Wi,j to Wi,j+1. Now using for example Gram-Schmidt every bi,j1can be extended to an orthonormal basis of Wij. We will call such a resulting basis B={b1,1,1,...,bh,ηh,νh}asymmetry-adapted basis of R[X]. We detail now how to compute the decompositions of representations of the symmetric group, the symmetry-adapted bases and how to apply those decompositions to solve Problem MFOMPλ. First of all, we concentrate on the problem of determining irreducible representations and symmetry adapted bases of R[Y] = R[Y1,...,Yp] for the symmetric group Sp. The irreducible representations of Spare in bijection with the partitions of p. Thus, in order to construct the suitable moment matrix that split this structure, we need a decomposition of the ring of polynomials into Sp-irreducible components. The classical construction of Specht based on the theory of tableaux allows this representation [30]. Let λ⊢pbe a partition of p, i.e., a sequence of non increasing positive integers λ1,...,λkwith Pk l=1 λl=p. Given two partitions λ, µ ⊢p, we say that λdominates µ, and we write λDµ, if Pi l=1 λi≥Pi l=1 µifor all i. A Young tableaux for a partition λ⊢pconsists of as many rows as components in λ, each of them with as many columns as the number in the corresponding component in λ. The entries are the elements in {1,...,n}, and each of these numbers appear exactly once. A generalized Young tableau of shape λ⊢pand content µ⊢nis a Young tableau for λwhose entries are {1,µ1 . . ., 1},...,{ℓ, µℓ . . ., ℓ}. A generalized Young tableau is called semistandard if its rows are non increasing and its columns are strictly increasing. Given a partition λ⊢p, and a λ-Young tableau t, the class of equivalence of t(by rows) is denoted by {t}and is called a tabloid. The permutation module Mλis then the Sp-module defined by C{{t1},...,{tℓ}}, where {{ti}ℓ i=1}is the complete list of λ-tabloids. Two tableaux are said equivalent if the corresponding rows and columns of the two tableaux contain the same numbers. The equivalence class of a tableau Tis denoted by [T]. The column stabilizer of a λ-tableau tis Cstabt=SC1×· · ·×SCνwhere C1,...,Cνare the columns of the tableau and SCiis the symmetric group on Ci. The polytabloid associated to a tabloid Tis defined by: et=X σ∈CStabT sgn(σ)σ({T}). The irreducible representations of the symmetric group Spare in one-to-one correspondence with the partitions of p, and they are given by the Specht modules. The Specht module of λ⊢p,Sλis the submodule of the permutation module Mλspanned by the polytabloids eT. The dimension of Sλ, dim(Sλ), is the number of standard Young tableaux for λ. On the other hand, for β∈Np, let us denote R{Yβ}={Yσ(β):σ∈ Sp}. Then, it is clear that R[Y]≤r= r M s=0 M β∈Np s R{Yβ}, where Np s={β∈Np:|β|=s}. With the above decomposition, it would be enough then to construct a decomposition of R{Yβ} into Sp-irreducible components, Let ξ∈Np. We denote by bξ∈Nqthe vector of distinct components of ξordered (non increasingly) according to the multiplicity of the occurrence in ξ. Then, we construct µ∈Nqas µj= #{i∈ 22 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS {1,...,p}:ξi=bξ j}. For example, for ξ= (4,2,2,4,7,4) ∈N6, we get that bξ= (4,2,7) and µ= (3,2,1) since 4 appears 3 times in ξ, 2 appears twice and 7 once. We analyze now how to express R{Y}in terms of irreducible Sp-invariant modules. Let bβas defined above. For a partition λ⊢p, a semi-standard λ-tableau tλand Ta generalized Young tableau with shape λand content µβwe define: Y(tλ,T )=Y kY (r,c) Ybβ T(r,c) tλ(r,c),k where, T(r, c) is the element in its c-th column and r-th row. Next, for each column cof the λ-tableaux, we construct the Vandermonde determinant as: V anT c= det      Ybβ T(1,c) tλ(1,c)··· Ybβ T(1,c) tλ(q,c) . . ..... . . Ybβ T(q,c) tλ(1,c)··· Ybβ T(q,c) tλ(q,c)      With this determinant, we construct the polynomial: stλ,T =Y c V anT c, and finally the Specht polynomial: Stλ,T =X S∈[T] stλ,S. For a partition µ⊢p,Mµis the Sp-module generated by the complete list of µ-tabloids. Sµis the submodule of Mµgenerated by the polytabloids eT=Pσ∈CStabTsgn(σ)σ{T}for each Young tableau for µ. The following result states that the Specht polynomials generate a submodule of R{Yβ} equivalent to the Specht module. Lemma 14. Let Tbe a generalized Young tableau with shape λ⊢pand content µβ. The generalized Specht polynomials S(tλ,T )generate an Sp-submodule of R{Yβ}which is isomorphic to the Specht module Sλ. With the above results, we get the following result which is proven in [23]. Theorem 15. Let β∈Np 0with p X i=1 βi=rand shape µβ. Then: R{Yβ}=M λ☎µβM T∈Tλ,µ R{Stλ,T } where tλdenotes the unique λ-tableau with increasing rows and columns and Tλ,µ the set of semistandard generalized Young tableaux of shape λand content µ. Once the general theory for decomposing the standard symmetric group is detailed, our action ϕ needs to be treated slightly different since our set of variables has Np+Melements and the symmetric group has p. To construct the basis of invariant polynomials (with degree at most the desired relaxation order) in the complete set of variables of MFOMPλ, once we know a basis of invariant polynomials in pvariables under Sp, we reproduce such a basis on each of the set of variables where the action is ϕ(i,j,ℓ)is non trivial and completed it with the standard monomial basis where the action is defined as the identity. Lemma 16. Let Bk(Y)be a symmetry-adapted basis of R[Y1,...,Yp]of degree at most kand Bst(X)the standard monomial basis of R[w(Iw), t(It)] with degree at most k. Then, the elements of a symmetryadapted basis of R[x, z, u, v, ζ, w, t, θ]are of the form: CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 23 b=bx1···bvn,d ·b′ where bxk∈ Bk(x(Ix(k))),bzi∈ Bi(z(Iz(i))),bui∈ Bk(u(Iu(i))),bvi,k ∈ Bk(v(Iv(i, k))), for i= 1,...,n,k= 1,...,d, and b′∈ Bst(X)and such that deg(b)≤k. Proof. The result follows from the equivalence between R[(x, z, u, v, ζ, w, t, θ)] and the construction of such a ring by the extension R[x(Ix(1))] ···[ζ(Iζ(n, d))][w(Iw), t(It), θ(Iθ)], where for a given multivariate polynomial ring K[Y], and a set of variables Y′, the polynomial ring K[Y][Y′] is defined as the set of polynomials in the variables Y′with coefficients in K[Y]. Hence a basis for R[Υ(0,0)] can be constructed by iteratively multiplying the element in bases for the polynomial rings R[x(Ix(1))],...,R[ζ(Iζ(n, d))] and R[w(Iw), t(It), θ(Iθ)]. For instance, let f∈R[(x, z, u, v, ζ, w, t, θ)]. Then, by dividing fby the standard monomial basis with term ordering ≻such that x1≻ · · · ≻ xd≻ · · · ≻ ζnd ≻w≻t≻θ, it can be written as f=qx1 1···qxd 1q′ 1+qx2 2···qxd 2q′ 2+···+qxd dq′ d+q′ 0 where qxk j∈R[x(Ix(k))], for k= 1,...,d, and q′ i∈R[w(Iw), t(It), θ(Iθ)], for j= 0,...,d. Now applying each of the bases to each polynomial, we get the desired expression. In the polynomial ring R[w(Iw), t(It), θ(Iθ)] no symmetry is applied, so the standard basis is used. For the first drings, the symmetry adapted basis is used.   Once the symmetry-adapted bases of our problem are computed, the symmetry-adapted SDP- relaxation must be stated. Note that, we have a symmetry-adapted basis for each shape λ⊢n. Each of those bases will give as a block in the overall moment matrix. In order to do that, we consider a Sp-linear map, i.e., a linear map Lsym :R[Υ] →Rsuch that Lsym(f(X)) = Lsym(f(ϕ(σ, X))) for all σ∈ Sp. We also define the following bilinear form, for any g∈R[Υ]: Lsym g:R[X]×R[X]−→ R (p, q)7→ Lsym  1 pX σ∈Sp p(ϕ(σ, X)) ·q(ϕ(σ, X)) ·g  For the sake of simplicity, we will use the following Sp-linear map for our computations: for each subset of variables {Y1,...,Yp}in {x(Ix(1)),...,x(Ix(d))),...,v(Iv(i, k)), ζ(Iζ(i, k))}we fix Lsym(Y1) = yv∈R. Since the mapping must be invariant under Spand there is always a permutation σ∈ Spthat maps 1 in σ(1) ∈ {1,...,p}, we know that Lsym(Yj) = yvfor j= 1,...,p. With the about settings, we define the symmetry-adapted moment matrices as follows: Corollary 17. For r∈N, the r-th symmetry-adapted moment matrix Msym r(y)is of the form Msym r(y) = M λ⊢n Msym r,λ (y), where Msym r,λ (y) is the moment matrix constructed for symmetry-adapted basis for fixed λ⊢nas in the standard case (see Section 2). Finally, we define the symmetry-adapted relaxation (47) Qsym r: infyLsym(p) Msym r(y)0, Msym r−⌈deg gj/2⌉(gky)0, k ≤j≤nK Msym r−⌈deg hj/2⌉(hjy)0,1≤j≤nc1 with optimal value denoted by inf Qsym r(and min Qsym rif the infimum is attained). Remark 18. The symmetry-adapted setting defined above can give a significant reduction of the SDPs objects that need to be calculated. Indeed the number of variables involved equals the size of Bk. Furthermore the symmetry-adapted moment matrix is block diagonal and the size of each block equals ηi. 24 CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS In this setting, Proposition 2 can be reformulated as follows. Theorem 19. Assume that the Archimedean Property 2 holds and let (Qsym r)r≥k0be the hierarchy of SDP-relaxations defined in (47). Then (inf Qsym r)r≥k0is a monotone non-decreasing sequence that converges to p∗, i.e., inf Qsym r↑p∗as r→ ∞. Example 20. Let us consider a toy example for Problem MFOMPλwith n= 3 demand points, in dimension d= 2,p= 2 facilities to be located and relaxation order k= 2. The set of variables of our problem is Υ=(x11, x21, x12, x22, z11, z12, z21, z22, z31, z32, u11, u12, u21, u22, u31, u32, v111, v121, v112, v122, v211, v221, v212, v222, v311, v w13, w21, w22, w23, w31, w32, w33, t1, t2, t3, θ1, θ2, θ3) We apply the symmetry results to each of the subsets of variables where the facility appears, i.e.: {x1k, x2k}k= 1,2,(SUBSET x·k) {zi1, zi2}i= 1,2,3,(SUBSET zi·) {ui1, ui2}i= 1,2,3,(SUBSET ui·) {vi1k, vi2k}i= 1,2,3, k = 1,2,(SUBSET vi·k) {ζi1k, ζi2k};i= 1,2,3, k = 1,2,(SUBSET ζi·k) Let us construct the symmetry adapted basis for any of the above subsets of variables, {Y1, Y2}. This construction will be applied to all the above 20 sets of variables. First, the components in the symmetry-adapted basis are indexed by the partitions λ⊢(2), thus λ∈ {(2),(1,1)}. The βto be taken into account are: β∈ {(0,0),(1,0),(2,0),(1,1)}with shapes µ equal to (2),(1,1),(1,1) and (2), respectively. Thus, the semistandard generalized Young tableaux for each of these shapes and contents are: •µ= (2):11and 12 •µ= (1,1): No semistandard generalized Young tableaux exists in this case. Hence, there is only one irreducible component in this case (for µ= (2)), so the symmetry-adapted basis in R[Y1, Y2]is {1, Y1+Y2, Y 2 1+Y2 2, Y1Y2} We observe that the standard monomial basis for this set of two variables has 6monomials while this basis has only four elements. Now, applying this shape to the 13 blocks of variables ( SUBSET x·k)-(SUBSET ζi·k)and adding the standard monomial basis to the remainder variables (wand t) we get that a 392-elements symmetryadapted basis with degree up to 2for our problem. The moment matrix is then a 392 ×392-size matrix whose elements are computed by applying the sym-linearization operator Lsym to the two-by-two product of the elements in the basis. Analogously to compute the localizing matrices. We consider the standard sym-linear operator that maps the variables that are in the same orbit of our action ϕi,j,ℓ to the same element. For instance, when multiplying (x11 +x21)by itself we get x2 11 +x2 21 + 2x11x21. Since x11 and x21 are in the same orbit (there is a permutation sigma that maps x11 into x21), we get that Lsym((x11 +x21)·(x11 +x21)) = 2y2,0,0,... + 2y1,1,0,.... Observe that the standard monomial basis for this problem has 861 elements (note that the number of variables is 40 and all the possible standard monomials with these variables with degree up to 2is 40+2 2), reducing considerably the sizes of the matrices for the SDP problem. This reduction is even more drastical when the number of demands points increases. Note that the standard monomial bases for each of the subsets of variables where the symmetry is applied have 6elements and it is reduced to 4by symmetry. Since this reduction is applied to thirteen sets of variables and then those elements are multiplied by the standard monomial bases for wand t(that depends of n, which is in general the larger CONTINUOUS MULTIFACILITY ORDERED MEDIAN LOCATION PROBLEMS 25 parameter of the location problem), we get that such a reduction will allow to solve larger instances of the problem. To illustrate the advantage of this symmetry reduction, in this special case, just by making some basic computations to count elements, the number of elements in the symmetry-adapted basis for 2-median planar problems with ndemand points is: n4+ 16n3+ 71n2+ 43n+ 68 2 while the number of elements in the standard basis is: n4+ 28n3+ 207n2+ 154n+ 30 2 being the difference of elements 6n3+68n2+43n+7. For instance, for 1000 demand points, the number of variables appearing in the SDP problem is reduced by 6,068,043,007 elements. 7. Conclusions We propose a novel, effective mixed integer nonlinear programming formulation for the continuous multifacility ordered median location problem for any ℓτ-norm and in any dimension. This formulation provides a unified approach for dealing with a broad family of multifacility location problems which up to now were usually solved only for some special cases and usually in low dimension. We also show that the problem can be solved by using tools from the Theory of Moments for polynomial optimization, by approximating the solution up to any desired degree of accuracy. Furthermore, such an algebraic framework allows us to prove new dimensionality reduction for the problem based on the sparsity and the symmetry of the formulation. References [1] Ahuja R.K., Magnanti T.L. and Orlin J.B. (1993).Network flows. Theory, algorithms, and applications, Prentice Hall; 1 edition, isbn=978-0136175490. [2] Blanco V., El-Haj Ben-Ali S. and Puerto J. (2013). Minimizing ordered weighted averaging of rational functions with applications to continuous location, Computers and Operations Research, 40:1448-1460. [3] Blanco V., Puerto J. and El-Haj Ben-Ali S. (2014). Revisiting several problems and algorithms in continuous location with ℓpnorms. Preprint, http://arxiv.org/abs/1312.7473. [4] Boland N., Dominguez-marin P., Nickel S. and Puerto J. (2006). Exact procedures for solving the discrete ordered median problem, Computers and Operations Research, 33:3270-3300. [5] Boyd S. and Vanderberghe L. (2004). Convex Optimization. Cambridge University Press. [6] Brimberg J., Hansen P., Mladenovic N. and Taillard E. D. (2000). Improvement and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem, Operations Research 48:444-460. [7] Drezner Z., Hamacher H.W. (2002). Facility location: applications and theory. Springer, ISBN 978-3-540-42172-6. [8] Eilon S., Watson-Gandy C. and Christofides N (1971). Distribution management: mathematical modeling and practical analysis, Operational Research Quarterly 20:309. [9] Jibetean D. and De Klerk E. (2006). Global optimization of rational functions: an SDP approach, Mathematical Programming, 106:103-109. [10] Hansen P., Mladenovic N. and Taillard E (1998). Heuristic solution of the multisource Weber problem as a p-median problem, Operational Research Letters 22:55-62. [11] Kariv O. and S.L. Hakimi (1979). An algorithmic approach to network location problems i: The p-centers, SIAM Journal of applied mathematics, 37:513-538. [12] Laraki R. and Lasserre J.B. (2012). Semidefinite Programming for min-max problems and Games, Math. Program., Ser. A, 131:305-332 [13] Lasserre J. B. (2001). Global Optimization with Polynomials and the Problem of Moments, SIAM J. Optim., 11:796- 817. [14] Lasserre J.B. (2006). Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17:822- 843. [15] Lasserre J. B. (2008). A semidefinite programming approach to the Generalized Problem of Moments. Mathematical Programming B, 112:65-92. [16] Lasserre J.B., Laurent M. and Rostalski P. (2008). Semidefinite characterization and computation of zerodimensional real radical ideals, Found. Comput. Math., 8:607-647. [17] Lasserre J.B. (2009). Moments and sums of squares for polynomial optimization and related problems, J. Global Optim., 45, 39-61. [18] Lasserre J.B. (2009). Moments, Positive Polynomials and Their Applications, Imperial College Press, London.