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