A characterization of efficient points in constrained location problems with regional demand

ELSEVIER Operations Research Letters 19 (1996) 129-134 A characterization of efficient points in constrained location problems with regional demand Emilio Carrizosa a,*, Frank Plastria b a Faeultad de Matemhticas, C/Tarfia s/n, 41012 Sevilla, Spain b Center Jbr Industrial Location and Development, Pleinlaan 2. B 1050 Brussels. Belyium Received 1 January 1995; revised I February 1996 Abstract In this paper we characterize the set of efficient points in the planar point-objective location problem under a convex locational constraint, when distances are measured by a strictly convex norm in ~2 and the set of demand points is a compact set. It is shown that, under these assumptions, the efficient set coincides with the closest-point projection of the convex hull of the demand points onto the feasible set. Keywords: Location problems; Efficiency; Convex analysis; Strictly convex norms 1. Introduction Let A and S be nonempty sets in ~2, and let 7 be a norm in ~2. Consider the vector-optimization problem P(>A,S), P(>A,S): min(Ta(X): acA), xEs where, for each a E A, ),a is the function 7a :X E ~2 ----+ ),a(X) = 7(X -- a) measuring the distance up to a. A point x c S is said to be efficient for problem P(7,A,S) iff there exists no yES such that 7a(Y) <~ )'a(x) for all a EA, with at least one strict inequality. A point x E S is weakly efficient iff there exists no y E S such that 7a(Y) < 7a(x) for all a EA. * Corresponding author. Throughout this note, the set of efficient and weakly efficient points for P(7,A, S) will be denoted, respectively, E(7,A, S) and WE(7,A, S). A number of papers (see e.g. [2,4,6,10,14,15]) have been devoted to the search of efficient points of the problem above, known in the literature as the pointobjective location problem (see [13]), but mostly in the unconstrained case, i.e., under the assumption that the facility can be placed at any point in the plane, i.e., S = ~2. Although this assumption has been widely questioned (see, e.g., [5]), only some partial results have been obtained in the presence of constraints. For instance, in [5, 9] necessary conditions for a point to be efficient are derived, e.g., the points in E(7,A, S) are visible from the set E(7,A, 1~ 2) of efficient points for the unconstrained problem [9]. However, a full characterization of the set of (weakly) efficient points has 0167-6377/96/$15.00 Copyright (~) 1996 Elsevier Science B.V. All rights reserved PH S0 167-6377(96)00005-3 130 E. Carrizosa, 1~ Plastria/ Operations Research Letters 19 (1996) 129-134 only been obtained in [1] for the classical case when 7 is the euclidean norm and A is finite, showing that E(7, A, S) and WE(7,A, S) coincide with the orthogonal projection onto S of E(7,A, ~2), known to equal the convex hull of A [13]. In this paper we characterize E(7,A,S) and WE(7,A, S) when A is compact, S is a closed convex set and 7 is a strictly convex norm, (i.e., 7 is a norm such that the boundary of its unit ball does not contain nondegenerate line segments), showing that both E(7,A,S) and WE(7,A,S) equal the closest-point projection (with respect to 7) of the convex hull of A (i.e., E(7,A, ~2) = WE(7,A ' ~2) [13]). Since the euclidean norm is strictly convex, the characterization given in [1] is extended here in two ways: A is allowed to be infinite, and 7 is an arbitrary strictly convex norm. The proofs make use of rather well-known results of Convex Analysis, which may be found, e.g., in [12]. of a more general result given in [11], and the proof is not repeated here. Lemmas 2-4 are new, and the proofs can be found in the Appendix. Lemma 1. For any x E S, the following statements are equivalent." (i) There exists no y E S such that 7o(Y) < 7a(x) jot all a E A. (ii) S*(x) N conv(Uae A t37a(X)) ¢ O. Lemma 2. The Jbllowing statements are equivalent." (i) 0 ~ conv(U~A O7(a)), (ii) 0 E conv(A), (iii) 0 E UaEco,v~A) t37(a)- Recall that, if x = 0, then O7(x) = B °, whilst, for x ~ 0, 07(x) is an exposed face ofB °, see e.g. [3]. Lelnma3. Let a,b, cEbd(B), u,v, wEbd(B °) be such that 2. The results u E t?7(a), v ~ ~37(b), w E c37(c ). In what follows, S is a nonempty closed and convex set in ~2, A is a nonempty compact subset of ~2, and 7 is a strictly convex norm, whose unit ball is denoted by B; the dual norm of 7 is denoted by 7 °, and its unit ball by B °. Given a set X c ~2, let conv(X) denote its convex hull, and bd(X ) its boundary; for any x c X, let X* (x) be the convex cone X*(x) = {u E Re: (u,y-x) ~ 0 for all yEX}, where (., .) denotes the usual scalar product. In other words, X*(x) = -Nx(x), where Nx(x) is the normal cone of X at x (see [12]). Given x E S, it is well-known that, since 7 is a strictly convex norm, saying that no y E S verifies 7~(Y) < 7~(x) for all a c A is equivalent to saying that no y E S verifies (7,(Y) ~< 7a(x) Va E A, with some inequality strict) [ 10, 13], thus the concepts of efficiency and weak efficiency coincide: WE(~,, A, S) = E(';, A, S). In order to characterize E(7,A, S), some properties of strictly convex norms are needed. These properties are stated in Lemmas 1-4: Lemma 1 is a consequence (i) Ij'a ~ dzb and c = )~a + Izb for some )~, p > 0, then there exist ~, fl > 0 such that w = ~tu + fly. (ii) Ira ¢ -b and w = ~u + fly for some ~, fl >1 O, then there exist )~, # >~ 0 such that e = )~a + pb. Lemma 4. For any closed convex cone C with vertex at 0, the followin 9 statements are equivalent: (i) C N conv(UaE A 07(a)) ¢ O, (ii) C N (UaEconv(A)~T(a)) • ~. Given a point x E [~2, denote by proj.;,s(x) the point in S closest to x with respect to 7, i.e., proj..s(X ) = arg rain 7x(Y)- yES Since S is closed and convex and 7 is a strictly convex norm, proj,;,s is always well-defined. For any set X C ~2, denote also by proj~, s(X), the set proj;, s(X ) = {projT, s(X): x E X}. With this notation, we are in position to characterize the set E(7,A,S) of efficient points for problem P(7,A,S), showing that the characterization given in F~ Carrizosa, F Plastria/ Operations Research Letters 19 (1996) 129-134 131 [1] for the euclidean norm remains valid for general strictly convex norms. the recent paper [8] for a different approach to the problem. Theorem 1. Let S be a nonempty closed convex set in ~2, and let ~, be a strictly convex norm. Then, for any nonempty compact set A C ~2, E(7, A, S) = WE(7, A, S) = projz,,s(conv(A )) Proof Let xES; by Lemma 1, xEWE(y,A,S) (=E(7,A, S)) iff As conv(Ua6 A aTa(X ) ) = conv(UbEx_ A aT(b)), S* (x ) is a closed convex cone with vertex at 0, and x - A is compact, Lemma 4 applies, and we have u bEconv(x--A) In other words, x E WE(7,A,S)iff3b E conv(x-A)= x - conv(A) such that S*(x) N 87(b) ~ 0, which occurs iff 3a* E conv(A) such that S*(x) N 87~,(x) ~ ~. By Lemma 1 (with A -- {a*}), nonvoidness of S*(x) N aTa* (x) is equivalent to x being equal to proj~.,s(a*). Hence, x E WE(7,A,S) iffx Cproj~.,s(COnv(A)). [] Remark 1. As a consequence of Theorem 1 in [7], when A is finite, WE(7,A,S) equals the set of Weber points, i.e., the optimal solutions to problems of the form rain Z 2a7a(X) xES aEA when 2 = (2~)~eA varies in the set of nonnegative nonzero vectors. Hence, Theorem 1 implies that the set of Weber points for constrained problems equals the closestpoint projection (with respect to 7) of the set of Weber points without constraints, a result more precise than those given in [5]. Remark 2. The proof of Theorem 1 (in fact, the technical precedent lemmas) heavily relies on the fact that 7 is a norm, thus its ball B is symmetric with respect to the origin. Extensions of Theorem 1 to general strictly convex gauges with asymmetric balls, seem to require different tools than those used in this paper. See also Acknowledgements The research of the first author has been partially financed by the Direcci6n General de Investigaci6n Cientifica y Trcnica, Spain, under grant PB93-0927. Appendix Proof of Lemma 2 (part (i) ~ (ii)). Since 7 is a norm, it follows that ay(-a)-- -aT(a ) for all a E ~2. Hence, 0 C cony( U 87(a))iff0 E conv( U 87(-a)] \ aEA / \ aEA / By Lemma 1 as (g~z)*(x) = {0}, one has 06 conv (a?A0y(--a)) iff (~2)*(0) O conv( U 87a(0)] ~ 0, \ aEA / iff there exists no y E ~2 such that 7o(Y)< 7a(0) VaEA, which is equivalent to 0EWE(7,A,~2). Hence, 0 6conv(aUA~7(a)) iff 0 EWE(7,A,~2). By Corollary 1 of[11], 0 E WE(7,A, ~z) iff 0 E WE(7,A', R e) for some finite A ~ C A Since 0 E WE(7,A ~, R 2) = conv(A ~) for all finite A ~ (see [13]), and conv(A) = U{conv(A'): A' CA, A' is finite}, it follows that 0Econv(UaE A 87(a) ) iff 0 E conv(A), as asserted. [] Proof of Lemma 2 (part (ii) ¢~, (iii)). 0 E conv(A) iff 3a* E conv(A) such that 0 minimizes in •2 the function 70*. As 7a* is convex, 0 minimizes 7a* iff 0 E 87(--a*)----- --87(a*). Hence, 0 E conv(A) iff 0 E UaEconv(A)aT(a), as asserted. [] Proof of Lemma 3. We only prove part (i); part (ii) can be proven with similar arguments. 132 E. Carrizosa, F Phtstria / Operations Research Letters 19 (1996) 129-134 As u E @(a), v E @(b), Jza, +b E bd(B), and B is symmetric with respect to 0, one has: (1) (a,u)= 1, (2) {b, v)= 1, (3) I(x,,>l ~< 1 and I(x,*'>l ~ 1 for allxEB. In particular, I(a, v) l~< 1 and l(b , u)l~< 1. Furthermore, these inequalities are strict; indeed, if {a, v) = 1 (respect. (a, v) = - 1 ), the line (v,x) = 1 would support B at a and b (resp. -a and b), implying, because of the convexity of B, that the whole segment with extreme points a and b (resp. -a and b) is contained in bd(B), contradicting the assumption that 7 is a strictly convex norm. Hence, one has: (4) [(a,v)l < 1, (5) I(b,u)[ < 1. As, by assumption, c = ).a +/2b ~ B, ( 1 ) (2) imply (by (3), forx = e): (6) I;. +/2(b,,)l ~< i, (7) I)~(a, v) +/21 ~< 1. The vectors u and v are linearly independent; indeed, otherwise, as 7°(u)= 7°(v)-= 1, we would have that u = :kv, contradicting (1)-(4). Hence, {u,v} is a basis in N2, thus there exist z~, fi E N such that w = z~u + fly. Observe that w E bd(B°); hence, the line (w,x) = 1 supports B, thus (8) I~(b,u) + fll ~< 1. (9) I~ +/3(a,v)l ~ 1. Furthermore, as w E 77(c) and (w, c) = 1, we also have: (10) ~{;. +/2(b,.) } + N;.(a, ~') +/2} = I. Define the segment F in R 2, F = {(~,fl) ~ N2: (~,]~) verifies (8),(9) and (10)} which, of course, contains the point (~,/3). In order to show that ~ and 13 are strictly positive, we first show that F is included in the nonnegative quadrant F' = {(~,fl) E N2: ~ ~> 0,fl >~ 0}, by showing that the vertices of F are in F'. The vertices of F are among the points obtained by replacing one of the inequalities in (8) or (9) by an equality. Let us study separately the different cases: Case 1: 7(b,u) +fi = 1 It leads to the values: ~=(l -/2 - 2(a,v} )/(2(1 - (a,v)(b,u) )), fi= (). - (1 -/2)(b,u))/().(1 - (a,v)(b,u))). By (4), (5) and (7), it immediately follows that ~ >/0. On the other hand, (9) implies that 2 ~> I 1 - #1; indeed, by (9), = I((l -/2 - ;~(a, t') ) + (a, v)( 2 - (1 -/2)(b,u)))/(2(l - (a, v) (b,u) ) )[ = I(l -/2)(1 - (a, v} (b, u) )/(,~(1 - (a,v}(b,u)))[ = f(1 -/2)/)-I, thus I1 -/21 ~< 12i =2, as asserted. Hence, by (5), ;~-(1 -/2)(b,~) >/i-I1 -/2I >~0. As ). > 0, (4) and (5) imply that ).(l - (a,v) (b, u)) > 0; hence, fl ~> 0. Case 2: ~(b, u} + fl = - 1 It leads to the values = (1 + It + 2{a,v))/2(1 - (a,v)(b,u)), = -(). + (1 +/2)(b,u))/)~(l - (a,v}(b,u)). First, (5) and (6) imply that 1 >~ ). +/2(b,u) >1 ). -/2l(b,u)l > 2 -/2, thus ~. < 1 +/2. On the other hand, (~, r) must verify (9), which is readily seen to be equivalent to 2 ~> [1 + /21 = I +/2, what is a contradiction. Hence, the solution of (10) and 7(b,u) + fl = -1 does not give a feasible point. Due to the symmetry in ~, r, 2,/2 in F and constraints (1)-(7), similar results are obtained for the cases + ]~(a, v) = + 1. Hence, all the extreme points ofF are contained in F', thus F C F'; as (~, fl) E F, it follows that ~, fl >~ 0. Furthermore, x and [~ are both strictly positive; otherwise, w = ~u for some ~ > 0 or w = /3v for some fl > 0; suppose that w = c~u for some ~ > 0; as l = 7°(w) = 7°(u), we would have that w = u. Hence, the line tu, x) = 1 would support B both at a and c, thus the nontrivial segment with extreme points a and c would be contained in bd(B), which is a contradiction (recall that 7 is a strictly convex norm). E. Carrizosa, F. Plastria/ Operations Research Letters 19 (1996) 129-134 133 With this we have shown part (i). [] Proof of Lemma 4 (part (i) ~ (ii)). As 0 E C, the result follows from Lemma 2 if 0E cony (U~A0?(a)). Hence, we further assume that 0 ¢ conv(U~EA 07(a)) (or, equivalently, 0 ¢ conv(A)). Consider the planar convex cone A, = {u E II~2: u = 2~ for some A E conv( U ct7(a)],2 ~> 0}. \ a~A ,t A is a planar closed convex cone, and A ¢ [~2; indeed, it is easily seen that A is a convex cone; closedhess follows from the fact that conv(Ua~ A O?(a)) is compact (see, e.g. [11]); as, by assumption, 0 ¢ conv(Ua~A 0?(a)) and conv(UaE A c3?(a)) is compact and convex, it follows that A ~ R 2. Furthermore, it is straightforward to check that the extreme rays of A are necessarily elements of UaCA c3?(a), i.e., there exist aj,a2 EA, ~1 ~ O?(al), ~2 E c37(a2) such that A= {u~[~2: u=h~l +/2~2 for some t~, tz >~ 0}. Furthermore, (1/y(al))al ¢ -(1/y(a2))a2 because, otherwise, 0 E conv(A). Let d E C~conv(UaEA 87(a)). As d E A, and de0, it follows that d = 21~.l + 22~2 for some )q,),2 ~> 0,),1 + 22 > 0 Let d t = d/?°(d). One has: • d' = ~l +/~2 for some ~,/~ t> 0, ~ +/~ > 0. • There exists c E bd(B) such that d' E 87(c) (because d' E bd(B°)). AS ~i E O?(ai/?(ai)), (i = 1,2), al/]:(al) ~ --a2/ y(az), and ai/7(ai) E bd(B), (i = 1,2), by Lemma 3 (part ii), c=2al+#a2 for some 2, /t ~> 0, A+/.t>0 Let c ~ be the vector c' = c/(2 + #) E conv(A). It follows that d' E ~7(c')C U~co, v(A)c97(a), and dl EC. Hence, U~E~onv(A) OT(a) N C ¢ 0, as asserted. [] Proof of Lemma 4 (part (ii) =~ (i)). The result follows from Lemma 2 if 0 E UaEconv(A) c~7(a). Hence, we further assume that 0 ¢ UaEconv(A) aT(a), i.e., 0 conv(A). Consider the planar convex cone F, F = {u E ~z: u = 2a for some 2 > 0, a E conv(A)}. Then, there exist a~,a2 E A such that F ---- {u: u = hal + t2a2 for some tl,t2 >~ O, t~ + t2 > 0}. Furthermore, (1/7(al))al :/:-(1/7(az))a2 (else, 0 E conv(A)). Let d ~Z 0, d E C M UaEconvIA) aT(a). There exists a* E conv(A) such that d E ~y(a*). Furthermore, as 0 ¢ conv(A) and a* ¢ 0, it follows that d E bd(B°). As conv(A)C Y, there exist 2,/~/> 0, Z +/~ > 0 such that a* : 2al + kta2. If (1/7(a*))a* = (1/?(ai))ai for some i= 1,2, (1/7(a*))a* : (1/?(al))al, say, the result holds because d E C and d E d7(a*) = Oy(a*/7(a*)) = c3?(aj/y(al )) :87(a, ) C conv( U 87(a)) \ a~A / If it is not the case, we have that 2 > 0,/~ > 0, and (1/7(al))al ¢ (1/7(a2))a2. Let ~1 E 07(al), ~2 E c3y(a2). By Lemma 3, part (i), there exist ct, fl > 0 such that d ~ = 7~1 +/3~2. Hence, the vector d" = d~/(~ + fl) verifies: • d'EC, • d" E conv(dT(al ) U c37(a2)) C conv(Ua~A ~?(a)), thus (i) holds, as asserted. [] References [1] E. Carrizosa, E. Conde, F.R. Fern~indez and J. Puerto, "Efficiency in euclidean constrained location problems", Oper. Res. Lett. 14 (1993)291-295. [2] L.G. Chalmet, R.L. Francis and A. Kolen, "Finding efficient solutions for rectilinear distance location problems efficiently", Eur. Z Oper. Res. 6 (1981) 117-124. [3] R. Durier and C. Michelot, "Geometrical properties of the Fermat-Weber problem", Eur. J. Oper. Res. 20 (1985) 332343. [4] R. Durier and C. Michelot, "Sets of efficient points in a normed space", J. Math. Anal. AppL 117 (1986) 506-528. 134 E. Carrizosa, F. Plastria/Operations Research Letters 19 (1996) 129 134 [5] P. Hansen, D. Peeters and J.F. Thisse, "An algorithm for a constrained Weber problem", Management Sci. 28 (1982) 1285-1295. [6] P. Hansen, J. Perreur and J.F. Thisse, "Location Theory, dominance and convexity: Some further results", Oper. Res, 28 (1980) 1241-1250. [7] T.J. Lowe, J.F. Thisse, J.E. Ward and R.E. Wendell, "On efficient solutions to multiple objective mathematical programs", Management Sci. 30 (1984) 1346-1349. [8] M. Ndiaye, "Efficiency in constrained continuous location", Working paper no. 8/1995 of the Laboratoire d'Analyse Appliqu~e et Optimisation, Universit~ de Bourgogne. [9] F. Plastria, Continuous location problems and cutting plane algorithms, Ph.D. Dissertation, Vrije Universiteit Brussel, 1983~ [10] F. Plastria, "Points efficaces en localisation continue", Cahiers de Centre d'Etude en Recherche Operationelle de I'ULB (CCERO) 25 (1983), 329-332. [I 1] F. Plastria and E. Carrizosa, "A geometrical characterization of weakly efficient points", to appear in: J. Optim. Theory, Appl. (1996). [12] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. [13] J.F. Thisse, J.E. Ward and R.E. Wendell, "Some properties of Location problems with block and round norms", Oper. Res. 32 (1984) 1309-1327. [14] R.E. Wendell and A.P. Hurter, "Location Theory, dominance and convexity", Oper. Res. 21 (1973) 314-320. [15] R.E. Wendell, A.P. Hurter and T.J. Lowe, "Efficient points in location problems", AIIE Trans. 9 (1977) 238-246.