Efficiency in Euclidean constrained location problems

Ope a ions Resea ch Le e s 14 (1993) 291-295 Decembe 1993 No h-Holland E iciency in Euclidean cons ained loca ion p oblems E. Ca izosa, E. Conde, F.R. Fe nandez and J. Pue o Dp o. de Es adis ica e In es igacion Ope a i a, Facuhad de Ma ema icas, Uni e sidad de Se Ula, Ta ia s / n, 41012 Se illa, Spain Recei ed May 1992 Re ised Augus 1993 In his no e we p esen geome ical cha ac e iza ions o he se o e icien , weakly e icien and p ope ly e icien solu ions o he mul iobjec i e Euclidean Loca ion p oblem wi h con ex loca ional cons ain s, ex ending he known esul s o he uncons ained p oblem. I is shown ha he se o he (weakly) e icien poin s coincides wi h he closes -poin p ojec ion o he con ex hull o he demand poin s on o he easible se S. I is also shown ha he se o p ope ly e icien solu ions is he union o wo se s: he se o easible demand poin s and he closes -poin p ojec ion o he ela i e in e io o he con ex hull o he demand poin s on o S. e iciency; loca ion heo y; Webe p oblems 1. The model Le A be a ini e se o poin s in En (demand poin s). A acili y is o be loca ed a some poin x wi hin a easible se S ~ En in such a way ha all he demand poin s ha e he acili y as close as possible, whe e dis ances a e measu ed by he Euclidean dis ance d in E": d(x, y) = (x -y, x _y)l/2 o all x, y ~ ~". The aim o simul aneous minimiza ion o e S o he amily o unc ions {d(a, • ): a ~A} leads us o he mul iobjec i e p oblem MOP(A, S), MOP(A,S): min(d(x,a)'a~A). x~S A poin x ~ S is said o be an e icien ( espec . weakly e icien ) solu ion o MOP(A, S) i he e exis s no y ~ S such ha d(y,a) <_d(x,a) Va ~A; d( y, a) < d( x, a) o some a~A ( espec . d(y, a) < d(x, a) o all a EA). Deno e espec i ely by E(A, S) and WE(A, S) he se o e icien and weakly e icien solu ions o MOP(A, S). Any poin x in E(A, S) is a bes -possible poin , in he sense ha no o he poin is p e e ed o x by all he demand poin s. Howe e , E(A, S) may con ain undesi able solu ions, (see, e.g. Geo ion, 1968) wha has mo i a ed he in oduc ion o al e na i e solu ionse s o MOP(A, S). A popula solu ionse in Loca ion heo y is he Webe se PE(A, S), he se o he op imal solu ions o p oblems o he o m miny~s Y"a~A wad(a, Y), when w a ies in he se o ec o s wi h posi i e componen s. Co espondence o: P o . E. Ca izosa, Dp o. de Es adis ica e In es igacion Ope a i a, Facul ad de Ma ema icas, Uni e sidad de Se illa, Ta ia s/n, 41012 Se illa, Spain. 0167-6377/93/$06.00 © 1993 - Else ie Science Publishe s B.V. All igh s ese ed 291 SSDI 0167-6377(93)E0067-2 Volume 14, Numbe 5 OPERATIONS RESEARCH LETTERS Decembe 1993 By con exi y o he unc ions d(., a), as soon as he se S is closed and con ex, he se PE(A, S) coincides wi h he se o p ope ly e icien poin s (see Geo ion, 1968). Th oughou his no e, he ollowing no a ion is used: W ep esen s he se o no malized nonnega i e ec o s, W= ((Wa)a~AE~IA', Wa>~OVaEA, E Wa= 1) a~A and W + ep esen he se o no malized posi i e ec o s, W+= ((Wa)a~A ~IAI, wa>O Va ~M, E Wa= l}. a~A Fo any se X in En, H(X) ep esen s i s con ex hull. Gi en a nonemp y closed con ex se Xc ~n and y ~ En, deno e by p ojx(y) he poin in X closes o y, i.e.: p ojx(y) is he op imal solu ion o he op imiza ion p oblem min d( x, y ). x~X Obse e ha , as soon as X is a nonemp y closed and con ex se , p oJx(.) is well-de ined. Fo any se Y_ E", deno e by p ojx(Y) he se p °jx( ) = U p oJx(y). y~Y 2. E icien poin s Lemma 1. Fo any x, y E ~n, and any w = (Wa) a ~ A E W, he ollowing s a emen s a e equi alen : (i) d(x, F~a~Awaa)<d(y, Ea~AWaa); (ii) Ea~Awad(x, a)2< Ea~Awad(Y, a) 2. P oo . Fo any z~ n, i can be seen ha 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 i 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 " Theo em 1. Le X be a nonemp y closed con ex se in ~", and le x ~ ~n. The ollowing s a emen s a e equi alen : (i) The e exis s no y ~ X such ha d(y,a)<d(x,a) o alla~A. (ii) The e exis s a* ~ H(A) such ha d(a*, y)>__d(a*,a) o ally~X. P oo . Indeed, condi ion (i) is e i ied i he se Y, Y= {y EX: d(y, a) 2 <d(x, a) 2 o all a ~A} 292 Volume 14, Numbe 5 OPERATIONS RESEARCH LETI'ERS Decembe 1993 is emp y. By Theo em 4.2.3 o Mangasa ian (1969), ( ecall ha d(., a) is con ex o all a ~A), Y is emp y i : w ~_ W~ ~ wad(x, a) 2 a ~A which, by Lemma 1, is equi alen o 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 condi ion (ii). ~H( A)/d( x, a*) < mind(y, a*) y~X Hence, (i) and (ii) a e equi alen [] The heo em o al e na i e abo e p o ides a simple cha ac e iza ion o he se o e icien poin s E(A, S) as soon as S is a closed and con ex se in ~", ex ending o cons ained p oblems he esul E(A, ~")= H(A) (Kuhn, 1967). Theo em 2. Fo any nonemp y closed con ex se S in ~n, WE(A, S)= E( A, S) = p oJsH( A ) P oo . As he Euclidean no m is a ound no m (Thisse, Wa d, Wendell, 1984), i ollows ha WE(A, S)= E(A, S). Le x ~ S; by de ini ion o weak e iciency, x ~ WE(A, S) i he e exis s no y ~ S such ha d(y, a) < d(x, a) o all a ~A. By Theo em 1, his condi ion is equi alen o 3a*~n(A)/d(a*, y)>__d(a*, x) o all yES i.e. ( ecall ha x ~ S): :la* ~-H(A)/x = p ojs(a* ), i.e. x ~ p oj s (H(A)), as asse ed. [] 3. P ope ly e icien poin s Ou nex heo em ep esen s he se PE(A, S) in e ms o i H(A), he ela i e in e io o H(A). Theo em 3. Fo any nonemp y closed con ex se S in ~, PEC A, S) = C A N S) 1,3 p oj s i HC A) P oo . Fo any w ~ W, conside he op imiza ion p oblems 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, Numbe 5 OPERATIONS RESEARCH LETTERS Decembe 1993 Fo any x ~ S A, le ~b x : W+-o W + be he unc ion ha associa es o each w = (w,)~ A he ec o (Ox(W), wi h (qbx(W))a = [wa/d(x, a)]//[b~A (Wb/d(x , b))] which is easily seen o be a bijec ion. We i s show ha x ~ S A is an op imal solu ion o p oblem Pl(W) i x is an op imal solu ion o e2(G(w)). Le x ~ S A, and le and g be he unc ions de ined as (y) = Y'~ wod(y, a), g(y) = E (G(w)),d(Y, a) 2 a~A a~A As x ~A, bo h V (x) Hence, o any sign, wha implies g(y)>g(x) o all y~S, wha , by Lemma 1, occu s i and only i x sol es P2(4)x(w)). Hence, we ha e: x ~ S A sol es Pl(W) i x sol es P2(4)x(W)). We show now ha PE(A, S) ___ p ojs( i H(A)) U (A N S). Fo his pu pose, le x be an a bi a y elemen o PE(A, S). I x ~A, he e is no hing o show, so we only ha e o conside he case x lA. and g a e con ex and di e en iable a x. Fu he mo e, i is eadily seen ha = Vg(x). E (wJ2d(x, a)) a cA di ec ion d, he di ec ional de i a i es o and g in he di ec ion d ha e he same ha x is an op imal solu ion o Pl(W) i (,) As x ~ PE(A, S), he e exis s w ~ W + such ha x is an op imal solu ion o Pl(w). As x ~A, (*) applies, hus he e exis s ( -- ~bx(w)) ~ W ÷ such ha x is an op imal solu ion o P2( ), i.e.: x=p ojs(a* ), wi ha*= ~ Ga. a cA As A is ini e, one has (see, e.g. B onds ed, 1983), iH(A)={z~n/z = ~_,haa o someA~W+}. (**) a cA Hence, a* ~ i H(A), hus x = p ojs(a* ) ~ p ojs( i H(A)). As x was an a bi a y poin in PE(A, S), we ha e PE(A, S) G p ojs( i H(A)) U (A AS). To show he con e se, obse e i s ha he majo i y heo em o Wi zgall (1964) implies ha (An S) c PE(A, S). On he o he hand, o any x ~ p ojs( i H(A)) A, (* *) implies ha 3 ~ W + such ha x sol es P2( ). As x ~A, by (*), x sol es Pl((bx(1))-l), hus x ~ PE(A, S). Hence, PE(S) ~ p ojs( i H(A)) U (A AS), and his comple es he p oo . [] 294 Volume 14, Numbe 5 OPERATIONS RESEARCH LETTERS Decembe 1993 4. Ex ensions The esul s ob ained in his pape can be ex ended in an s aigh o wa d manne o ellipsoidal me ics, i.e.: me ics induced by a scala p oduc . Indeed, o any ellipsoidal me ic d*, he e exis s a egula ma ix T such ha d*(x, y) =d(Tx, Ty) o all x, y. I we deno e by E(A, S; d*) ( espec i ely WE(A, S; d*), PE(A, S; d*)) he se o e icien ( espec- i ely weakly and p ope ly e icien ) poin s o he mul iobjec i e p oblem wi h S as easible se , A as se o demand poin s, and dis ances measu ed by d*, one has: E(A, S; d*) = T -1.E(T'A, " 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 he o he hand, deno ing by p OjS,d, he closes -poin p ojec ion wi h me ic d*, one has p ojs, d*(X) = T -1" p oj .s, d(T'x) and Hence, WE(A, S; d*) =E(A, S; d*) = p oJs, d.(H(A)) PE(A, S; d*) = (A n S) U p oJs, d.( i (H(A))). Ex ensions o he esul s o nonellipsoidal me ics (e.g.,/p-me ics, wi h p ¢ 2) a e no i ial, and a e now unde s udy. Re e ences A. B onds ed (1983), An in oduc ion o Con ex Poly opes. Sp inge -Ve lag, New Yo k. A.M. Geo ion (1968), "P ope e iciency and he heo y o ec o maximiza ion", J. Ma h. Anal Appl. 22, 618-630. H.W. Kuhn (1967), "On a pai o dual nonlinea p og ams", in: J. Abadie (ed.), Nonlinea p og amming, Wiley, New Yo k. O.L. Mangasa ian (1969), Nonlinea P og amming, McG aw-Hill, New Yo k. J.F. Thisse, J.E. Wa d and R.E. Wendell (1984), "Some p ope ies o Loca ion p oblems wi h block and ound no ms", Ope . Res. 32, 1309-1327. C. Wi zgall (1964), "Op imal loca ion o a cen al acili y, ma hema ical models and concep s", Na ional Bu eau o S anda ds Repo 8388. 295