Efficiency in Euclidean constrained location problems

Operations Research Letters 14 (1993) 291-295 December 1993 North-Holland Efficiency in Euclidean constrained location problems E. Carrizosa, E. Conde, F.R. Fernandez and J. Puerto Dpto. de Estadistica e Investigacion Operativa, Facuhad de Matematicas, Universidad de SevUla, Tarfia s / n, 41012 Sevilla, Spain Received May 1992 Revised August 1993 In this note we present geometrical characterizations for the set of efficient, weakly efficient and properly efficient solutions to the multiobjective Euclidean Location problem with convex locational constraints, extending the known results for the unconstrained problem. It is shown that the set of the (weakly) efficient points coincides with the closest-point projection of the convex hull of the demand points onto the feasible set S. It is also shown that the set of properly efficient solutions is the union of two sets: the set of feasible demand points and the closest-point projection of the relative interior of the convex hull of the demand points onto S. efficiency; location theory; Weber problems 1. The model Let A be a finite set of points in En (demand points). A facility is to be located at some point x within a feasible set S ~ En in such a way that all the demand points have the facility as close as possible, where distances are measured by the Euclidean distance d in E": d(x, y) = (x -y, x _y)l/2 for all x, y ~ ~". The aim of simultaneous minimization over S of the family of functions {d(a, • ): a ~A} leads us to the multiobjective problem MOP(A, S), MOP(A,S): min(d(x,a)'a~A). x~S A point x ~ S is said to be an efficient (respect. weakly efficient) solution to MOP(A, S) iff there exists no y ~ S such that d(y,a) <_d(x,a) Va ~A; d( y, a) < d( x, a) forsome a~A (respect. d(y, a) < d(x, a) for all a EA). Denote respectively by E(A, S) and WE(A, S) the set of efficient and weakly efficient solutions to MOP(A, S). Any point x in E(A, S) is a best-possible point, in the sense that no other point is preferred to x by all the demand points. However, E(A, S) may contain undesirable solutions, (see, e.g. Geoffrion, 1968) what has motivated the introduction of alternative solutionsets for MOP(A, S). A popular solutionset in Location theory is the Weber set PE(A, S), the set of the optimal solutions to problems of the form miny~s Y"a~A wad(a, Y), when w varies in the set of vectors with positive components. Correspondence to: Prof. E. Carrizosa, Dpto. de Estadistica e Investigacion Operativa, Facultad de Matematicas, Universidad de Sevilla, Tarfia s/n, 41012 Sevilla, Spain. 0167-6377/93/$06.00 © 1993 - Elsevier Science Publishers B.V. All rights reserved 291 SSDI 0167-6377(93)E0067-2 Volume 14, Number 5 OPERATIONS RESEARCH LETTERS December 1993 By convexity of the functions d(., a), as soon as the set S is closed and convex, the set PE(A, S) coincides with the set of properly efficient points (see Geoffrion, 1968). Throughout this note, the following notation is used: W represents the set of normalized nonnegative vectors, W= ((Wa)a~AE~IA', Wa>~OVaEA, E Wa= 1) a~A and W + represent the set of normalized positive vectors, W+= ((Wa)a~A ~IAI, wa>O Va ~M, E Wa= l}. a~A For any set X in En, H(X) represents its convex hull. Given a nonempty closed convex set Xc ~n and y ~ En, denote by projx(y) the point in X closest to y, i.e.: projx(y) is the optimal solution to the optimization problem min d( x, y ). x~X Observe that, as soon as X is a nonempty closed and convex set, proJx(.) is well-defined. For any set Y_ E", denote by projx(Y) the set pr°jx(r) = U proJx(y). y~Y 2. Efficient points Lemma 1. For any x, y E ~n, and any w = (Wa) a ~ A E W, the following statements are equivalent: (i) d(x, F~a~Awaa)<d(y, Ea~AWaa); (ii) Ea~Awad(x, a)2< Ea~Awad(Y, a) 2. Proof. For any z~ n, it can be seen that Ea~AWad(z, a)Z=d(z, Ea~Awaa)2-d(O, Ea~Waa)2+ Ea E AWad(O, a) 2. Hence wJ( x, 2 a) < ~., wad(y, a) 2 a~A a~A iff d(x, E Waa}2<d(Y, E Waa)2, i'e': d(x, E Waa)<_d(y, E waa)" [] a ~A " a ~A a ~A a ~A " Theorem 1. Let X be a nonempty closed convex set in ~", and let x ~ ~n. The following statements are equivalent: (i) There exists no y ~ X such that d(y,a)<d(x,a) foralla~A. (ii) There exists a* ~ H(A) such that d(a*, y)>__d(a*,a) forally~X. Proof. Indeed, condition (i) is verified iff the set Y, Y= {y EX: d(y, a) 2 <d(x, a) 2 for all a ~A} 292 Volume 14, Number 5 OPERATIONS RESEARCH LETI'ERS December 1993 is empty. By Theorem 4.2.3 of Mangasarian (1969), (recall that d(., a) is convex for all a ~A), Y is empty iff :tw ~_ W~ ~ wad(x, a) 2 a ~A which, by Lemma 1, is equivalent to i.e.: _<min ~] wad (y,a) 2 y~X a~A Zwoa) a~A y~X a~A 3a*(a*= a~A%a ) which is condition (ii). ~H( A)/d( x, a*) < mind(y, a*) y~X Hence, (i) and (ii) are equivalent [] The theorem of alternative above provides a simple characterization of the set of efficient points E(A, S) as soon as S is a closed and convex set in ~", extending to constrained problems the result E(A, ~")= H(A) (Kuhn, 1967). Theorem 2. For any nonempty closed convex set S in ~n, WE(A, S)= E( A, S) = proJsH( A ) Proof. As the Euclidean norm is a round norm (Thisse, Ward, Wendell, 1984), it follows that WE(A, S)= E(A, S). Let x ~ S; by definition of weak efficiency, x ~ WE(A, S) iff there exists no y ~ S such that d(y, a) < d(x, a) for all a ~A. By Theorem 1, this condition is equivalent to 3a*~n(A)/d(a*, y)>__d(a*, x) forall yES i.e. (recall that x ~ S): :la* ~-H(A)/x = projs(a* ), i.e. x ~ proj s (H(A)), as asserted. [] 3. Properly efficient points Our next theorem represents the set PE(A, S) in terms of ri H(A), the relative interior of H(A). Theorem 3. For any nonempty closed convex set S in ~, PEC A, S) = C A N S) 1,3 proj s ri HC A) Proof. For any w ~ W, consider the optimization problems Pl(W) and P2(w), el(w): min ~ wad(y, a), y~S a~A P2(w): min d(y, ~ Waa ). y~S a~A 293 Volume 14, Number 5 OPERATIONS RESEARCH LETTERS December 1993 For any x ~ S\A, let ~b x : W+-o W + be the function that associates to each w = (w,)~ A the vector (Ox(W), with (qbx(W))a = [wa/d(x, a)]//[b~A (Wb/d(x , b))] which is easily seen to be a bijection. We first show that x ~ S \A is an optimal solution to problem Pl(W) iff x is an optimal solution to e2(G(w)). Let x ~ S \A, and let f and g be the functions defined as f(y) = Y'~ wod(y, a), g(y) = E (G(w)),d(Y, a) 2 a~A a~A As x ~A, both f Vf(x) Hence, for any sign, what implies g(y)>g(x) forall y~S, what, by Lemma 1, occurs if and only if x solves P2(4)x(w)). Hence, we have: x ~ S\A solves Pl(W) iff x solves P2(4)x(W)). We show now that PE(A, S) ___ projs(ri H(A)) U (A N S). For this purpose, let x be an arbitrary element of PE(A, S). If x ~A, there is nothing to show, so we only have to consider the case x flA. and g are convex and differentiable at x. Furthermore, it is readily seen that = Vg(x). E (wJ2d(x, a)) a cA direction d, the directional derivatives of f and g in the direction d have the same that x is an optimal solution to Pl(W) iff (,) As x ~ PE(A, S), there exists w ~ W + such that x is an optimal solution to Pl(w). As x ~A, (*) applies, thus there exists v (v -- ~bx(w)) ~ W ÷ such that x is an optimal solution to P2(v), i.e.: x=projs(a* ), witha*= ~ Ga. a cA As A is finite, one has (see, e.g. Brondsted, 1983), riH(A)={z~n/z = ~_,haaforsomeA~W+}. (**) a cA Hence, a* ~ ri H(A), thus x = projs(a* ) ~ projs(ri H(A)). As x was an arbitrary point in PE(A, S), we have PE(A, S) G projs(ri H(A)) U (A AS). To show the converse, observe first that the majority theorem of Witzgall (1964) implies that (An S) c PE(A, S). On the other hand, for any x ~ projs(ri H(A))\A, (* *) implies that 3v ~ W + such that x solves P2(v). As x ~A, by (*), x solves Pl((bx(1))-l), thus x ~ PE(A, S). Hence, PE(S) ~ projs(ri H(A)) U (A AS), and this completes the proof. [] 294 Volume 14, Number 5 OPERATIONS RESEARCH LETTERS December 1993 4. Extensions The results obtained in this paper can be extended in an straightforward manner to ellipsoidal metrics, i.e.: metrics induced by a scalar product. Indeed, for any ellipsoidal metric d*, there exists a regular matrix T such that d*(x, y) =d(Tx, Ty) for all x, y. If we denote by E(A, S; d*) (respectively WE(A, S; d*), PE(A, S; d*)) the set of efficient (respectively weakly and properly efficient) points to the multiobjective problem with S as feasible set, A as set of demand points, and distances measured by d*, one has: E(A, S; d*) = T -1.E(T'A, r" S; d), WE(A, S; d*) = T-1.WE(T.A, T. S; d), PE(A, S; d*) = T -1- PE(T.A, T-S; d). On the other hand, denoting by prOjS,d, the closest-point projection with metric d*, one has projs, d*(X) = T -1" projr.s, d(T'x) and Hence, WE(A, S; d*) =E(A, S; d*) = proJs, d.(H(A)) PE(A, S; d*) = (A n S) U proJs, d.(ri (H(A))). Extensions of the results to nonellipsoidal metrics (e.g.,/p-metrics, with p ¢ 2) are not trivial, and are now under study. References A. Brondsted (1983), An introduction to Convex Polytopes. Springer-Verlag, New York. A.M. Geoffrion (1968), "Proper efficiency and the theory of vector maximization", J. Math. Anal Appl. 22, 618-630. H.W. Kuhn (1967), "On a pair of dual nonlinear programs", in: J. Abadie (ed.), Nonlinear programming, Wiley, New York. O.L. Mangasarian (1969), Nonlinear Programming, McGraw-Hill, New York. J.F. Thisse, J.E. Ward and R.E. Wendell (1984), "Some properties of Location problems with block and round norms", Oper. Res. 32, 1309-1327. C. Witzgall (1964), "Optimal location of a central facility, mathematical models and concepts", National Bureau of Standards Report 8388. 295