On the exponential cardinality of FDS for the ordered p-median problem
Abstract
We study finite dominating sets (FDS) for the ordered median problem. This kind of problems allows to deal simultaneously with a large number of models. We show that there is no valid polynomial size FDS for the general multifacility version of this problem even on path networks.
Full text
UNCORRECTED PROOF PROD. TYPE: COM PP:1-11 (col.fig.: nil) OPERES4808 DTD VER: 5.0.1 ED: Prathiba PAGN: Vidya -- SCAN: v4soft ARTICLE IN PRESS Operations Research Letters ( ) – Operations Research Letters www.elsevier.com/locate/dsw 1 On the exponential cardinality of FDS for the ordered p-median problem夡 3 J. Puertoa,∗, A.M. Rodríguez-Chíab aDept. Estadistica e Investigacion Operativa, Facultad de Matemáticas, Universidad de Sevilla, 41012 Sevilla, Spain5bFacultad de Ciencias, Universidad de Cádiz, Spain Received 4 June 2003; accepted 1 November 2004 7 Abstract We study finite dominating sets (FDS) for the ordered median problem. This kind of problems allows to deal simultaneously 9 with a large number of models. We show that there is no valid polynomial size FDS for the general multifacility version of this problem even on path networks. 11 © 2004 Elsevier B.V. All rights reserved. Keywords: Location; Networks; Finite dominating sets13 1. Introduction Network location models have been widely studied in the literature as can be seen in several textbooks17 [1,4,8,12]. Since the seminal paper by Hakimi [7], much of this work has been devoted to identify finite19 sets of points where an optimal solution of a problem must belong to. These sets, called finite dominating21 sets (FDS), reduce the search for an optimal solution of a problem to a finite set of candidates.23 夡The research of the authors is partially financed by Spanish research Grants BFM2001-2378, BFM2001-4028, BFM2004-0909 and HA2003-0121. ∗Corresponding author. Tel.: +34 95 4557940; fax: +34 95 4622800. E-mail addresses: [email protected] (J. Puerto), [email protected] (A.M. Rodríguez-Chía). 0167-6377/$ - see front matter © 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.orl.2004.11.005 In the last years, a new type of function has attracted the attention of locators: the ordered median objective 25 function. The corresponding ordered median problem allows a common algebraic analysis for a wide range 27 of location models since many of the classical problems in location theory can be formulated as some 29 of its particular instances. In the literature of location analysis, we can find a number of results con- 31 cerning the ordered median problem, for example in the continuous case, characterizations of the optimal 33 solution set and some algorithms have been obtained in [5,6,14–18]. On networks, finite dominating sets 35 are known for particular instances of the problem, see [10,11,13,19]. Recently, also the discrete version of 37 this model has been studied in [2,3]. (This objective function was already introduced in [21] in the context 39 of multi-criteria decision making.)
UNCORRECTED PROOF 2J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – OPERES4808 ARTICLE IN PRESS Nevertheless, it has been an open problem whether1 polynomial size FDS exist for the general version of this problem even on path networks. In this paper, we3 show that such sets do not exist. An overview of the literature, involving characteri-5 zations of FDS, shows a lot of papers that succeed in finding this type of sets for different versions of lo-7 cation models. Ref. [9] is an excellent paper on this subject that characterizes FDS for a large number of9 location problems. However, we are not aware of any paper that states a negative result concerning existence11 of a polynomial size FDS for a given problem. The main result in this paper proves that there exists13 a path graph with nnodes satisfying the following property: there is a family of O(nn)ordered n 4-median15 problems defined on the above path graph, such that: (1) each problem has a unique optimal solution and (2)17 each optimal solution contains an element (facility) not included in any other solution. Therefore, in general,19 the multifacility ordered median problem cannot have polynomial size FDS.21 To introduce the problem formally, some notation is needed. Let G=(V, E) denote a path graph where V=23 {v1,...,v n}is the set of nodes (demand points) and Ethe set of edges. Suppose without loss of generality25 that the nodes are points on the real line, satisfying v1⩽...⩽vn. Therefore, we denote by [vi,v i+1]27 the edge that joins the nodes viand vi+1 for i= 1,...,n−1. Let A(G) be the interval [v1,v n], then29 the distance from two points xand yin A(G) is simply d(x,y) =|x−y|. In the same way, the distance from31 a node to a set with ppoints, Xp={x1,...,x p}⊆ A(G), is defined as33 d(v,Xp)=min i=1,...,p d(v,xi)=min i=1,...,p |xi−v|. Notice that A(G) is a metric space which distance35 function is induced by the edge lengths, see [20]. We consider a set of non-negative weights37 {w1,...,w n}, called w-weights, where the weight wiis associated to the node viand represents the39 intensity of the demand at this node, for i=1,...,n. Let be a permutation of the set {1,...,n}satis-41 fying that w1d(v1,X p)⩽w2d(v2,X p) ⩽...⩽wnd(vn,X p). 43 Foragiven=(1,...,n), vector of non-negative components, called -weights, the p-facility ordered 45 median function (the ordered p-median function) on Gis defined as 47 F(Xp):= n i=1 iwid(vi,X p) := n i=1 iwid(vi,X p), (1) where is a permutation of {1,...,n}such that 49 j<kif wjd(vj,X p)⩽wkd(vk,X p)for all j,k ∈ {1,...,n}.51 The -weights are the parameters that define the objective function and depending on the values of these 53 parameters we obtain different problems. In fact, the ordered p-median problem allows to model the p-55 facility versions of the median (i=1,∀i), center (n=1,i=0,∀i= n), -centdian (n=1,i=57 ,∀i= n), k-centrum (i=1, for i=n−k+ 1,...,n and i=0 for i=1,...,n−k), k-trimmed 59 p-mean location model (we omit the k 2smallest and k 2largest weighted distances, to simplify assume kis 61 even, 1=... =k 2=0, k 2+1=... =n−k 2=1, n−k 2+1=...=n=0), etc. Notice that we do not 63 impose any assumption on the monotonicity of the - weights, therefore we do not restrict to the convex nor 65 the concave cases, see [13]. Although we have already used the concept of FDS, 67 in what follows, we give its formal definition. Definition 1.1. Let G=(V, E) be a graph with n69 nodes and positive edge lengths. Let w1,...,w nbe non-negative reals and =(1,...,n)a vector of 71 non-negative components. A finite subset Xof A(G) is an FDS, for the multifacility ordered median problem, 73 if for any integer pand w-weights associated to vifor i=1,...,n, either wior 0 there is an optimal solution, 75 Xp, of the respective ordered p-median problem, such that Xp⊂X.77 Obtaining an FDS for this model allows the development of different types of algorithms to solve 79 it. Therefore, recently much effort has been devoted to obtain FDS for the ordered median problems (see 81 [10,11,13,19]). In the following, we recall several 83
UNCORRECTED PROOF OPERES4808 ARTICLE IN PRESS J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – 3 sets used to define FDS for particular instances of the1 problem. A point x∈A(G) is in equilibrium with respect to3 the nodes vk,v l,vk= vl, if: wkd(vk,x)=wld(vl,x). It is important to realize that there may exist subedges5 in equilibrium with respect to two nodes. We denote by EQ the set consisting of the nodes of G, the points in7 equilibrium which are isolated and the extreme points of the subedges in equilibrium. Moreover, we consider9 the following sets: Y={y∈A(G) :wid(vi,y)=wjd(vj,z), vi,v j∈V, z ∈EQ}, T={X2=(x1,x 2)∈A(G) ×A(G) :∃vr,v s served by x1and vr,v sserved by x2,such that wrd(vr,x 1)=wrd(vr,x 2)and ws d(vs,x 1)=wsd(vs,x 2). Moreover, if wr=wr and ws=ws,then the slopes of the functions d(vr,·)and d(vs,·), in the edge that x1belongs to, must have the same signs at x1 and the slopes of the functions d(vr,·) and d(vs,·), in the edge that x2belongs to, must have different signs at x2}. 11 Ref. [13] proves that for 1⩾...⩾n⩾0 the node set Vconstitutes an FDS for the multifacility13 ordered median problem. For arbitrary non-negative -weights, it also obtains that EQ is an FDS for the15 single-facility ordered median problem. Ref. [11] studies the multifacility ordered median17 problem where the -weights are defined as a=1=...=k= k+1=...=n=b,19 forafixedk, such that, 1⩽k<n. It proves that the set Yis an FDS for this problem.21 Ref. [19] proves that the set F=(EQ ×Y)∪T⊂ A(G) ×A(G) contains an optimal solution of the or-23 dered 2-median problem in any network for any choice of -weights.25 Ref. [10] gives an FDS for the single facility ordered median problem with general node weights (the27 w-weights can be negative). Moreover, for the case of a directed network with non-negative w-weights,29 it proves that there is always an optimal solution in V.31 However, none of these papers deals with the general case of the multifacility ordered median problem.33 In fact, these papers impose very restrictive hypotheses such that their respective results cannot be ex- 35 tended any further. Indeed, only [13] and [11] consider p-facility problems for any p>2, although for partic- 37 ular cases: [13] when the -weights are given in non increasing order and [11] when the -weights satisfy 39 a=1=...=k= k+1=...=n=b, for some k,1⩽k<n. 41 2. On the exponential cardinality of FDS for the p-facility ordered median problem 43 In this section we prove that there is no polynomial size FDS for the general ordered p-median problem 45 even on path networks. In order to do that we consider a path graph Gwhere V={v1,...,v 2p}, being pafixed 47 natural number, v1=0, v2=2, v2i−1=v2i−2+Mand v2i=v2i−1+2i, for i=2,...,p, and M=4p i=12i+149 (a sufficiently large number) (see Fig. 1). The w-weights associated to the nodes are assumed 51 to be equal to one and the -weights are given as follows: 53 1=0,2=3=2p, 4=pand i=22p+1 22p+1(i−2+i−1), for i=5,...,2p. (2) Under these conditions our goal is to find ppoints 55 on A(G),Xp={x1,...,x p}, solving the following problem: 57 min Xp⊆A(G) F(X p):= 2p i=1 id(vi,X p), (3) where is a permutation of {1,...,2p}, such that, 59 k<lif d(vk,X p)⩽d(vl,X p)for each k,l ∈ {1,...,2p}. (In this case, we say that the -weight 61 iis assigned (allocated) to the node vi.) Remark 2.1. Notice that, the -weights defined in (2) 63 satisfy the relationships: 2 max{i−2,i−1}>2i>i−2+i−1, for all i=5,...,2p, (4) 65 24=2=3>1=0,(5) 22>4+5+8.(6) 67
UNCORRECTED PROOF 4J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – OPERES4808 ARTICLE IN PRESS Fig. 1. Illustration of the graph in Section 2. Moreover, the components of the vector =1 (1,...,2p)satisfy the following chain of inequalities:3 2=3>...>2p−3>2p−1>2p>2p−2 >2p−4>...>4>1=0. Therefore 5 (i) 2j+1>2(j+1)+1,for j=1,...,p−2 (the sequence of -weights with odd indexes (>1) is7 decreasing). (ii) 2(j+1)>2j,for j=2,...,p −1 (the se-9 quence of -weights with even indexes (>2) is increasing).11 (iii) 2j−1>2i,for any i, j ∈{2,...,p}(a - weight with odd index (>1) is always greater13 than any other with an even index (>2)). (iv) 2j<k,ifk>2j,j>1 and 2j+1>k,if15 k>2j+1, j⩾1. We will prove that the optimal policy to solve Prob-17 lem (3) is to locate a service facility on each edge [v2i−1,v 2i]for i=1,...,p and to assign ito vifor19 i=1,...,2p. Lemma 2.1. If Xp={x1,...,x p}is an optimal so-21 lution of Problem (3) then xi∈[v2i−1,v 2i]for i= 1,...,p.23 Proof. First, we prove that the nodes v2iand v2i+1 for i=1,...,p, are not covered by the same service25 facility. Suppose on the contrary that there exists j∈ {1,...,p}, such that, v2jand v2j+1are served by the27 same service facility x∈Xp. This implies that the following terms would appear in the objective function:29 2jd(v2j,x)+2j+1d(v2j+1,x). Notice that d(v2j,x)+d(v2j+1,x)⩾M. Moreover 31 1. If both 2jand 2j+1are different from 1, we have that 2j⩾4,2j+1⩾4, and at least one of these33 inequalities is strict. 2. If 2j=1, then d(v2j+1,x)⩾M/2. In a similar way, 35 the case 2j+1=1 implies that d(v2j,x)⩾M/2. In all cases 37 2jd(v2j,x)+2j+1d(v2j+1,x)>M−1 24 =24 p i=1 2i=2 p i=1 2i. The inequality above contradicts the optimality of Xp.39 Indeed, consider X p={x 1,...,x p}such that x iis located at the midpoint of the edge [v2i−1,v 2i]for 41 i=1,...,p. Then, since 2⩾ifor i=1,...,2p, we have that F(X p)⩽2p i=12i. Therefore, v2iand 43 v2i+1for i=1,...,p, can not be covered by the same service facility. 45 Hence, in what follows, we can assume without loss of generality that each service facility xicovers the 47 demand of v2i−1and v2ifor i=1,...,p. The fact that xi∈[v2i−1,v 2i]follows directly 49 from the isotonicity property of the ordered median objective with nonnegative -weights (see Theo- 51 rem 1 in [5]). Indeed, if xi/∈[v2i−1,v 2i]for some i, i=1,...,p,wemovexito its closest node in the 53 interval [v2i−1,v 2i], the new vector of distances of {v1,...,v 2p}from the servers is smaller than the old 55 vector. Remark 2.2. Since all the w-weights are equal to one, 57 by symmetry arguments and without loss of generality, in what follows we only consider solutions of this 59 problem satisfying that d(v2i−1,x i)⩽d(v2i,x i)for i=1,...,p, and consequently, by the structure of the 61 graph, d(v2i,x i)⩽d(v2i+2,x i+1)for i=1,...,p−1. Hence, 63 (i) 2i−1<2ifor i=1,...,p, (ii) 2i<2i+2for i=1,...,p−1. 65 The above assertions imply that 2p=2p. Moreover, by Lemma 2.1 and for the sake of the readability, we 67 can represent the graph of Fig. 1 as a graph with only
UNCORRECTED PROOF OPERES4808 ARTICLE IN PRESS J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – 5 Fig. 2. The new representation of the graph where 2i>2i−1, for i=1,...,p and 2i+2>2i, for i=1,...,p−1. pedges where the edges with length Mare omitted1 (see Fig. 2). Theorem 2.1. If Xpis an optimal solution of Problem3 (3) then i=ifor i=1,...,2p. Proof. First, we prove that 1must be assigned to5 v2i−1for some i,i=1,...,p. Indeed, if 2i=1 for some i,i=1,...,p then, by Remark 2.2.i,7 2i−1<1. However, this is impossible because 2i−1∈{1,...,2p}.9 Second, by Lemmas A.1 and A.2, for k=1,...,p, we have that 2kis assigned to v2ifor some i,i=11 1,...,p. Moreover, Remark 2.2(ii), implies that 2i= 2i, (i.e. 2iis assigned to v2i) for i=1,...,p. There-13 fore, using a recursive argument and Remark 2.2(i), we obtain that 1=1 (i.e. 1is assigned to v1), 3=315 and so on. Thus, the result follows. Remark 2.3. The above result has been proven as-17 suming that |v2i+1−v2i+2|=2|v2i−1−v2i|. However, the reader may notice that the result also holds when-19 ever |v2i+1−v2i+2|⩾2|v2i−1−v2i|. In order to disprove the polynomial cardinal-21 ity of any FDS for the multifacility ordered median problem, we consider the graph Gof Fig.23 1(assume that pis even). Let P={1,...,p} and J={j1,j 2,...,jp 2−1,jp 2}⊆P, such that, 25 1=j1<j 2<...<jp 2−1<jp 2=p. On the graph Gwe formulate the following (p 2)-facility ordered median27 problem: 29 min Xp 2 ⊆A(G) 2p i=1 iw id(vi,Xp 2), (7) where =(0,...,0,1,...,p), such that, iis de- 31 fined by (2) for i=1,...,p,w 2j−1=w 2j=1 for each j∈Jand w 2j−1=w 2j=0 for each j∈P\J.33 Moreover, since w 2j−1d(v2j−1,Xp 2)=w 2jd(v2j, Xp 2)=0∀j∈P\J, the first ppositions of the 35 ordered sequence of weighted distances between each node and its service facility are given by 37 w 2j−1d(v2j−1,Xp 2),w 2jd(v2j,Xp 2)with j∈P\J. (Indeed, these positions are always zeros.) Thus, we 39 can assume without loss of generality that the - weights allocated to v2j−1and v2jfor any j∈P\Jare 41 the first pcomponents of the vector , that is, 0. Notice that the nodes v2j−1and v2j∀j∈P\Jare 43 not really taken into account in the objective value because w 2j−1=w 2j=0. Thus, using Lemma 2.1, 45 this problem reduces to locate p/2 service facilities on a graph with p/2 edges. Indeed, if we consider 47 V= p 2 i=1,ji∈J {v2ji−1,v 2ji}:= p 2 i=1 {v 2i−1,v 2i} and the path graph Ginduced by the set of nodes V,49 Problem (7) can be reformulated as min Xp 2 ⊆A(G) p i=1 id(v i,Xp 2). (8) 51
UNCORRECTED PROOF 6J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – OPERES4808 ARTICLE IN PRESS Observe that the components of the vector =1 (1,...,p)coincide with the first pentries of (2) and therefore they satisfy (4)–(6). In addition, i∈3 {1,...,p}and i<jif d(v i,Xp 2)⩽d(v j,Xp 2)(the w-weights are all equal to one). 5 Theorem 2.2. If Xp/2is the optimal solution of Problem (7) then xi=v2ji−1+ziwith z1=1and zi=7 2ji−1−zi−1for i=2,...,p/2. Proof. To prove this result we consider the equiva-9 lent formulation of Problem (7) given in (8). Applying Theorem 2.1 and Remark 2.3, we get that the -weight11 allocated to the node v iis ifor i=1,...,p. In addition, the solution Xp 2satisfies the relation- 13 ship d(v 2i,x i)=d(v 2i+1,x i+1)for i=1,...,p/2−1. Indeed, since 2iand 2i+1are assigned to v 2i 15 and v 2i+1, respectively, for i=1,...,p/2−1, then d(v 2i,x i)⩽d(v 2i+1,x i+1). Moreover, xi+1 17 must be located as close as possible to v 2i+1be- cause 2i+1>2i+2, which in turn implies that19 d(v 2i,x i)=d(v 2i+1,x i+1). Next, we prove that d(v 1,x 1)=1. Notice that,21 by Remark 2.2, we have that d(v 1,x 1)⩽1. If d(v 1,x 1)<1 then we would move x1towards v 2a23 small enough amount, . This movement would allowustomovexitowards v 2i−1for any even index25 i=2,...,p/2, and xjtowards v 2jfor any odd index j=2,...,p/2 by the same amount ; without27 any reassignment of the -weights. These movements would produce the following change in the objective29 function: −(2−1)+ p 2 k=2 (−1)k−1(2k−1−2k) . 31 This amount is negative because −(2−1)is negative and {2k−1−2k}k⩾2is a decreasing sequence of33 positive values, that is, 2k−1−2k>2k+1−2k+2>0 for k=1,...,p/2. However, this is not possible since35 Xp 2is optimal. Therefore, we obtain that x1=v 1+ 1 and that Xp 2is the unique solution satisfying that 37 d(v2i−1,x i)⩽d(v2i,x i)for i=1,...,p.(See Remark 2.2.) Finally, since d(v 2i,x i)=d(v 2i+1,x i+1)for i=39 1,...,p/2−1, the result follows. Our next result proves that there is no polynomial 41 size cardinality FDS for the multifacility ordered median problem. The proof consists of building a fam- 43 ily of O(nn)problems on the same graph with different solutions (each solution contains at least one point 45 not included in the remaining), nbeing the number of nodes. 47 Theorem 2.3. There is no polynomial size FDS for the multifacility ordered median problem.49 Proof. Consider Problem (7), by Theorem 2.2 and Remark 2.2, for each choice of the set J⊆P,51 we have an unique optimal solution satisfying that d(v2i−1,x i)⩽d(v2i,x i)for i=1,...,p, such that, 53 the service facility located on the edge [v2p−1,v 2p] has a different location, recall that jp/2=p. Thus, 55 since there are 2p−2 p 2−2different choices of the set J, any FDS for the considered problem contains at least 57 2p−2 p 2−2elements. Therefore, we have found a family of problems for 59 which a valid FDS is at least of order O(nn)where n denotes the number of nodes (recall that in our case 61 n=2p). Remark 2.4. Problem (7) is formulated based on the 63 concrete given in (2). Nevertheless, a detailed reading of the proofs shows that any satisfying (4)–(6) 65 would be also valid. 3. Concluding remarks 67 This paper proves that polynomial size FDS cannot exist for the multifacility ordered median problem. 69 However, it is still an open question whether polynomial size FDS may exist for the convex version 71 of this problem (-weights given in non-decreasing order). 73 Acknowledgements The authors would like to thank professor Arie Tamir for his valuable comments on an earlier version of this paper, as well as to an anonymous referee for his careful reading of the manuscript.
UNCORRECTED PROOF OPERES4808 ARTICLE IN PRESS J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – 7 Appendix A. Lemma A.1. If Xpis an optimal solution of Problem3 (3) then for k=2,...,p,2kis assigned to v2ifor some i,i=1,...,p.5 Proof. Suppose on the contrary that 2kis assigned to v2j−1for some j,j=1,...,p. We can assume7 without loss of generality that 2kis the maximum possible even index of a -weight assigned to v2j−1 9 with j=1,...,p. Recall that kmust be less than p since 2p=2p(see Remark 2.2). In what follows we11 distinguish two cases depending on the type of node where 2k+1has been assigned to.13 Case 1: 2k+1is assigned to v2jfor some j,j= 1,...,p.15 By Remark 2.2(i) we have that 2j>2j−1=2k. Thus, by Remark 2.1(iv), we must have that17 2j>2j−1=2k. Hence, since Xpis optimal, xjmust be located as far as possible from v2j−1.19 Besides, since 2j−1=2k<2k+1=2jthen d(v2j−1,x j)⩽d(v2j,x j). Therefore, we have that21 d(v2j−1,x j)=d(v2j,x j)and we can reassign the -weights, so that 2kis assigned to v2jand 2k+1to23 v2j−1. Case 2: 2k+1is assigned to v2j−1for some j,25 j=1,...,p. Assume that d(v2j−1,x j)= d(v2j,x j)and27 d(v2j−1,x j)= d(v2j,x j). Under this assumption, we can move xjand xjtowards v2jand v2j,29 respectively, by the same small enough amount, , without any reassignment of the -weights (see Fig.31 3(a)).This is possible because 2k+2=2j for some j,j =1,...,p (recallthat 2kis the maximum in-33 dexofa-weight assigned to a node with odd index) and d(v2j−1,x j)as well as d(v2j−1,x j)are strictly35 smaller than d(v2j ,x j ). These movements imply the following change in the objective function:37 (2k+2k+1−2j−2j). This amount is negative. Indeed, since 2j>2k+139 and 2j>2k+1, by Remark 2.1(iv), we get 2j+2j>22k+2and, by (4), we have that 41 22k+2>2k+2k+1. This is a contradiction because Xpwas an optimal solution.43 In what follows, we study the cases d(v2j−1,x j)= d(v2j,x j)and d(v2j−1,x j)=d(v2j,x j).45 Case 2.1: d(v2j−1,x j)=d(v2j,x j). Since 2j−1=2k+1 we can assume without loss 47 of generality that 2j=2k+2. Now, since 2k+1and 2k+2have been already assigned and, by Remark 49 2.2(i), 2j>2kwe get that 2j>2k+2=2j. This means, by Remark 2.2(ii), that j>j . Moreover, since 51 2j>2kthen, by Remark 2.1(iv), 2j>2j−1=2k. Hence, xjmust be located as far as possible from 53 v2j−1because Xpis optimal. Besides, the relationship 2j−1=2k<2k+1=2j−1implies that 55 d(v2j−1,x j)⩽d(v2j−1,x j). Therefore, we obtain that d(v2j−1,x j)=d(v2j−1,x j). This permits reas- 57 signing the -weights so that 2kis assigned to v2j−1, 2k+1to v2jand2k+2to v2j−1(see Fig. 3(b)). How- 59 ever, this allocation induces a contradiction because 2kis the maximum even index of a -weight assigned 61 to a node with odd index. Case 2.2: d(v2j−1,x j)=d(v2j,x j). The analysis of 63 this case is analogous to the Case 2.1 and also induces a contradiction. 65 After this case analysis, we conclude that the optimal assignment of the -weights satisfies that each 67 2kfor any k=2,...,p, is allocated to v2ifor some i,i=1,...,p.69 The result above describes the optimal assignment of the -weights with even index, k>2. However, it is 71 still missing the case 2. The following result analyzes this case: 73 Lemma A.2. If Xpis an optimal solution of Problem (3) then 2must be assigned to v2.75 Proof. First, notice that if 2were assigned to v2i for some i,i=1,...,p, then by Remark 2.2(ii) and 77 since 1is already assigned to a v2j−1for some j, j=1,...,p, we would have that i=1. 79 In order to prove the result, we proceed by contradiction assuming that 2is assigned to v2j−1for some 81 j,j=1,...,p. Therefore, since by Lemma A.1, for k=2,...,p,2kis assigned to v2ifor some iwith 83 i=1,...,p, and 2is assigned to v2j−1then there exists only one jo∈{1,...,p}such that 2jo−1is as- 85 signed to a node v2ifor some i,i=1,...,p. Depending on the value of jo, we distinguish the following 87
UNCORRECTED PROOF 8J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – OPERES4808 ARTICLE IN PRESS Fig. 3. Illustration of Lemma A.1. Fig. 4. Illustration of Lemma A.2. cases:1 Case 1: jo=2 (see Fig. 4(a)). If 3is assigned to v2ifor some i,i=1,...,p,3 then, by Remark 2.2(ii) and Lemma A.1, 3must be assigned to v2(i=1) and 4to v4. By Remark 2.2(i),5 1<3 and 3<4 then 1⩽2 and 3⩽2. Therefore, 1is assigned either to v1or v3and the same occurs7 with 2. In any case, to minimize the objective function we must have that d(v1,x 1)=d(v2,x 2)=d(v3,x 3)9 and this implies that we can reassign the -weights such that 1goes to v1,2to v2and 3to v3. Since11 the objective value does not change, we get the thesis of the Lemma.13 Case 2: jo=3 (see Fig. 4(b)). If 5is assigned to v2ifor some i,i=1,...,p, then,15 by Remark 2.2(ii) and Lemma A.1, 4must be assigned to v2,5to v4and 2ito v2ifor any i=3,...,p.17 Since 4,5and 6have been already allocated and Remark 2.2(i) ensures that 1<4, 2<5 and 3<619 then 1⩽3, 3⩽3 and 5⩽3. Moreover (i) Since 4<5then d(v1,x 1)⩽d(v3,x 2). (Other-21 wise the objective function may decrease). Indeed, if d(v1,x 1)>d(v 3,x 2)we move x1and x2 23 towards v1and v4, respectively, such that, x 1and x 2, the new locations of x1and x2, satisfy that25 d(v1,x 1)=d(v3,x 2)and d(v3,x 2)=d(v1,x 1). This movement induces the following change in 27 the objective function: (d(v1,x 1)−d(v3,x 2))(4−5)<0,29 what contradicts the optimality of Xp. (ii) Since 3⩽3, 5⩽3 and 2=4, Xpmust satisfy 31 that d(v2,x 1)⩾d(v3,x 2)and d(v2,x 1)⩾d(v5, x3). In addition, we have by construction that 33 d(v2,x 1)⩽2 then d(v3,x 2)⩽2 and d(v5,x 3)⩽2. This allows us to use the same arguments of Case 35 2(i) to prove that d(v3,x 2)⩾d(v5,x 3)because 5>6.37 Therefore, 1must be assigned to v1,2to v5and 3to v3. In addition, since 1,2,3,4,5,6have 39 been already assigned and 8is assigned to v8; Remark 2.2(i) implies that 7is assigned to v7. Repeating this 41 argument for any i>4 we have that 2i−1is assigned to v2i−1. Thus, 2i−1=2i−1 and 2i=2ifor any 43 i=4,...,p. This assignment of the -weights implies that 45 d(v2i,x i)=d(v2i+1,x i+1)for any i=3,...,p−1. Indeed, since 2i=2i<2i+1=2i+1then 47 d(v2i,x i)⩽d(v2i+1,x i+1), and since 2i+1>2i+2 we deduce that xi+1is located as close as possible 49
UNCORRECTED PROOF OPERES4808 ARTICLE IN PRESS J. Puerto, A.M. Rodríguez-Chía / Operations Research Letters ( ) – 9 Fig. 5. Illustration of Case 4. to v2i+1,i=3,...,p −1. Hence, it implies that1 d(v2i,x i)=d(v2i+1,x i+1)for any i=3,...,p−1. Moreover, with this assignment of the -weights3 and since, by (6), 22>4+5+8then the optimal location for x1,x2and x3must be: x1=v1,x2=v3,5 x3=v5. However, this is a contradiction because we will7 prove that the above configuration of Xpdoes not provide an optimal solution of Problem (3). Indeed,9 move x1,x2and x3to the new positions x 1,x 2and x 3, respectively, where x 1=v1+1, x 2=v3+1, and x 3=v5+11 3. Using the condition d(v2i,x i)=d(v2i+1,x i+1)for any i=3,...,p, this movement allows us to displace13 three units length: (1) xitowards v2i−1for any even index i=4,...,pand (2) xjtowards v2jfor any odd15 index j=4,...,p; without any reassignment of the -weights corresponding to these nodes. Therefore,17 these movements produce the following change in the objective function:19 +1+2+3+4−5−36−3(7−8) +3(9−10)−3(11 −12)+.... We prove that this amount is negative. Indeed, by the21 definition of the -weights, see (2) and (4)–(6), they satisfy that +1+2+3+4−5−36is negative.23 Besides, −3(7−8)+3(9−10)−3(11 −12)+...25 is negative because the sequence 7−8,9−10, ... is decreasing. This fact contradicts the optimality of27 Xpsince the objective function decreases. Case 3: jo=4. The proof is similar to the one in29 Case 2, and therefore it is omitted. Case 4: jo>4 (see Figs. 5 and 6). 31 Using Remark 2.2(ii), Lemma A.1 and a similar argument to that used in Case 2(i), 1must be assigned 33 to v1,2to v3,2i+2to v2ifor i=1,...,j o−2, 2i−3to v2i−1for i=3,...,j o−2, 2jo−3to v2jo−3,35 2jo−5to v2jo−1,2jo−1to v2jo−2, and ito vifor i=2jo,...,2p.37 Moreover, notice that, 2i−1>2ifor i>1. Hence, following a similar argument to the one in 39 Case 2, we obtain that d(v2i,x i)=d(v2j−1,x j) whenever 2j−1−2i=1. 41 For this assignment of the -weights, using (2) and (4)–(6), the optimal location of x1,x2,x3,x4and x543 must be x1=v1,x2=v3,x3=v5, and either 1. x4=v7+4 and x5=v9+2, if jo=5 (Fig. 5)45 or 2. x4=v7+2 and x5=v9+4, if jo>5 (Fig. 6). 47 However, this is a contradiction because we will prove that the above configuration of Xpdoes not 49 provide an optimal solution of Problem (3). Move x1, x2,x3,x4and x5to the new positions x 1,x 2,x 3,x 451 and x 5, respectively, where x 1=v1+1, x 2=v3+1, x 3=v5+4, and 53 1. x 4=v7+4 and x 5=v9+3, if jo=5 (Fig. 5). 2. x 4=v7+3 and x 5=v9+4, if jo>5 (Fig. 6). 55 These displacements permit us to move xitowards either v2i−1or v2ifor i=6,...,p without any re- 57