Chap e 1
Loca ion P oblems wi h Mul iple C i e ia
S. Nickel, J. Pue o, A.M. Rod ´ıguez-Ch´ıa
Abs ac This chap e analyzes mul ic i e ia con inuous, ne wo k, and disc e e lo-
ca ion p oblems. In he con inuous amewo k, we p o ide a comple e desc ip ion
o he se o weak Pa e o, Pa e o, and s ic Pa e o loca ions o a gene al Q-c i e ia
loca ion p oblem based on he cha ac e iza ion o h ee c i e ia p oblems. In he
ne wo k case, he se o Pa e o loca ions is cha ac e ized o gene al ne wo ks as
well as o ee ne wo ks using he conca i y and con exi y p ope ies o he dis-
ance unc ion on he edges. In he disc e e se ing, he en i e se o Pa e o loca ions
is cha ac e ized using a ional gene a ing unc ions o in ege poin s in poly opes.
Mo eo e , we desc ibe algo i hms o ob ain he solu ions se s ( he di e en Pa e o
loca ions) using he abo e cha ac e iza ions. We also include a de ailed complexi y
analysis. A numbe o e e ences has been ci ed h oughou he chap e o a oid he
inclusion o unnecessa y echnical de ails and also o be use ul o a deepe analysis.
Keywo ds: Pa e o-op imal, Pa e o loca ions, Le el cu es, T ee ne wo ks, Ne -
wo ks, Ra ional unc ions.
S. Nickel
Ins i u e o Ope a ions Resea ch, Ka ls uhe Ins i u e o Technology (KIT), Ka ls uhe, Ge many,
F aunho e Ins i u e o Indus ial Ma hema ics (ITWM), Kaise slau e n, Ge many,
e-mail: s e an.nick[email p o ec ed]
J. Pue o
IMUS, Uni e sidad de Se illa, Spain,
e-mail: pue [email p o ec ed]
A.M. Rod ´ıguez-Ch´ıa
Uni e sidad de C´adiz, C´adiz, Spain,
e-mail: an onio. od iguezc[email p o ec ed]
1
2 Nickel, Pue o, Rod iguez-Ch´ıa
1.1 In oduc ion
Ve y o en, loca ional decisions in ol e he in es men o a signi ican amoun o
money. I will be he e o e e y p obable ha a loca ional decision is made by a
g oup o Qdecision make s (DM). In u n, i is e y likely ha each DM will choose
a median unc ion o e alua e he quali y o a new loca ion, bu he weigh s assigned
o clien s may di e a lo . The same scena io occu s i one loca ion o di e en
ypes o goods has o be ound.
Mul ic i e ia analysis o loca ion p oblems has ecei ed conside able a en ion
wi hin he scope o con inuous, ne wo k, and disc e e models in he las yea s. Fo
an o e iew o gene al me hods as well as o a mo e bibliog aphic o e iew o
he ela ed loca ion li e a u e he eade is e e ed o ?and ?. P esen ly, he e a e
se e al p oblems ha a e accep ed as classical ones: he poin -objec i e p oblem
(see, e.g., ???), he con inuous mul ic i e ia min-sum acili y loca ion p oblem (see,
e.g., ??), he ne wo k mul ic i e ia median loca ion p oblem (see, o ins ance, ??)
and he mul ic i e ia disc e e loca ion p oblem (see, e.g., ?), among o he s.
In con as o p oblems wi h only one objec i e, we do no ha e a na u al o de ing
in highe dimensional objec i e spaces. The e o e, in mul ic i e ia op imiza ion one
has o decide which concep o “op imali y” o choose.
The goal in a mul ic i e ia loca ion p oblem is o op imize simul aneously a se
o objec i e unc ions ( 1,..., Q). The e o e, he o mula ion o he p oblem is:
−min
x∈X⊆IRd( 1(x),..., Q(x)),(1.1)
whe e −min s ands o ec o ial op imiza ion. Obse e ha we ge poin s in a
Q-dimensional objec i e space whe e we do no ha e he canonical o de o IR
anymo e. Acco dingly, o his ype o p oblems, di e en concep s o solu ion
ha e been p oposed in he li e a u e ( he eade is e e ed o ?as a gene al e -
e ence in mul ic i e ia op imiza ion). A poin x∈IRdis called a Pa e o loca ion
(o Pa e o-op imal) i he e exis s no y∈IRdsuch ha q(y)≤ q(x)∀q∈Q:=
{1,...,Q}and p(y)< p(x) o some p∈Q. We deno e he se o Pa e o solu ions
by X∗
Pa  1,..., Qo simply by X∗
Pa i his is possible wi hou causing con usion.
I q(x)≤ q(x′)∀q∈Qand ∃q∈Q: q(x)< q(x′)we say ha xdomina es x′
in he decision space and (x)domina es (x′)in he objec i e space.
Al e na i e solu ion concep s a e weak Pa e o-op imali y and s ic Pa e o-op i-
mali y. A poin x∈IRdis called a weak Pa e o loca ion (o weakly Pa e o-op imal)
i he e exis s no y∈IRd, such ha q(y)< q(x)∀q∈Q.We deno e he se
o weak Pa e o solu ions by X∗
w−Pa  1,..., Qo simply by X∗
w−Pa i his
is possible wi hou causing con usion. A poin x∈IRdis called a s ic Pa e o
loca ion (o s ic ly Pa e o-op imal) i he e exis s no y∈IRd,y6=x, such ha
q(y)≤ q(x)∀q∈Q.Analogously, he se o s ic Pa e o solu ions is deno ed
by X∗
s−Pa  1,..., Q, o simply by X∗
s−Pa i his is possible wi hou causing con-
usion. No e ha X∗
s−Pa ⊆X∗
Pa ⊆X∗
w−Pa and in case we a e conside ing s ic ly
1 Loca ion P oblems wi h Mul iple C i e ia 3
con ex unc ions hese h ee se s coincide. Finally, we ecall ha ?p o ed he con-
nec edness o he se X∗
Pa when he unc ions a e con ex.
In ou p oo s we use he concep o le el se s. Fo a unc ion :IRd→IR he le el
se o a alue
ρ
∈IR is gi en by L≤( ,
ρ
):={x∈IRd: (x)≤
ρ
}( he s ic le el
se is L<( ,
ρ
):={x∈IRd: (x)<
ρ
}) and he le el cu e o a alue
ρ
∈IR is
gi en by L=( ,
ρ
):={x∈IRd: (x) =
ρ
}.Fo a unc ion i(·)we use he no a ion
X∗( i):=a g min
x∈IRd i(x).
Fo wo poin s xand ywe deno e he segmen de ined by xand yas xy.
In his chap e we ocus on some undamen al esul s in he con inuous, ne wo k
and disc e e cases. We will desc ibe in some de ail a comple e geome ic cha ac-
e iza ion o he plana 1- acili y case, an op imal ime algo i hm o he 1- acili y
ne wo k p oblem as well as he compu a ion o he en i e se o Pa e o-op imal solu-
ions o he disc e e mul ic i e ia p-median p oblem. Al hough we a e concen a ing
on he median case we will gi e some ou look o ex ensions.
1.2 1-Facili y Plana /Con inuous Loca ion P oblems
In his sec ion we s udy P oblem (??) whe e 1(·),..., Q(·)a e con ex, in -
compac unc ions, de ined in IR2, which ep esen di e en c i e ia o scena ios.
Recall ha a eal unc ion (·)is said o be in -compac i i s lowe le el se s
{x: (x)≤
ρ
}a e compac o any
ρ
∈IR. The nex esul s a es a use ul cha -
ac e iza ion o he di e en solu ion se s de ined in he p e ious sec ion using le el
se s and le el cu es which will be used la e .
Theo em 1.1. The ollowing cha ac e iza ions hold :
x∈X∗
w−Pa  1,..., Q⇔
Q
q=1
L<( q, q(x)) = /0 (1.2)
x∈X∗
Pa  1,..., Q⇔
Q
q=1
L≤( q, q(x)) =
Q
q=1
L=( q, q(x)) (1.3)
x∈X∗
s−Pa  1,..., Q⇔
Q
q=1
L≤( q, q(x)) = {x}.(1.4)
P oo . I x6∈ X∗
w−Pa  1,..., Q, he e exis s z∈IR2such ha q(z)< q(x) o
each q∈Q, ha means,
z∈
Q
q=1
L<( q, q(x)).
Hence, we ob ain ha
4 Nickel, Pue o, Rod iguez-Ch´ıa
Q
q=1
L<( q, q(x)) 6=/0.
Since he implica ions abo e can be e e sed he p oo is concluded. The emain-
ing esul s can be p o ed analogously. 
Rema k 1.1. Fo he case Q=2 he p e ious esul s a es ha he se X∗
w−Pa ( 1, 2)
coincides wi h angen ial cusps be ween he le el cu es o unc ions 1(·)and 2(·)
union wi h X∗( 1)∪X∗( 2)(see Example ??).
Co olla y 1.1. I 1,..., Qa e s ic ly con ex unc ions hen
X∗
w−Pa ( 1,..., Q) = X∗
Pa  1,..., Q=X∗
s−Pa  1,..., Q.
Example 1.1. (see Figu e ??) Le us conside he poin s a1= (0,0),a2= (8,3),a3=
(−3,5)and he unc ions 1(x) = kx−a1k1, 2(x) = kx−a2k∞, 3(x) = kx−a3k1.
By Theo em ??,X∗
w−Pa ( 1, 2)is he ec ilinea hick pa h joining a1and a2and
X∗
w−Pa ( 1, 3)is he da k ec angle wi h a1and a3as opposi e e ices.
a1
a2
a3
X∗
w−Pa ( 1, 3)
X∗
w−Pa ( 1, 2)
Fig. 1.1 Illus a ion o Example ??.
In wha ollows, since we a e dealing wi h gene al con ex, in -compac unc-
ions, we will ocus on p o iding in o ma ion abou he geome ical s uc u e o
X∗
w−Pa ( 1, 2, 3). This cha ac e iza ion will allow us o ob ain a geome ical de-
sc ip ion o X∗
Pa  1, 2, 3and X∗
s−Pa  1, 2, 3in he nex sec ion o an im-
po an amily o unc ions. Ac ually, we will cha ac e ize X∗
w−Pa ( 1, 2, 3)as a
1 Loca ion P oblems wi h Mul iple C i e ia 5
kind o hull delimi ed by he chains o bic i e ia solu ions o any pai o unc ions
p, qp,q=1,2,3. This esul enables us o ob ain he se X∗
w−Pa  1,..., Qby
union o h ee-c i e ia solu ion se s al eady cha ac e ized. In o de o do ha , le
C∞(IR+
0,IR2):=n
ϕ
|
ϕ
:IR+
0→IR2,
ϕ
con inuous,lim
→∞k
ϕ
( )k2=∞o,
whe e kxk2is he Euclidean no m o he poin x.C∞(IR+
0,IR2)is he se o con inu-
ous cu es, which map he se o non-nega i e numbe s IR+
0:= [0,∞)in o he wo-
dimensional space IR2and whose image
ϕ
(IR+
0)is unbounded in IR2. These cu es
a e in oduced o cha ac e ize he geome ical locus o he poin s su ounded by
weak-Pa e o and Pa e o chains.
Fo a se S⊆IR2we de ine he enclosu e o Sby
encl(S):=x∈IR2:∃
ε
>0 wi h B(x,
ε
)∩S=/0,∃
ϕ
∈[0,∞)wi h
ϕ
(
ϕ
)∈S o all
ϕ
∈C∞(IR+
0,IR2)wi h
ϕ
(0) = x,
whe e B(x,
ε
) = {y∈IR2:ky−xk2≤
ε
}. No e ha S∩encl(S) = /0. In o mally,
encl(S)con ains all he poin s which a e su ounded by S, bu do no belong hem-
sel es o S.
We deno e he union o he bic i e ia chains o weak-Pa e o solu ions by
Xgen
w−Pa  1, 2, 3:=
2
[
p=1
3
[
q=p+1
X∗
w−Pa ( p, q).
We use “gen” since his se will gene a e he se X∗
w−Pa  1, 2, 3. The nex
heo em p o ides use ul geome ic in o ma ion o build X∗
w−Pa  1, 2, 3. I s
p oo can be ound in ?.
Theo em 1.2.
X∗
w−Pa ( 1, 2, 3) = enclXgen
w−Pa  1, 2, 3∪Xgen
w−Pa  1, 2, 3.
Rema k 1.2. I is wo h no ing ha he egion enclXgen
w−Pa  1, 2, 3is well-
de ined because he se Xgen
w−Pa  1, 2, 3is connec ed (see ?).
As an illus a ion o he abo e esul we p esen he ollowing example.
Example 1.2. Le us conside h ee poin s a1= (0,0),a2= (3,−1)and a3= (3,3),
and he unc ions 1(·), 2(·)and 3(·)such ha ,
L≤( 1,1) = (x1,x2):x2
1
4+x2
2
9≤1
L≤( 2,1) = (x1,x2):(x1−3)2+ (x2+1)2≤1
L≤( 3,1) = (x1,x2):(x1−3)2
9+(x2−3)2
4≤1.

6 Nickel, Pue o, Rod iguez-Ch´ıa
We can see ha hese h ee unc ions a e con ex unc ions. The e o e by he p e i-
ous esul we ob ain he geome ical cha ac e iza ion o he se X∗
w−Pa ( 1, 2, 3);
his se is he shadowed egion in Figu e ??.
a1
a2
a3
X∗
w−Pa ( 1, 3)
X∗
w−Pa ( 1, 2)
X∗
w−Pa ( 2, 3)
X∗
w−Pa ( 1, 2, 3)
Fig. 1.2 Illus a ion o Example ??.
Now we a e in he igh posi ion o show he main esul abou he geome ical
s uc u e o X∗
w−Pa ( 1,..., Q).
Theo em 1.3.
X∗
w−Pa ( 1,..., Q) = [
p,q, ∈Q
p<q<
X∗
w−Pa ( p, q, ).
P oo . By Theo em ??,x∈X∗
w−Pa ( 1,..., Q)i and only i
q∈Q
L<( q, q(x)) =
/0. Fu he mo e, by Helly’s heo em (see ?), his in e sec ion is emp y i and only
i he e exis p,q, ∈Q(p<q< )such ha L<( p, p(x)) ∩L<( q, q(x)) ∩
L<( , (x)) = /0 and his is equi alen o x∈X∗
w−Pa ( p, q, ). Since in any
case we ha e ha
[
p,q, ∈Q
p<q<
X∗
w−Pa ( p, q, )⊂X∗
w−Pa ( 1,..., Q),
he esul ollows. 
Rema k 1.3. This esul ex ends p e ious cha ac e iza ions in he li e a u e:
1 Loca ion P oblems wi h Mul iple C i e ia 7
- Taking i(x) = kx−aikwi h ai∈IR2 o i=1,...,Qand k · k being a s ic ly
con ex no m o a no m de i ed om a scala p oduc , we ge P oposi ion 1.3,
Theo em 4.3 and Co olla y 4.1 in ?. The se o weakly e icien loca ions is he
con ex hull o he poin s aiwi h i=1,...,Q. In Example ??, we illus a e his
esul .
- Taking i(x) = kx−aikwi h ai∈IR2 o i=1,...,Qand k·k being a polyhed al
gauge we ge Theo em 6.1 in ?, whe e he se o weakly e icien loca ions is
he union o elemen a y con ex se s, (see ? o a de ini ion). In Example ??, we
illus a e his esul .
- Taking i(x) = maxj∈Mwijkx−ajkwi h aj∈IR2,wij>0 o i=1,...,Q,j∈
M:={1,...,m}and k · k being he ℓ∞-no m, we ge Theo em 6.1 in ?, whe e
he se o weakly e icien loca ions is he union o he se s o weakly e icien
loca ions o all pai s o unc ions. In Example ??, we illus a e he use o his
esul .
Example 1.3. (See Figu e ??) Le us conside he poin s a1= (0,0),a2= (5,−10),
a3= (10,0)and he unc ions i(x) = kx−aik2 o i=1,2,3. By Theo em ??,
X∗
w−Pa ( 1, 2, 3)is he da k egion, which in his case is he con ex hull o a1,a2
and a3.
a1
a2
a3
X∗
w−Pa ( 1, 2, 3)
Fig. 1.3 Illus a ion o Example ??.
Example 1.4. (See Figu e ??) Le us conside he poin s a1= (0,0),a2= (8,3),
a3= (−3,5)and he unc ions 1(x) = kx−a1k1, 2(x) = kx−a2k∞and 3(x) =
kx−a3k1. By Theo em ??,X∗
w−Pa ( 1, 2)is he hick pa h joining a1and a2,
X∗
w−Pa ( 2, 3)is he hick pa h joining a2and a3, and X∗
w−Pa ( 1, 3)is he da k
ec angle wi h a1and a3as opposi e ex eme poin s. The e o e, by Theo em ??,
X∗
w−Pa ( 1, 2, 3)is he da k egion su ounded by he union o he h ee p e ious
se s. No e ha his egion is he union o wo ull dimensional elemen a y con ex
se s.
Example 1.5. (See Figu e ??) Le us conside he poin s a1= (4,16),a2= (10,5),
a3= (25,12)and he unc ions i(x) = kx−aik∞ o i=1,2,3. By Theo em ??,
8 Nickel, Pue o, Rod iguez-Ch´ıa
a1
a2
a3
X∗
w−Pa ( 1, 3)
X∗
w−Pa ( 1, 2)
X∗
w−Pa ( 2, 3)
X∗
w−Pa ( 1, 2, 3)
Fig. 1.4 Illus a ion o Example ??.
X∗
w−Pa ( 1, 2) = R1,X∗
w−Pa ( 1, 3) = R2∪R4,X∗
w−Pa ( 2, 3) = R3∪R4. By
Theo em ??,X∗
w−Pa ( 1, 2, 3) = R1∪R2∪R3∪R4. No e ha in his example
X∗
w−Pa ( 1, 2, 3) = X∗
w−Pa ( 1, 2)∪X∗
w−Pa ( 1, 3)∪X∗
w−Pa ( 2, 3).
a1
a2
a3
R4
R1
R2
R3
b
b
b
Fig. 1.5 Illus a ion o Example ??.
1.2.1 Polyhed al Plana Minisum Loca ion P oblems
Conside a se o demand poin s A:={a1,...,aM} ⊆ IR2. Le Bi⊂IR2, o i∈M:=
{1,2,...,M}, be a compac , con ex se con aining he o igin in i s in e io . The
1 Loca ion P oblems wi h Mul iple C i e ia 9
gauge wi h espec o Biis de ined as
γ
i:IR2→IR,
γ
i(x):=in { >0 : x∈ Bi}.
Taking his de ini ion in o accoun , he plana minisum loca ion p oblem is
min
x∈IR2
M
∑
i=1
wi
γ
i(x−ai),
whe e wiis a nonnega i e weigh associa ed wi h he demand poin ai(i∈M).
In his sec ion we s udy he pa icula case whe e he unc ions 1,..., Qa e
minisum loca ion objec i e unc ions and he dis ances a e measu ed wi h polyhe-
d al gauges, i.e., he uni balls associa ed wi h hese gauges a e con ex poly opes.
This ype o objec i e unc ion is no s ic ly con ex and o his eason, he h ee so-
lu ions se s (Pa e o, weak Pa e o and s ic Pa e o loca ions) do no coincide. The e-
o e, in his sec ion we ocus on he cha ac e iza ion o he Pa e o loca ions and how
i can be ex ended o he emaining solu ion se s.
b b
p1+N(B0, p1)
p2+N(B0, p2)
(0,0)
(0,0)
d1
d2
d3
d4
e1
e2
e3
e4
BB0
p1
p2
Fig. 1.6 Illus a ion o he uni ball o he ℓ1-no m, i s dual ball and wo no mal cones o his
dual ball.
The pola se Bo
io Biis gi en by Bo
i:={p∈IR2:hp,xi ≤ 1∀x∈Bi}and he
no mal cone o Bia xis gi en by N(Bi,x):={p∈IR2:hp,y−xi ≤ 0∀y∈Bi},
whe e h·,·i deno es he scala p oduc . In case o polyhed al gauges (i.e., Biis a
poly ope), he se o ex eme poin s o Biis deno ed by Ex (Bi):={ei
1,...,ei
Gi}.
The maximal numbe o ex eme poin s is deno ed by Gmax :=max{Gi:i∈M}.
We de ine undamen al di ec ions di
1,...,di
Gias he hal -lines de e mined by 0 and
ei
1,...,ei
Gi(see Figu e ??).
Le
π
= (pi)i∈Mbe a amily o elemen s o IR2such ha pi∈Bo
i o each i∈M
and le C
π
=Ti∈M(ai+N(Bo
i,pi)). Acco ding o ?, a nonemp y con ex se C is
called an elemen a y con ex se i he e exis s a amily
π
such ha C
π
=C. I he uni
balls a e poly opes, hen we can ob ain he elemen a y con ex se s as in e sec ions
o cones gene a ed by undamen al di ec ions o hese balls poin ed a each demand
poin ( o de ails, see ?). The 2-dimensional elemen a y con ex se s a e called cells.
Le Cdeno e o he se o hese cells. The e o e each cell is a polyhed on whose
16 Nickel, Pue o, Rod iguez-Ch´ıa
enclXgen
Pa  1, 2, 3⊆X∗
Pa  1, 2, 3
⊆Xgen
Pa  1, 2, 3∪enclXgen
Pa  1, 2, 3
=X∗
w−Pa  1, 2, 3.
P oo . Using Lemma ?? and Theo em ?? we ha e he ollowing chain o inclusions
ha p o es he hesis o he heo em.
enclXgen
Pa  1, 2, 3⊆X∗
s−Pa  1, 2, 3
⊆X∗
Pa  1, 2, 3⊆X∗
w−Pa  1, 2, 3
⊆Xgen
Pa  1, 2, 3∪enclXgen
Pa  1, 2, 3.
Now i emains o conside he Pa e o-op imali y o he se Xgen
Pa  1, 2, 3
wi h espec o he h ee objec i e unc ions 1, 2, 3. Fo a cell C∈Cwe de ine
he collapsing and he emaining pa o Cwi h espec o Q-c i e ia op imali y by
colQ(C):=x∈C:x/∈X∗
Pa  1,..., Q
emQ(C):=x∈C:x∈X∗
Pa  1,..., Q.
Summing up he p eceding esul s we ge a comple e geome ic cha ac e iza-
ion o he se o Pa e o solu ions o he h ee c i e ia case. Fo each cell C,
colQ(C)˙
∪ emQ(C) = Cand, as shown by ?, de e mining bo h se s can be done wi h
he g adien s o he objec i e unc ions wi h a complexi y o O(QlogQ).
Theo em 1.6. The se o Pa e o solu ions sa is ies:
X∗
Pa  1, 2, 3=Xgen
Pa  1, 2, 3∪enclXgen
Pa  1, 2, 3
{x∈IR2:∃C∈C,C⊆Xgen
Pa  1, 2, 3,x∈col3(C)}.
P oo . Le y∈X∗
Pa  1, 2, 3. Then we ha e, by Theo em ??, ha
y∈Xgen
Pa  1, 2, 3∪enclXgen
Pa  1, 2, 3.Mo eo e o C∈Cwi h y∈C
we ha e y∈ em3(C), i. e., y/∈col3(C). This implies
y∈Xgen
Pa  1, 2, 3∪enclXgen
Pa  1, 2, 3
{x∈IR2:∃C∈C,C⊆Xgen
Pa  1, 2, 3,x∈col3(C)}.
We dis inguish he ollowing cases :
Case 1: y∈enclXgen
Pa  1, 2, 3. Then y∈X∗
Pa  1, 2, 3by Theo em ??.
Case 2 : y∈Xgen
Pa  1, 2, 3.
Case 2.1 : ∃C∈C,C⊆Xgen
Pa  1, 2, 3wi h y∈C
⇒y/∈col3(C)⇒y∈ em3(C)⇒y∈X∗
Pa  1, 2, 3.
Case 2.2 : 6 ∃C∈C,C⊆Xgen
Pa  1, 2, 3wi h y∈C

1 Loca ion P oblems wi h Mul iple C i e ia 17
⇒L≤( p, p(y))∩L≤( q, q(y)) = {y} o some p,q∈ {1,2,3},p<q
⇒T3
q=1L≤( q, q(y)) = {y} ⇒ y∈X∗
s−Pa  1, 2, 3⊆X∗
Pa  1, 2, 3.
In he case o median unc ions he g adien s ∇ q(x),q∈ {1,2,3},(in hose
poin s whe e hey a e well-de ined) can be compu ed in O(Mlog(Gmax)) ime (anal-
ogous o he e alua ion o he unc ion). The e o e, we can es in O(Mlog(Gmax))
ime i a cell C∈C,C⊆Xgen
Pa  1, 2, 3collapses. We ob ain he ollowing algo-
i hm o he 3-c i e ia median p oblem wi h ime complexi y O(M3G2
max log(Gmax))
(see ? o mo e de ails).
Algo i hm 1.2.
S ep 1. Compu e he he subdi ision o he plane gene a ed C, he amily o elemen-
a y con ex se s. Compu e X∗
w−Pa  1, 2,X∗
w−Pa  1, 3,X∗
w−Pa  2, 3
using Algo i hm ??.
S ep 2. Se Xgen
Pa  1, 2, 3:=X∗
w−Pa  1, 2∪X∗
w−Pa  1, 3∪X∗
w−Pa  2, 3
and X∗
Pa  1, 2, 3:=Xgen
Pa  1, 2, 3∪enclXgen
Pa  1, 2, 3.
S ep 3. Fo any C∈Cwi h C⊆Xgen
Pa  1, 2, 3compu e col3(C)and se
X∗
Pa  1, 2, 3:=X∗
Pa  1, 2, 3 col3(C).
Ou pu :
X∗
Pa  1, 2, 3.
Figu e ?? illus a es he p eceding esul s using he da a in oduced in Exam-
ple ??. The dashed pa h joining X∗
1and X∗
3in he pic u e ep esen s he se
X∗
w−Pa  1, 3a e emo ing he col3(C). In he same way, he pa h joining X∗
1
and X∗
2 ep esen s he se X∗
w−Pa  1, 2a e emo ing he col3(C). Finally, he
do ed segmen joining X∗
2and X∗
3is X∗
w−Pa  2, 3(in his case he e a e no
cells o be collapsed).
b b
b
b b
b
b b
b
s
s
s
a1a2
a3
a4a5
a6
a7a8
a9
X∗
1
X∗
3
X∗
2
Fig. 1.12 Illus a ion o Xgen
Pa  1, 2, 3and X∗
Pa  1, 2, 3 o he p oblem in oduced in
Example ??.
18 Nickel, Pue o, Rod iguez-Ch´ıa
1.2.1.3 Case whe e Q>3
In his sec ion we conside he gene al Q-C i e ia case (Q>3). We p o e ha he
Pa e o solu ion se can be ob ained om he Pa e o solu ion se s o all he h ee
c i e ia p oblems. This cons uc ion equi es he emo al o he domina ed poin s
om he union o all he h ee c i e ia Pa e o solu ion se s. The eade may no ice
ha all his p ocess educes o ob aining he bic i e ia Pa e o chains as p o ed in
Theo em ??.
Theo em 1.7. The ollowing inclusions hold:
1. [
p,q, ∈Q
p<q<
clenclXgen
Pa ( p, q, )⊆X∗
Pa  1,..., Q.
2. X∗
Pa  1,..., Q⊆[
p,q, ∈Q
p<q<
Xgen
Pa ( p, q, )∪[
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, )=
X∗
w−Pa  1,..., Q.
P oo . (1) Le x∈S
p,q, ∈Q
p<q<
clenclXgen
Pa ( p, q, ). This is equi alen o
x∈clenclXgen
Pa ( p, q, ) o some p,q, ∈Q,p<q< .
Then, by Lemma ??,x∈X∗
s−Pa ( p, q, ) o some p,q, ∈Q,p<q< . Ap-
plying cha ac e iza ion (??), his is equi alen o L≤( p, p(x)) ∩L≤( q, q(x)) ∩
L≤( , (x)) = {x} o some p,q, ∈Q,p<q< and since x∈L≤( q, q(x))
o all q∈Qi ollows ha TQ
q=1L≤( q, q(x)) = {x}. Finally, again by (??),
x∈X∗
s−Pa  1,..., Q, which implies ha x∈X∗
Pa  1,..., Q.
(2) Le x∈X∗
Pa  1,..., Q hen x∈X∗
w−Pa  1,..., Qand, by (??), his is
equi alen o TQ
q=1L<( q, q(x)) = /0. By Helly’s heo em, he e exis s p,q, ∈
Q,p<q< , such ha , L<( p, p(x)) ∩L<( q, q(x)) ∩L<( , (x)) = /0. By
cha ac e iza ion (??), his is equi alen o x∈X∗
w−Pa ( p, q, ) o some p,q, ∈
Q,p<q< and, by Theo em 3.2 in ?, his implies ha x∈Xgen
Pa ( p, q, )∪
enclXgen
Pa ( p, q, ) o some p,q, ∈Q,p<q< . Finally, his can be equi -
alen ly w i en as
x∈[
p,q, ∈Q
p<q<
Xgen
Pa ( p, q, )∪[
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, ).

In he Q-c i e ia case he c ucial egion is now gi en by he cells C∈Cwi h
C⊆[
p,q, ∈Q
p<q<
Xgen
Pa ( p, q, ) [
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, )
1 Loca ion P oblems wi h Mul iple C i e ia 19
=[
p,q∈Q
p<q
X∗
w−Pa ( p, q) [
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, ).
Simila o he si ua ion in he p e ious sec ion one can es whe he he cell C∈C
collapses wi h espec o 1,..., Qby compa ing he g adien s o he objec i e
unc ions in in (C). Finally we ob ain he ollowing heo em, which can be p o en
using he same easoning as in he 3-c i e ia case (see p oo o Theo em ??).
Theo em 1.8.
X∗
Pa  1,..., Q=
S
p,q, ∈Q
p<q<
Xgen
Pa ( p, q, )∪S
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, )




x∈IR2:∃C∈C,C⊆S
p,q∈Q
p<q
X∗
w−Pa ( p, q) S
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, ),x∈colQ(C)


Fo he Q-c i e ia median p oblem we ob ain he ollowing algo i hm.
Algo i hm 1.3.
S ep 1. Compu e he he subdi ision o he plane gene a ed C, he amily o elemen-
a y con ex se s. Compu e X∗
w−Pa ( p, q),p,q∈Q,p<q,using Algo i hm ??.
S ep 2. Se o any p,qand wi h p<q<
Xgen
Pa ( p, q, ):=X∗
w−Pa ( p, q)∪X∗
w−Pa ( p, )∪X∗
w−Pa ( q, ),
and
X∗
Pa  1,..., Q:=S
p,q, ∈Q
p<q<
Xgen
Pa ( p, q, )∪S
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, ).
S ep 3. Fo e e y cell C⊆S
p,q∈Q
p<q
X∗
w−Pa ( p, q) S
p,q, ∈Q
p<q<
enclXgen
Pa ( p, q, )
compu e colQ(C)and se X∗
Pa  1,..., Q:=X∗
Pa  1,..., Q colQ(C).
Ou pu :
X∗
Pa  1,..., Q.
The complexi y o Algo i hm ?? can be de e mined as ollows. Fo each cell
C,colQ(C)can be compu ed in O(Qlog(Q)) ime. Algo i hm ?? needs o sol e
O(Q3) h ee-c i e ia p oblems which domina es all o he elemen a y ope a ions o
he algo i hm. Each one o hem has he same complexi y as he wo-c i e ia p ob-
lem. Thus, he o e all complexi y is O(M3G2
maxQ3(logGmax) + M2G2
maxQlogQ) =
O(M3G2
maxQ3(logGmax).
We would like o conclude his sec ion poin ing ha he mul i- acili y e sions
o he p oblems analyzed in his sec ion ha e been ha dly s udied in he li e a u e,
al hough an excep ion is he pape by ?.
20 Nickel, Pue o, Rod iguez-Ch´ıa
1.3 Ne wo k Loca ion P oblems
1.3.1 1-Facili y Median P oblems
1.3.1.1 Pa e o Loca ions in Gene al Ne wo ks
Le G= (V,E)be a connec ed g aph wi h node se V={ 1,..., n}and edge se
E={e1,...,em}. Each edge e∈Ehas a posi i e leng h ℓ(e), and is assumed o be
ec i iable. Le P(G)deno e he con inuum se o poin s on edges o G. We deno e a
poin x∈e={u, }as a pai x= (e, ), whe e (0 ≤ ≤1) gi es he ela i e dis ance
o x om node ualong edge e. Fo he sake o eadabili y, we iden i y P(G)wi h
Gand P(e)wi h e o e∈E. We also de ine (e,( 1, 2)) :={x= (e, ): ∈( 1, 2)};
(e,[ 1, 2]),(e,( 1, 2]), and (e,[ 1, 2)) a e used in an analogous way.
We deno e by d(x,y) he leng h o he sho es pa h connec ing wo poin s x,y∈
G. Le i∈Vand x= ({ , s}, )∈G. The dis ance om i o xen e ing he edge
{ , s} h ough ( s) is gi en as D+
i(x) = d( ,x) + d( , i)(D−
i(x) = d( s,x)+
d( s, i)). Hence, he leng h o a sho es pa h om i o xis gi en by Di(x) =
min{D+
i(x),D−
i(x)}. As d( ,x) = ·ℓ(e)and d( s,x) = (1− )·ℓ(e), he unc ions
D+
i(x)and D−
i(x)a e linea in xand Di(x)is piecewise linea and conca e in x
(c . ?). The dis ance om i o a acili y loca ed a xis inally de ined as d( i,x) =
Di(x) = min{D+
i(x),D−
i(x)}.
We conside he objec i e unc ion (x) = ( 1(x),..., Q(x)), whe e each q(x),
q∈Q, is a median unc ion de ined as:
q(x) = ∑
i∈V
wq
id( i,x).
Mo e o mally, we assign a ec o o weigh s
wi=


w1
i
.
.
.
wQ
i


6=0 o e e y e ex i∈V,wi h wq
i≥0,q∈Q:={1,...,Q}.
The quali y o a poin x∈P(G)in his mul ic i e ia se ing is de ined by
(x):=


1(x)
.
.
.
Q(x)


:=


∑ i∈Vw1
id(x, i)
.
.
.
∑ i∈VwQ
id(x, i)



in he undi ec ed case and
(x):=


1(x)
.
.
.
Q(x)


:=


∑ i∈Vw1
i(d(x, i) + d( i,x))
.
.
.
∑ i∈VwQ
i(d(x, i) + d( i,x))



1 Loca ion P oblems wi h Mul iple C i e ia 21
in he di ec ed case.
Le S⊆P(G)and W⊆IRQ. We de ine Wpa ={ (x)∈W:∄ (y)∈Wsuch ha
(y)domina es (x)in he objec i e space}and X∗
pa :={x∈S: (x)∈Wpa }. I
S=P(G)we simply w i e X∗
pa . A poin x∈X∗
pa (S)is called a Pa e o loca ion
wi h espec o S, and he elemen s o X∗
pa (V)a e called Pa e o nodes o Pa e o
e ices.
Compu ing X∗
pa (V)can simply be done by pai wise compa ision o he nodes.
Fo X∗
pa we i s ha e o check i a mul ic i e ia e sion o Hakimi’s node domi-
nance esul holds (?). Fo he di ec ed case we e en ha e X∗
pa (V) = X∗
pa . The
p oo elies on he conca i y o he dis ance unc ions among he edges and also on
he ac ha in he di ec ed case we ha e no choice on which side o exi o en e
an edge. This implies ha he objec i e unc ion is s ic ly conca e and he e o e
he nodes always domina e he edges. Fo he echnical de ails and he p oo s he
eade is e e ed o ?. In he case o undi ec ed ne wo ks, his aspec is sligh ly
mo e complica ed as shown in he nex example.
Example 1.7. Conside he ollowing ne wo k N= (G,ℓ)wi h n=6 nodes and a
dis ance ma ix D= (di j)i,j=1,...,6gi en by
D=








0 1 1 4 3 2
1 0 2 3 4 1
1 2 0 3 2 3
4 3 3 0 5 2
3 4 2 5 0 3
2 1 3 2 3 0








.
1 2
3 4
5 6
1
3
3
1
3
3
1
22
Fig. 1.13 Ne wo k o Example ??.
Assume ha he weigh ec o s a e
w1=1
2,w2=2
1,w3=1
2,w4=2
2,w5=2
2,w6=2
1.
Using his in o ma ion we ge

22 Nickel, Pue o, Rod iguez-Ch´ıa
1 2 3 4 5 6
(·)21
1919
2121
1727
2929
2717
21
By pai wise compa ison we ge
X∗
pa (V) = { 3} ∪ { 6}=X∗ 1(V)∪X∗ 2(V).
Now we look a he poin s on he edges and ge (by using conca i y in he objec i e
unc ions):
• 3domina es all poin s on he edges { 3, 5},{ 3, 4},{ 3, 1}
• 6domina es all poin s on he edges { 6, 2},{ 6, 5},{ 6, 4}
• 2domina es all poin s on he edge { 2, 4}
• 1domina es all poin s on he edge { 1, 5}
We also obse e ha no e ex can domina e a poin wi h bo h objec i e unc ions
smalle han 21. The only edge le is now { 1, 2}.
19
20
21
22
19
20
21
22
0 1
2
1
Fig. 1.14 Objec i e unc ions on he edge { 1, 2}in Example ??.
We see ha
1. Fo all poin s x∈P({ 1, 2})wi h x6= 1,x6= 2we ha e 1(x)<21, 2(x)<21.
2. No poin on { 1, 2}domina es ano he poin on { 1, 2}
⇒X∗
pa ={ 3} ∪ { 6} ∪ ({ 1, 2},(0,1)).
We conclude ha we ha e no node dominance and ha e en on edges wi h
endnodes no in X∗
pa (V)we can ind elemen s o X∗
pa .
Since we do no ha e node dominance in he undi ec ed case, we ha e o explic-
i ly sol e a mul ic i e ia global op imiza ion p oblem. Fi s we will iden i y local
Pa e o loca ions wi h espec o an edge e={ i, j} o all edges o he ne wo k. In
a second s ep we will compa e all local Pa e o loca ions o ge X∗
pa . Due o he lim-
i ed space and a possible o e load o echnicali ies, we will desc ibe he main ideas
which allow he eade o unde s and he inal algo i hm. Fo he echnical de ails
and he p oo s he eade is e e ed o ?.
1 Loca ion P oblems wi h Mul iple C i e ia 23
1.3.1.2 Bi-c i e ia Case
We will i s deal wi h he bi-c i e ia case, since he e we can de i e a geome ical
solu ion me hod. The main p ope y o he objec i e unc ions we a e using is he
conca i y on an edge e={ i, j}. In addi ion we ha e also piecewise linea i y bu
his is no eally needed. Suppose ha ( i)> ( j)o ( j)> ( i). In he i s
si ua ion we say ha jdomina es iand in he la e idomina es j. Bo h si ua ions
do no allow any loca ion on he edge, which is no domina ed by an endnode due
o conca i y.
Now assume ha o an edge e={ i, j}wi h iand jno domina ing each
o he one o he unc ions 1o 2is cons an . I is easy o see ha his is only he
case i ( i) = ( j). I o an edge eonly one o he objec i e unc ions is cons an
hen X∗
pa (e) = { i}∪{ j}. I bo h objec i e unc ions a e cons an hen X∗
pa (e) =
({ i, j},[0,1]). Again his is due o he conca i y o he objec i e unc ions and can
be seen in Figu e ??.
0 1
2
1
Fig. 1.15 Conca i y on an edge wi h one objec i e unc ion cons an .
Now we ha e only one si ua ion le ( he mos ypical one), whe e he endnodes
do no domina e each o he and none o he wo objec i e unc ions is cons an .
Wi hou loss o gene ali y we can assume 1( i)> 1( j)and 2( i)< 2( j)(o h-
e wise exchange he oles o iand j). The beha iou o he objec i e unc ions
can be seen in Figu e ??. Fi s , bo h objec i es unc ions a e inc easing (maybe o
a small o ze o in e all only) and all poin s a e domina ed by he le endnode.
Only a e he i s objec i e unc ion is al eady dec easing and smalle han he le
endnode alue, he endnode canno domina e he poin s o he edge. The same a -
gumen can be applied by s a ing om he igh endnode. Mo e o mally we can
de ine
1:=max{ ∈[0,1]: 1( i) = 1(({ i, j}, ))}
and
2:=min{ ∈[0,1]: 2( j) = 2(({ i, j}, ))}
24 Nickel, Pue o, Rod iguez-Ch´ıa
Then
X∗
pa (e) = { i} ∪ { j} ∪ { i, j}, 1, 2.
0 1
1 2
1
2
Fig. 1.16 De i a ion o 1and 2.
O e all we ha e ha o each e∈Ein (G,ℓ),X∗
pa (e)is a (possibly emp y) single
subedge o eplus one o bo h endnodes. Now we can combine hese esul s o ge
an e icien algo i hm o de e mining X∗
pa (e).
Algo i hm 1.4. (Compu a ion o X∗
pa (e))
Inpu : edge e={ i, j} ∈ E, undi ec ed ne wo k (G,l), dis ance ma ix D
S ep 1. IF idomina es j hen X∗
pa (e):={ i}, go o S ep 7
S ep 2. IF jdomina es i hen X∗
pa (e):={ j}, go o S ep 7
S ep 3. IF ( i) = ( j) hen
a. IF { i, j},1
2= ( i) hen X∗
pa (e):=P({ i, j}), go o S ep 7
b. IF { i, j},1
26= ( i) hen X∗
pa (e):={ i} ∪ { j}, go o S ep 7
S ep 4. IF 1( i)< 1( j)and 2( i)> 2( j) hen exchange iand j
S ep 5. Compu e 1and 2as de ined abo e
S ep 6. IF 1< 2
THEN X∗
pa (e):={ i} ∪ { j} ∪ { i, j},( 1, 2)
ELSE X∗
pa (e):={ i} ∪ { j}
Ou pu : X∗
pa (e)
To analyze he complexi y o his algo i hm, we need he ollowing de ini ion: A
poin x= ({ i, j}, ), ∈[0,1]on one edge e={ i, j}is called a bo leneck poin
o qi he e exis s a e ex kwi h wq
k>0, such ha
d( k,x) = d( k, i) + d( i,x) = d( k, j)+ d( j,x).
1 Loca ion P oblems wi h Mul iple C i e ia 25
Le Bi j deno e he se o bo leneck poin s on he edge { i, j}. No e ha |Bi j| ≤ |V|.
I Dis gi en, he only non cons an ope a ion in Algo i hm ?? is he compu-
a ion o 1and 2. To plo qwe ha e o de e mine he b eakpoin s o qwhich
is piecewise linea on an edge. Since hese b eakpoin s co espond o he bo -
leneck poin s on his edge we ha e o compu e Bi j o e={ i, j}. This can
be done in O(|V|log|V|)(see ?). Then 1and 2can be de e mined by explo -
ing he so ed lis o bo leneck poin s wo imes. The o al complexi y o ind-
ing X∗
pa (e)is O(|V|log|V|)and he o al complexi y o inding Se∈EX∗
pa (e)is
O(|E||V|log|V|).
Example 1.8. Conside he ollowing ne wo k:
1 2
3 4
1
1
1
2
1
3 2
1
2
12
2
Fig. 1.17 Ne wo k o Example ??.
wi h dis ance ma ix
D=



0 1 2 2
1 0 2 1
2 2 0 1
2 1 1 0



.
We i s compu e
1 2 3 4
110 7 8 6
27 8 9 9
and ob ain X∗
pa (V) = { 1, 2, 4}. Now we ha e o de e mine he se X∗
pa (e) o
e e y e∈E:
•e={ 1, 2}. 1and 2do no domina e each o he and 1, 2a e no cons an ,
i.e., we need o plo 1, 2and he e o e we ha e o ind B12
B12 =b1
12 ={ 1, 2},1
2
1b1
12=9.5 and 2b1
12=8.5
So he objec i e unc ion can be d awn as shown in Figu e ??.
32 Nickel, Pue o, Rod iguez-Ch´ıa
Theo em 1.9. Le a,b∈P(T)and h := (h1,...,hQ)be a ec o o Q objec i e unc-
ions, wi h hqcon ex on T , o all q ∈Q={1,...,Q}. Then he ollowing holds:
{a,b} ⊆ X∗
pa i and only i L[a,b]⊆X∗
pa .
Fo T= (V,E)and V′⊆Vle
W(V′):=




w1(V′)
w2(V′)
.
.
.
wQ(V′)





,
whe e wq(V′):=∑ i∈V′wq
i,∀q∈Q.
P oposi ion 1.1. Le T be pa i ioned in such a way ha T =T1∪T2∪ {e}(and
T1∩T2=/0). Then W(V(T1)) domina es W (V(T2)) i and only i o all x ∈P(T1)
he e exis s some y ∈P(T2)which domina es x.
Now we can s a e a mul ic i e ia e sion o Goldman’s dominance algo i hm (see
?). We s a wi h a sub ee con aining only one lea o he ee (check o dominance)
and enla ge his sub ee un il we ge a Pa e o loca ion using he c i e ion es ablished
in P oposi ion ??. This p ocedu e is hen epea ed o all lea es and we end up wi h
a sub ee o all Pa e o loca ions by using Theo em ??.
Algo i hm 1.7. (Sol ing Q-c i e ia median p oblems on a ee)
Inpu : T= (V,E), wi h leng h unc ion ℓand node weigh ec o s wq,q∈Q.
S ep 0. Se W:=W(V)
S ep 1. Choose a lea ko T, which was no ye conside ed and gi e i he s a us
“conside ed”.
S ep 2. IF V={ k}
Se X∗
pa ( (V)) :=X∗
pa ( (T)) :={ k}and go o S ep 6
S ep 3. Le lbe he only node adjacen o k
IF (w1
k...wQ
k)T<1
2W
THEN
•wq
l:=wq
l+wq
k,q=1,...,Q
•T:=T { k}
S ep 4. IF he e a e any lea es le in Tgi e hem s a us “no conside ed”
and go o S ep 1
S ep 5. Se X∗
pa ( (V)) :=V(T),X∗
pa ( (T)) :=T
S ep 6. STOP
Ou pu : X∗
pa ( (V)) and X∗
pa ( (T))
The complexi y o his algo i hm is O(Q|V|). To illus a e he algo i hm conside
he ollowing example:

1 Loca ion P oblems wi h Mul iple C i e ia 33
Example 1.10. Conside he ee depic ed in Figu e ??. We sol e he ollowing in-
s ance o a 3-c i e ia median p oblem. Le l(e):=1, ∀e∈E. The weigh s o he
nodes a e gi en in he ollowing able:
1 2 3 4 5 6 7 8 9 10 11
w114 6 8 4 1 2 1 3 2 2 7
w211 3 3 24 5 2 2 3 2 2 5
w316 2 1 1 2 3 3 1 6 4 21
The e o e W=

50
62
60 
and 1
2W=

25
31
30 
.
The adjacency s uc u e o he ee is also gi en in Figu e ??. Now we check e e y
lea ill he e is none le wi h s a us “no conside ed”.
1
2
3 4
5
6
7
8
9
10
11
Fig. 1.24 T ee o Example ??. The bold edges and nodes indica e he se o Pa e o loca ions.
•Take 1:w1=

14
11
16 
domina es W
2=

25
31
30 
.
The e o e w2:=

6+14
3+11
2+16
=

20
14
18 
.
By ollowing he algo i hm we dele e 8, 7, 6, 5and 4. The ac ual alue o w3is


13
32
4
.
34 Nickel, Pue o, Rod iguez-Ch´ıa
•Take 3:w3=

13
32
4
does no domina e W
2.
•Take 11:w11 =

7
5
21 
domina es W
2. The e o e w9:=

9
7
27 
.
•Take 10:w10 =

2
2
4
domina es W
2. The e o e w9:=

11
9
31 
.
•Take 9:w9=

11
9
31 
does no domina e W
2.
Since we dele e a e e e y domina ion s ep he co esponding node om he ee
acco ding o Algo i hm ?? and no lea wi h s a us no conside ed is le we end up
wi h
X∗
pa =L[ 9, 3].
1.3.2 O he Mul ic i e ia Loca ion P oblems on Ne wo ks
In he p e ious wo subsec ions we p esen ed op imal ime algo i hms o one acil-
i y median p oblems when looking o Pa e o loca ions. We chose hese wo p ob-
lems because he eade ge s some insigh in o he needed p ope ies. In addi ion, he
simpli ica ion on ees caused by he uniqueness o pa hs can be seen. In he ecen
su ey ?an o e iew on o he loca ion p oblems can be ound. In ?an ex ension o
1- acili y cen e p oblems as well as o posi i e and nega i e weigh ec o s on he
nodes is de eloped. Those ideas ha e been u he ex ended o p oblems wi h c i-
e ia dependen leng hs in ?. A uni ied amewo k o mul ic i e ia o de ed median
unc ions can be ound in ?. In ? he loca ion o undesi able acili ies on mul ic i e-
ia ne wo ks is looked a by using con ex combina ions o wo objec i e unc ions.
Some complexi y analysis o he cen -dian loca ion p oblem has been de elopped
by ?. Mos app oaches o he (in gene al NP-ha d) mul i- acil y case a e ea ed as
disc e e loca ion p oblems (see Sec ion ??). Only ecen ly ?s a ed looking in o
polynomial cases o mul i- acili y mul ic i e ia loca ion p oblems on ne wo ks.
1.4 Disc e e Loca ion P oblems
The p e ious sec ions show ha plana and ne wo k mul ic i e ia loca ion p oblems
ha e been widely de eloped om a me hodological poin o iew so ha impo -
an s uc u al esul s and algo i hms a e known o de e mine solu ion se s. On he
1 Loca ion P oblems wi h Mul iple C i e ia 35
con a y, mul ic i e ia analysis o disc e e loca ion p oblems has a ac ed less a -
en ion. In spi e o ha , se e al au ho s ha e deal wi h p oblems and applica ions
o mul ic i e ia decision analysis in his ield. An anno a ed bibliog aphy wi h many
e e ences up o 2005 can be ound in ?. In gene al, e y ew pape s ocus in he
comple e de e mina ion o he whole se o Pa e o-op imal solu ions. Ne e heless,
he e a e some excep ions, such as he pape by ? ha gi es a heo e ical cha ac-
e iza ion bu does no exploi i s algo i hmic possibili ies, as well as he wo k by
? ha add esses he compu a ion o he en i e se o Pa e o-op imal solu ions o he
mul iobjec i e uncapaci a ed plan loca ion p oblem.
Nowadays, Mul i-Objec i e Combina o ial Op imiza ion (MOCO) (see ??) p o-
ides an adequa e amewo k o ackle a ious ypes o disc e e mul ic i e ia p ob-
lems as, o ins ance, he p-Median P oblem (p-MP). Wi hin his eme gen esea ch
a ea, se e al me hods a e known o handle di e en p oblems. I is wo h no ing
ha mos o MOCO p oblems a e NP-ha d and in ac able (see ?, o u he de-
ails). E en in mos o he cases whe e he single objec i e p oblem is polynomially
sol able he mul iobjec i e e sion becomes NP-ha d. This is he case o spanning
ee p oblems and min-cos low p oblems, among o he s. In he case o he p-MP,
he single objec i e e sion is al eady NP-ha d. This ensu es ha he mul iobjec i e
o mula ion is no sol able in polynomial ime unless P=NP. In his con ex , when
ime and e iciency become a eal issue, di e en al e na i es can be used o ap-
p oxima e he Pa e o-op imal se . One o hem is he use o gene al-pu pose MOCO
heu is ics (?). Ano he possibili y is he design o “ad hoc” me hods based on one o
he ollowing s a egies: 1) compu ing suppo ed non-domina ed solu ions; and 2)
pe o ming pa ial enume a ions o he solu ions space. Ob iously, he second s a -
egy does no gua an ee he non-domina ed cha ac e o all he gene a ed solu ions
al hough he educ ion in compu a ion ime can be ema kable.
The aim o his sec ion is o p esen me hods o ob ain he Pa e o-op imal se o
he mul iobjec i e p-median p oblem (p-MP). In all cases, ou app oach o sol e he
mul ic i e ia p-MP akes ad an age o he p oblem’s s uc u e. The i s me hod is
exac and i de e mines he whole se o Pa e o-op imal solu ions based on new ools
bo owed om he heo y o sho a ional gene a ing unc ions. The second me hod
is an “ad hoc” app oxima e me hod ha gene a es suppo ed Pa e o loca ions.
1.4.1 Model and No a ion
Le I={1,...,M}and J={1,...,N} espec i ely deno e he se s o indices o
demand poin s and o plan s, and Q={1,...,Q}deno e he se o indices o
he conside ed c i e ia. Fo each c i e ion q∈Q, le (cq
i j)i∈I,j∈J∈QM×Nbe he
alloca ion cos s o demand poin s o plan s. The mul ic i e ia p-median loca ion
p oblem is:
36 Nickel, Pue o, Rod iguez-Ch´ıa
-Minimize M
∑
i=1
N
∑
j=1
c1
i jxi j,...,
M
∑
i=1
N
∑
j=1
cq
i jxi j!(1.6)
subjec o
N
∑
j=1
xi j =1,i∈I,(1.7)
xi j ≤yj,i∈I,j∈J,(1.8)
N
∑
j=1
yj=p,(1.9)
xi j ∈ {0,1},yj∈ {0,1},i∈I,j∈J.(1.10)
As i is usual, -min s ands o ec o minimum o he conside ed objec i e unc-
ions. He e a iable yj akes he alue 1 i plan jis open and 0 o he wise. The bina y
a iable xi j is 1 i he demand poin iis assigned o plan jand 0 o he wise. Con-
s ain s (??), oge he wi h in eg ali y condi ions on he x a iables, ensu e ha each
demand poin is assigned o exac ly one plan , while cons ain s (??) gua an ee ha
no demand poin is assigned o a non-open plan . Finally, cons ain (??) ensu es
ha exac ly pplan s a e opened.
Recall ha in he single c i e ion case he in eg ali y condi ions on he x a iables
need no be explici ly s a ed. The eason is ha when he xi j ep esen he p opo ion
o demand o clien isa is ied by plan j(i.e. 0 ≤xi j ≤1), he e exis s an op imal so-
lu ion wi h xi j =0,1, i∈I,j∈JThis p ope y is no necessa ily ue when mul iple
c i e ia a e conside ed because, in gene al, he e migh be undomina ed solu ions
wi h non-in ege alues and e en non-suppo ed undomina ed in ege solu ions.
1.4.2 De e mining he En i e Se o Pa e o-op imal Solu ions
In o de o cha ac e ize he se o Pa e o loca ions o he p-MP we shall use a ional
gene a ing unc ions. Sho a ional gene a ing unc ions we e used by ?as a ool o
de elop an algo i hm o coun ing he numbe o in ege poin s inside con ex poly-
opes, based on he p e ious geome ical pape by ?. The main idea is o encode
hose in ege poin s in a a ional unc ion o as many a iables as he dimension
o he space whe e he poly ope is de ined. Le P⊂IRn
+be a gi en con ex bounded
polyhed on. I s in ege poin s may be exp essed in a o mal sum (P,z) = ∑
α
z
α
wi h
α
= (
α
1,...,
α
n)∈P∩Zn, whe e z
α
=z
α
1
1···z
α
n
nBa inok’s goal was o ep esen
ha o mal sum o monomials in he mul i a ia e polynomial ing Z[z1,...,zn], as a
“sho ” sum o a ional unc ions wi h he same a iables. Ac ually, ?de eloped a
polynomial- ime algo i hm when he dimension, n, is ixed, o compu e hose unc-
ions. A clea example is he poly ope P= [0,T]⊂IR wi h T∈N: he long exp ession
o he gene a ing unc ion o he in ege poin s inside Pis (P,z) = ∑T
i=0zi, and i
is easy o see ha i s ep esen a ion as sum o a ional unc ions is he well known
o mula (1−zT+1)/(1−z).
1 Loca ion P oblems wi h Mul iple C i e ia 37
The abo e app oach, apa om coun ing la ice poin s, has been used o de elop
some algo i hms o sol e in ege p og amming p oblems exac ly. Speci ically, ?,?,
and ?p esen ed di e en me hods o sol e his amily o p oblems using Ba inok’s
a ional unc ion o he poly ope de ined by he easible se o he gi en p oblem.
Fi s o all, o he sake o eadabili y, we ecall some esul s on sho a ional
unc ions o poly opes ha shall be la e used in ou p esen a ion. Fo u he de ails
he in e es ed eade is e e ed o ??.
Le P={x∈IRn:Ax ≤b,x≥0}be a a ional poly ope in IRn. The main idea o
Ba inok’s Theo y was o encode he in ege poin s inside a a ional poly ope in a
“long” sum o monomials:
(P,z) = ∑
α
∈P∩Zn
z
α
,
whe e z
α
=z
α
1
1···z
α
n
n, and hen o e-encode, in polynomial- ime o ixed dimen-
sion, hese in ege poin s in a “sho ” sum o a ional unc ions in he o m
(P;z) = ∑
i∈I
ε
i
zui
n
∏
j=1
(1−z i j )
,
whe e Iis a polynomial-size indexing se ,
ε
i∈ {1,−1}, and ui, i j ∈Zn o all iand
j(Theo em 5.4 in ?).
I is well-known ha enume a ing he en i e se o Pa e o-op imal solu ions o
gene al mul iobjec i e in ege linea p oblems is #P-ha d e en in ixed dimension
(see, e.g., ?and ?). The e o e lis ing hese solu ions, in gene al, is hopeless. Ne -
e heless, one can y o ep esen hese se s in polynomial ime using a di e en
s a egy by simply encoding hei elemen s in an e icien way. This s a egy has
been ecen ly applied by ?. In ha pape , i is p o ed ha using sho gene a ing
unc ions o a ional poly opes, one can encode he whole se o Pa e o-op imal so-
lu ions o MOILP in polynomial ime, ixing only he dimension o he space o
a iables. As an applica ion o his esul we can s a e he ollowing heo em.
Theo em 1.10. Assume ha he numbe o acili ies M and plan s N is ixed. Then,
in polynomial ime, we can encode he en i e se o Pa e o-op imal solu ions o
(??)–(??)in a sho sum o a ional unc ions.
P oo . Apply Theo em 1 in ? o he poly ope o P oblem (??)–(??). ⊓⊔
The combina ion o Theo em ?? and Theo em 7 in ? esul s in he ollowing
heo em.
Theo em 1.11. Assume M and N a e cons an . The e exis s a polynomial-delay
polynomial-space p ocedu e o enume a e he en i e se o Pa e o-op imal solu ions
o (??)–(??).
This cons uc ion can be implemen ed o p oblems o small o medium size
dimension using he open sou ce so wa e ba inok, see ?.

38 Nickel, Pue o, Rod iguez-Ch´ıa
1.4.3 De e mining Suppo ed Pa e o-op imal Solu ions
In some si ua ions i su ices o gene a e he se o suppo ed Pa e o-op imal poin s.
I is well-known ha he se o suppo ed Pa e o-op imal solu ions o a p oblem can
be ob ained by sol ing he scala ized p oblem o all possible alues o he scala
weigh s in he s anda d Q-dimensional simplex
Λ
Q={
λ
∈RQ:∑Q
q=1
λ
q=1,
λ
q≥
0,∀q=1,...,Q}.
In o de o desc ibe how o ob ain hese solu ions in p oblem (??)–(??) we need
o in oduce some addi ional no a ion. We deno e by Bany easible basis o he
linea elaxa ion o P oblem (??)–(??); and by Nall he columns ha a e no in B.
Also, abusing no a ion, as usual in linea p og amming, we shall e e o he indices
de e mining he basis B(N) in he a iables and he objec i e unc ion by (x,y)B
((x,y)N) and cB(cN), espec i ely.
Fo any
λ
∈
Λ
Q, we shall deno e by c(
λ
) = (ci j(
λ
))i j, whe e ci j(
λ
) = ∑Q
q=1
λ
qcq
i j.
Fo each easible basis B, conside he subdi ision o he space
Λ
Qinduced by
he hype planes:
λ
qcq
BB−1N−
λ
qcq
N=0,q∈Q.
Nex , le
λ
Q
B∈
Λ
Qbe a pa ame e such ha i belongs o he ela i e in e io o
one o he elemen s in he abo e subdi ision and sa is ies cB(
λ
Q)B−1N−cN(
λ
Q)≤
0. This choice o
λ
Qensu es ha he p oblem:
Minimize
M
∑
i=1
N
∑
j=1
ci j(
λ
Q
B)xi j (1.11)
subjec o
N
∑
j=1
xi j =1,i∈I,(1.12)
xi j ≤yj,i∈I,j∈J,(1.13)
N
∑
j=1
yj=p,(1.14)
xi j ≥0,yj≥0,i∈I,j∈J.(1.15)
will iden i y suppo ed Pa e o-op imal solu ions o he linea elaxa ion o P oblem
(??)–(??). Howe e , hese Pa e o-op imal solu ions may esul in ac ional loca ion
a iables since P oblem (??)–(??) is a scala iza ion o he con inuous e sion o ou
o iginal mul iobjec i e loca ion p oblem. To a oid his incon enience we shall sol e
he bina y e sion o (??)–(??), namely
1 Loca ion P oblems wi h Mul iple C i e ia 39
Minimize
M
∑
i=1
N
∑
j=1
ci j(
λ
B)xi j (1.16)
subjec o
N
∑
j=1
xi j =1,i∈I,(1.17)
xi j ≤yj,i∈I,j∈J,(1.18)
N
∑
j=1
yj=p,(1.19)
xi j ∈ {0,1},yj∈ {0,1},i∈I,j∈J.(1.20)
Any op imal bina y solu ion o (??)-(??) gi es a suppo ed Pa e o-op imal solu ion
o ou o iginal mul iobjec i e loca ion p oblem. Repea ing he abo e p ocess o all
easible basis o P oblem (??)-(??) will esul in a se o suppo ed Pa e o-op imal
solu ions o he p oblem.
1.5 Conclusions
In his chap e we ha e p esen ed and analyzed some o he mos impo an mod-
els o mul ic i e ia loca ion p oblems conside ing h ee di e en decision spaces:
con inuous, ne wo ks and disc e e. This ma e ial p o ides a gene al o e iew o he
s a e-o - he-a o he ield as well as a numbe o e e ences ha can be used by he
in e es ed eade s o go o a u he analysis o he opic. Emphasis was pu on an
e icien (i possible) desc ip ion o he whole se o Pa e o loca ions.
Acknowledgemen s The au ho s we e pa ially suppo ed by p ojec s FQM-5849 (Jun a de An-
daluc´ıa FEDER), Fundaci´on S´eneca, g an numbe 08716/PI/08, he In e uni e si y A ac ion
Poles P og amme ini ia ed by he Belgian Science Policy O ice and MTM2010-19576-C02-01/02
(Minis y o Economy and Compe i i eness FEDER, Spain)