Con inuous Op imiza ion
A global op imiza ion p ocedu e o he loca ion o a median line
in he h ee-dimensional space
q
Ra ael Blanque o
a
, Emilio Ca izosa
a
, Ani a Schöbel
b
, Daniel Scholz
b,
⇑
a
Facul ad de Ma ema icas, Uni e sidad de Se illa, A da Reina Me cedes s/n, 41012 Se illa, Spain
b
Ins i u ü Nume ische und Angewand e Ma hema ik, Geo g-Augus -Uni e si ä Gö ingen, Lo zes aße 16-18, 37083 Gö ingen, Ge many
a icle in o
A icle his o y:
Recei ed 4 Augus 2010
Accep ed 18 May 2011
A ailable online 1 June 2011
Keywo ds:
Global op imiza ion
Geome ic b anch-and-bound me hods
Line loca ion
abs ac
A global op imiza ion p ocedu e is p oposed o find a line in he Euclidean h ee-dimensional space
which minimizes he sum o dis ances o a gi en fini e se o h ee-dimensional da a poin s.
Al hough we a e using simila echniques as o loca ion p oblems in wo dimensions, i is shown ha
he p oblem becomes much ha de o sol e. Howe e , a p oblem pa ame e iza ion as well as lowe
bounds a e sugges ed whe eby we succeeded in sol ing medium-size ins ances in a easonable amoun
o compu ing ime.
Ó2011 Else ie B.V. All igh s ese ed.
1. In oduc ion
In his wo k, we conside he median line p oblem in he Euclid-
ean h ee-dimensional space, i.e. we seek a line which minimizes
he sum o Euclidean dis ances o some gi en da a o demand
poin s in R
3
.
The median line p oblem in wo dimensions and in he con ex
o loca ion heo y was fi s analyzed by Wesolowsky (1975).
The ein, i was shown ha he e exis s an op imal line in e sec ing
wo da a poin s which leads o a polynomial- ime solu ion algo-
i hm. Many gene aliza ions such as gene al dis ance measu es,
line segmen s, and es ic ions we e s udied e.g. in Mo is and No -
back (1983, 1980), No back and Mo is (1980), and Ko neenko and
Ma ini (1993) as well as in Schöbel (1999) and e e ences he ein.
An o e iew abou loca ing lines as well as mo e gene al
dimensional acili ies on he plane can be ound in Díaz-Báñez
e al. (2004). Mo eo e , also he ecen wo k (Blanque o e al.,
2009) add esses he op imal loca ion o s uc u es in he plane
by means o d.c. op imiza ion ools. This pape uses a simila ap-
p oach o he median line loca ion p oblem in he Euclidean
h ee-dimensional space.
Al hough he Euclidean wo-dimensional median line p oblem
is well-s udied and exac polynomial ime algo i hms a e a ailable,
he h ee-dimensional p oblem becomes much ha de and only a
ew e e ences can be ound in he li e a u e. In B imbe g e al.
(2002), he au ho s discussed he p oblem o loca ing a e ical line
as well as e ical line segmen s o any ‘
p
no m. I was shown ha
hese p oblems can be essen ially educed o classical plana
Webe p oblems. The wo k was ex ended in B imbe g e al.
(2003). The ein, he h ee-dimensional median line p oblem was
s udied wi h some es ic ions, e.g. ha all da a poin s and/o he
line o be loca ed a e con ained in a gi en hype plane. Fu he -
mo e, some heu is ics o he gene al p oblem we e p esen ed,
bu wi hou any nume ical esul s. Summa izing, o he bes o
ou knowledge no algo i hm o he gene al h ee-dimensional
median line p oblem has been epo ed in he li e a u e.
The emainde o his pape is s uc u ed as ollows. In Sec ion
2, we discuss he p oblem o mula ion and some heo e ical esul s
a e gi en. Fu he mo e, we p esen a p oblem pa ame e iza ion
which is o undamen al impo ance o he ollowing sec ions.
Nex , geome ic b anch-and-bound solu ion me hods a e b iefly
summa ized in Sec ion 3. To apply his echnique o he median
line p oblem, lowe bounds a e de i ed in Sec ion 4. Some nume -
ical esul s can be ound in Sec ion 5whe e i is shown ha he
geome ic b anch-and-bound leads o solu ions o he median line
p oblem wi h da a se s o mode a e size in a easonable amoun o
compu ing ime. Finally, a discussion as well as some u he e-
sea ch ideas a e gi en in Sec ion 6.
2. P oblem o mula ion
A line in R
3
has he o m
¼ ðx;dÞ¼ xþ d : 2Rg;
whe e d2R
3
n 0gis he di ec ion o and x2R
3
. Mo eo e , we
will use he ollowing no a ion.
0377-2217/$ - see on ma e Ó2011 Else ie B.V. All igh s ese ed.
doi:10.1016/j.ejo .2011.05.030
q
Pa ially suppo ed by G an s FQM329, MTM2009-14039, P08-TIC-03518,
Spain.
⇑
Co esponding au ho . Tel.: +49 551 394513.
E-mail add esses: [email p o ec ed] (R. Blanque o), [email p o ec ed] (E. Ca i-
zosa), [email p o ec ed] (A. Schöbel), [email p o ec ed]
gen.de (D. Scholz).
Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20
Con en s lis s a ailable a ScienceDi ec
Eu opean Jou nal o Ope a ional Resea ch
jou nal homepage: www.else ie .com/loca e/ejo
No a ion 1. Fo any a2R
3
and x;d2R
3
wi h d–0 deno e by
d
a
ðx;dÞ:¼min
2R
kxþ d ak
2
he Euclidean dis ance om a o he line (x,d).
This no a ion leads o he ollowing analy ical exp ession o he
dis ance om a poin o a line.
Lemma 1. Le a 2R
3
and x;d2R
3
wi h d –0. Then
d
a
ðx;dÞ¼ xþd
T
ðaxÞ
d
T
d
!
da









2
¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
kxak
2
2

d
T
ðaxÞ

2
d
T
d
u
u
:ð1Þ
P oo . Define he scala unc ion
gð Þ:¼kxþ d ak
2
2
:
No e ha gis di e en iable, s ic ly con ex, and ha g
0
(
⁄
) = 0 o

¼d
T
ðaxÞ
d
T
d:
Hence,
⁄
minimizes gand we ob ain d
a
ðx;dÞ¼ ffiffiffiffiffiffiffiffiffiffiffi
gð

Þ
p. Fu he mo e,
easy calcula ions lead o
ððxaÞþ

dÞ
T
ððxaÞþ

dÞ¼kxak
2
2

d
T
ðaxÞ

2
d
T
d;
which p o es he claim. h
In he emainde o his pape ou goal is o loca e a line
= (x,d) in he h ee-dimensional Euclidean space which mini-
mizes he sum o dis ances be ween and a gi en se o da a
poin s.
To his end, le A¼ a
1
;...;a
n
gR
3
be a se o da a poin s.
Then we conside he median line p oblem
min
x;d2R
3
d–0
X
n
k¼1
d
a
k
ðx;dÞ¼min
x;d2R
3
d–0
X
n
k¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
kxa
k
k
2
2

d
T
ða
k
xÞ

2
d
T
d
u
u
:ð2Þ
2.1. P ope ies
Ob iously, he line (x,d) is no uniquely defined by he pai
(x,d). Indeed, (x,d)= (x+
m
d,d) o any
m
2R. Hence, we can as-
sume wi hou loss o gene ali y ha xis he in e sec ion o wi h
he hype plane
H
d
¼ y2R
3
:d
T
y¼0g:ð3Þ
Lemma 1 di ec ly leads o he ollowing co olla y.
Co olla y 2. Fo any a 2R
3
and x;d2R
3
wi h d –0 and d
T
x=0we
ha e
d
a
ðx;dÞ¼ xþd
T
a
d
T
d
!
da









2
¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
kxak
2
2

d
T
a

2
d
T
d
u
u
:ð4Þ
Nex , le us conside he median line p oblem wi h fixed di ec-
ion d2R
3
n 0gand he hype plane H
d
as defined in (3). We wan
o show ha he median line p oblem wi h fixed dis equi alen o
a plana Webe p oblem. This p oblem is o loca e a poin in he
plane minimizing he sum o dis ances o a gi en se o demand
poin s, see D ezne e al. (2001) o an o e iew. To his end, define
he mapping
p
d
:R
3
!H
d
wi h p
d
ðxÞ¼xd
T
x
d
T
dd
and no e ha p
d
(x) is he p ojec ion o xon o H
d
.
Lemma 3. Conside a fixed di ec ion d 2R
3
n 0g. Then
d
a
ðx;dÞ¼kp
d
ðxÞp
d
ðaÞk
2
o all x;a2R
3
.
P oo . One has
kp
d
ðxÞp
d
ðaÞk
2
¼xd
T
x
d
T
dd
!
ad
T
a
d
T
dd
!









2
¼xþd
T
ðaxÞ
d
T
d
!
da









2
¼d
a
ðx;dÞ;
due o Lemma 1, see Eq. (1).h
We ema k ha he same esul o he special case o a e ical
line, i.e. o d= (0,0,1), can also be ound in B imbe g e al. (2002).
Mo eo e , Lemma 3 di ec ly leads o he ollowing co olla y which
is a special case o he esul s in Ma ini (1994).
Co olla y 4. The ( h ee-dimensional) median line p oblem wi h fixed
di ec ion d 2R
3
n 0gis equi alen o a ( wo-dimensional) Webe
p oblem.
To be mo e p ecise, o any d2R
3
n 0gone has
min
x2R
3
X
n
k¼1
d
a
k
ðx;dÞ¼min
x2R
3
X
n
k¼1
kp
d
ðxÞp
d
ða
k
Þk
2
¼min
x2H
d
X
n
k¼1
kxp
d
ða
k
Þk
2
:ð5Þ
The ollowing basic p ope y will be impo an in o de o es ic
ou sea ch o a compac se .
Co olla y 5. The e exis s an op imal solu ion ðx

;d

Þ2R
6
o he
median line p oblem such ha he line = (x
⁄
,d
⁄
) in e sec s he
con ex hull o A.
P oo . Recall ha o any fixed d2R
3
n 0g he median line p ob-
lem is equi alen o a plana Webe p oblem, see Co olla y 4.
Mo eo e , i is well-known ha he e exis s an op imal solu ion
x
⁄
o he Webe p oblem which in e sec s he con ex hull o he
(p ojec ed) demand poin s
A
d
¼ p
d
ða
1
Þ;...;p
d
ða
n
Þg;
see e.g. D ezne e al. (2001), i.e. x
⁄
is he median o
p
d
(a
1
),...,p
d
(a
n
)2H
d
.
Hence, o any fixed d2R
3
n 0g he e exis s a x
⁄
2H
d
such ha
min
x2H
d
X
n
k¼1
kxp
d
ða
k
Þk
2
¼X
n
k¼1
kx

p
d
ða
k
Þk
2
¼X
n
k¼1
kpðx

Þp
d
ða
k
Þk
2
¼X
n
k¼1
d
a
k
ðx

;dÞ¼min
x2R
3
X
n
k¼1
d
a
k
ðx;dÞ;
see Eq. (5). To sum up, i exis s an op imal line =(x
⁄
,d) wi h fixed
di ec ion dwhich in e sec s he con ex hull o A. Since his is ue
o any d2R
3
n 0g, he s a emen is shown. h
2.2. P oblem pa ame e iza ion
The six-dimensional p oblem, i.e. finding x2R
3
and
d2R
3
n 0g, can be educed o a ou -dimensional p oblem in
R. Blanque o e al. / Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20 15
many ways. In he ollowing we p esen he pa ame e iza ion
which u ns ou o be he mos e ficien one o he solu ion algo-
i hm p oposed in he ollowing sec ions.
Fi s , we ha e ha (x,d)= (x,
s
d) o any
s
–0. Thus, we can
also assume wi hou loss o gene ali y ha kdk
1
= 1. Hence, we
can pa ame e ize any line = (x,d) by i s associa ed pai (x,d) wi h
kdk
1
= 1 and d
T
x= 0. Mo eo e , since (x,d)= (x,d), we can as-
sume ha
max
i¼1;2;3
jd
i
j¼max
i¼1;2;3
d
i
¼1:ð6Þ
Le d¼ðd
1
;d
2
;d
3
Þ2R
3
sa is ying (6) and le us fi s assume ha
d
3
= 1 is fixed. We only need o conside x¼ðx
1
;x
2
;x
3
Þ2R
3
such
ha d
T
x= 0 as discussed a he beginning o his sec ion. I we do
so, we easily ob ain
x
3
¼ðx
1
d
1
þx
2
d
2
Þ:
Wi h a
k
=(
a
k
,b
k
,
c
k
) o k=1,...,nand making use o Co olla y 2,we
ob ain he objec i e unc ion (in he case ha d
3
=1)
3
ðx
1
;x
2
;d
1
;d
2
Þ:¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
d
2
1
þd
2
2
þ1
qX
n
k¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
g
k
3
ðx
1
;x
2
;d
1
;d
2
Þ
q;
whe e
g
k
3
ðx
1
;x
2
;d
1
;d
2
Þ:¼ðx
1

a
k
Þ
2
þðx
2
b
k
Þ
2
þðx
1
d
1
þx
2
d
2
þ
c
k
Þ
2

ðd
2
1
þd
2
2
þ1Þðd
1
a
k
þd
2
b
k
þ
c
k
Þ
2
:
In he same way we can also fix d
1
= 1 and d
2
= 1 which yields
( enaming he ou emaining a iables always as x
1
,x
2
,d
1
, and d
2
)
1
ðx
1
;x
2
;d
1
;d
2
Þ:¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
d
2
1
þd
2
2
þ1
qX
n
k¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
g
k
1
ðx
1
;x
2
;d
1
;d
2
Þ
q;
2
ðx
1
;x
2
;d
1
;d
2
Þ:¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
d
2
1
þd
2
2
þ1
qX
n
k¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
g
k
2
ðx
1
;x
2
;d
1
;d
2
Þ
q;
whe e
g
k
1
ðx
1
;x
2
;d
1
;d
2
Þ:¼ðx
1
d
1
þx
2
d
2
þ
a
k
Þ
2
þðx
1
b
k
Þ
2
þðx
2

c
k
Þ
2

ðd
2
1
þd
2
2
þ1Þð
a
k
þd
1
b
k
þd
2
c
k
Þ
2
;
g
k
2
ðx
1
;x
2
;d
1
;d
2
Þ:¼ðx
1

a
k
Þ
2
þðx
1
d
1
þx
2
d
2
þb
k
Þ
2
þðx
2

c
k
Þ
2

ðd
2
1
þd
2
2
þ1Þðd
1
a
k
þb
k
þd
2
c
k
Þ
2
:
To sum up, he six-dimensional p oblem (2) is equi alen o he
ou -dimension p oblem
min
x
1
;x
2
;d
1
;d
2
2R
ðx
1
;x
2
;d
1
;d
2
Þð7Þ
wi h
ðx
1
;x
2
;d
1
;d
2
Þ:¼min
1
ðx
1
;x
2
;d
1
;d
2
Þ;
2
ðx
1
;x
2
;d
1
;d
2
Þ;
3
ðx
1
;x
2
;d
1
;d
2
Þg:
3. Geome ic b anch-and-bound algo i hm
To sol e he median line p oblem, we sugges a geome ic
b anch-and-bound algo i hm summa ized below which is a popu-
la solu ion echnique o non-con ex loca ion p oblems. One o
he fi s geome ic b anch-and-bound app oaches in he a ea o
acili y loca ion p oblems was sugges ed by Hansen e al. (1985),
he big squa e small squa e echnique o some acili y loca ion
p oblems on he plane. Plas ia (1992) gene alized his me hod
o he gene alized big squa e small squa e echnique. Using iangles
ins ead o squa es, D ezne and Suzuki (2004) p oposed he big i-
angle small iangle me hod. Since all hese echniques a e b anch-
and-bound solu ion me hods o p oblems wi h wo a iables,
Schöbel and Scholz (2010a) sugges ed he big cube small cube ech-
nique o acili y loca ion p oblems wi h mul iple a iables.
In gene al, assume an objec i e unc ion
:X!R;
whe e Xis a box wi h sides pa allel o he axes, i.e. a Ca esian p od-
uc o in e als. Mo eo e , deno e by c(Y) he cen e o any subbox
YXand le LB(Y) be a lowe bound o Y, i.e.
LBðYÞ6 ðzÞ o all z2Y:
Then, unde ce ain assump ions on and he bounding p ocedu e,
he ollowing algo i hm finds a global minimum o up o any abso-
lu e accu acy o
e
> 0, see e.g. Tuy (1998) o Schöbel and Scholz
(2010a).
(1) Calcula e a lowe bound LB(X) and se UB = (c(X)) and
X¼ Xg.
(2) Choose a box wi h he lowes lowe bound in X, spli i
in o scong uen smalle boxes Y
1
,...,Y
s
, dele e he
selec ed box om X, and add Y
1
,...,Y
s
o X. Calcula e
lowe bounds LB(Y
1
),...,LB(Y
s
) and upda e
UB ¼min UB; ðcðY
1
ÞÞ;...; ðcðY
s
ÞÞg:
Dele e all boxes Y om Xwi h LB(Y)+
e
PUB.
(3) When he e a e no boxes le , i.e. X¼;, he algo i hm
e mina es and UB is wi hin he absolu e accu acy o
e
om he global minimum. I he e a e boxes le , e u n o
s ep (2).
Be o e we can apply his geome ic b anch-and-bound ech-
nique o he median line p oblem, we ha e o discuss some mo e
de ails. No e ha we conside he ou -dimensional pa ame e iza-
ion as defined in Eq. (7).
Some lowe bounds can be ound in he ollowing sec ion.
Mo eo e , we ha e o ensu e ha he ini ial box Xcon ains a leas
one op imal solu ion.
Theo em 6. Wi hou loss o gene ali y assume ha A [1,1]
3
. Then
he ini ial box
X¼½ ffiffiffi
3
p;ffiffiffi
3
p½ ffiffiffi
3
p;ffiffiffi
3
p½1;1½1;1
con ains a leas one op imal solu ion o he median line p oblem using
he ou -dimensional pa ame e iza ion gi en in (7).
P oo . Le (x,d) be an op imal solu ion o he median line p oblem
wi h x=(x
1
,x
2
,x
3
) and d=(d
1
,d
2
,d
3
) such ha d
T
x= 0. Acco ding o
Co olla y 5 we can u he assume ha (x,d) in e sec s he con ex
hull o he demand poin s.
(1) Choose s2{1,2,3} such ha d
s
= max{jd
1
j,jd
2
j,jd
3
j} and
define
~
d¼ð
~
d
1
;~
d
2
;~
d
3
Þ¼1
d
s
d
1
;d
2
;d
3
ðÞ:
We ob ain ~
d
s
¼1 and j~
d
i
j61 o i= 1, 2, 3. Since (x,d) and
ðx;~
dÞ ep esen he same line, we ha e shown ha he e is
an op imal solu ion (x
1
,x
2
,d
1
,d
2
) o he median line p oblem
using he pa ame e iza ion (7) such ha d
1
,d
2
2[1,1].
16 R. Blanque o e al. / Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20
(2) Nex , assume ha x
1
R½ ffiffiffi
3
p;ffiffiffi
3
po x
2
R½ ffiffiffi
3
p;ffiffiffi
3
p. We know
ha d
T
x= 0. Hence, by Co olla y 2, he Euclidean dis ance
om 0 2R
3
o he line (x,d) is gi en by
d
0
ðx;dÞ¼kxk
2
¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
x
2
1
þx
2
2
þðx
1
d
1
þx
2
d
2
Þ
2
q>ffiffiffi
3
p:
Howe e , since kak
2
6ffiffiffi
3
p o all a2[1,1]
3
, he line (x,d)
does no in e sec he con ex hull o he demand poin s, a
con adic ion. h
4. Calcula ing lowe bounds
Be o e we p esen lowe bounds o he median line p oblem,
we ecall some gene al concep s o he calcula ion o lowe
bounds.
4.1. Na u al in e al ex ension
We assume ha he eade is amilia wi h in e al analysis, see
Hansen (1992) o Ra schek and Rokne (1988), which leads o sim-
ple bu in gene al no e y sha p lowe bounds. Applica ions o his
bounding p ocedu e o loca ion p oblems can be ound o exam-
ple in Fe nández e al. (2007), Fe nández e al. (2006), and Tó h
e al. (2009) whe e some compe i ion loca ion models we e sol ed.
Le g:R
m
!Rbe a unc ion such ha he na u al in e al
ex ension exis s. Fo any box Y¼X
1
X
m
R
m
we hen ob-
ain he lowe bound
LBðYÞ¼GðYÞ
L
;
whe e G(Y)=G(X
1
,...,X
m
) is he na u al in e al ex ension o g(x)
and he supe index
L
deno es he le endpoin o he in e al G(Y).
Fo a second, mo e sophis ica ed lowe bound, we will use he
gene al bounding ope a ion o o de wo as in oduced in Schöbel
and Scholz (2010b) which is summa ized in he ollowing
subsec ion.
4.2. Gene al bounding ope a ion
Assume a di e en iable unc ion g:R
m
!Rand calcula e some
lowe bounds on he pa ial de i a i es using he na u al in e al
ex ension, i.e. calcula e he ec o
LðYÞ:¼ðG
1
ðYÞ
L
;...;G
m
ðYÞ
L
Þ;
whe e G
k
(Y) is he na u al in e al ex ension o
g
k
ðxÞ:¼@g
@x
k
ðxÞ o k¼1;...;m:
Fu he mo e, le ‘¼‘ðYÞ¼ðX
L
1
;...;X
L
m
Þbe he le poin o
Y¼X
1
X
m
R
m
and define he linea unc ion
mðxÞ:¼gð‘ÞþLðYÞ
T
ðx‘Þ:
As shown in Schöbel and Scholz (2010b), we ob ain m(x)6g(x) o
all x2Y. Hence, we ge he lowe bound
LBðYÞ¼min
2VðYÞ
mð
Þ;
whe e V(Y) i he se o he 2
m
e ices o Y.
4.3. Lowe bounds o he median line p oblem
Recall ha o any subbox
Y¼X
1
X
2
D
1
D
2
R
4
;
we wan o find a lowe bound on he median line objec i e
unc ion
ðx
1
;x
2
;d
1
;d
2
Þ¼min
1
ðx
1
;x
2
;d
1
;d
2
Þ;
2
ðx
1
;x
2
;d
1
;d
2
Þ;
3
ðx
1
;x
2
;d
1
;d
2
Þ
g
;
whe e
i
ðx
1
;x
2
;d
1
;d
2
Þ¼ 1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
d
2
1
þd
2
2
þ1
qX
n
k¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
g
k
i
ðx
1
;x
2
;d
1
;d
2
Þ
q
o i= 1, 2, 3 as defined be o e.
One ob ains a fi s lowe bound o his p oblem using he na -
u al in e al ex ension, i.e.
LB
1
ðYÞ:¼FðYÞ
L
;ð8Þ
whe e F(Y)=F(X
1
,X
2
,D
1
,D
2
) is he na u al in e al ex ension o
(x
1
,x
2
,d
1
,d
2
).
Fo a second lowe bound, we make use o he gene al bounding
ope a ion as ollows. No e ha o i= 1, 2, 3 and k=1,...,n he
unc ions g
k
i
a e di e en iable, define he linea unc ion
m
k
i
ðx
1
;x
2
;d
1
;d
2
Þ:¼g
k
i
ð‘ÞþL
k
i
ðYÞ
T
ðx
1
;x
2
;d
1
;d
2
Þ‘ðÞ
de i ed om he gene al bounding ope a ion, and define
M
k
i
ðYÞ:¼min
2VðYÞ
m
k
i
ð
Þ:
Using hese defini ions, we ob ain he ollowing esul .
Lemma 7. Fo i = 1, 2, 3 and k = 1,...,n, he unc ions
h
k
i
ðx
1
;x
2
;d
1
;d
2
Þ:¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
m
k
i
ðx
1
;x
2
;d
1
;d
2
Þ
qi M
k
i
ðYÞP0
0i M
k
i
ðYÞ<0
8
<
:
a e conca e in Y and sa is y
h
k
i
ðx
1
;x
2
;d
1
;d
2
Þ6ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
g
k
i
ðx
1
;x
2
;d
1
;d
2
Þ
q
o all (x
1
,x
2
,d
1
,d
2
)2Y.
P oo . Ob iously, 0 is a conca e unc ion. Nex , i M
k
i
ðYÞP0 hen
m
k
i
ðx
1
;x
2
;d
1
;d
2
ÞP0 o all ðx
1
;x
2
;d
1
;d
2
Þ2Y;
since m
k
i
is linea . Mo eo e , since he scala unc ion uð Þ¼ ffiffi
pis
conca e and mono one inc easing o P0, we know ha also
h
k
i
ðx
1
;x
2
;d
1
;d
2
Þ¼uðm
k
i
ðx
1
;x
2
;d
1
;d
2
ÞÞ
is conca e. Finally, since
m
k
i
ðx
1
;x
2
;d
1
;d
2
Þ6g
k
i
ðx
1
;x
2
;d
1
;d
2
Þ o all ðx
1
;x
2
;d
1
;d
2
Þ2Y
and since uis mono one inc easing, we know ha
06h
k
i
ðx
1
;x
2
;d
1
;d
2
Þ6ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
g
k
i
ðx
1
;x
2
;d
1
;d
2
Þ
q;
which p o es he claim. h
Wi h he help o Lemma 7 we ob ain he ollowing second lowe
bound o he median line p oblem.
Theo em 8. Define he unc ions
h
i
ðx
1
;x
2
;d
1
;d
2
Þ:¼1
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
d
2
1
þd
2
2
þ1
qX
n
k¼1
h
k
i
ðx
1
;x
2
;d
1
;d
2
Þ
o i = 1, 2, 3 and le
hðx
1
;x
2
;d
1
;d
2
Þ:¼min h
1
ðx
1
;x
2
;d
1
;d
2
Þ;h
2
ðx
1
;x
2
;d
1
;d
2
Þ;
h
3
ðx
1
;x
2
;d
1
;d
2
Þg:
Then
R. Blanque o e al. / Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20 17
LB
2
ðYÞ:¼min
2VðYÞ
hð
Þð9Þ
is a lowe bound whe e V(Y) is he se o he 16 e ices o Y.
P oo . Fi s o all define qðx
1
;x
2
;d
1
;d
2
Þ:¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
d
2
1
þd
2
2
þ1
qand
s
i
ðx
1
;x
2
;d
1
;d
2
Þ:¼X
n
k¼1
h
k
i
ðx
1
;x
2
;d
1
;d
2
Þ
o i= 1, 2, 3. Then, qis a s ic ly posi i e and con ex unc ion and
he unc ions s
i
a e posi i e and conca e o i=1,2,3byLemma
7. Hence, we conclude ha
h
i
ðx
1
;x
2
;d
1
;d
2
Þ¼s
i
x
1
;x
2
;d
1
;d
2
ðÞ
qx
1
;x
2
;d
1
;d
2
ðÞ
a e quasiconca e unc ions o i= 1, 2, 3, see e.g. A iel e al. (1987).
Mo eo e , since he minimum o quasiconca e unc ions is quasi-
conca e again, his quasiconca e on Yand we he e o e ob ain
min
x2Y
hðxÞ¼min
2VðYÞ
hð
Þ:
Lemma 7 u he mo e s a es ha
hðx
1
;x
2
;d
1
;d
2
Þ6 ðx
1
;x
2
;d
1
;d
2
Þ o all ðx
1
;x
2
;d
1
;d
2
Þ2Y
and he heo em is shown. h
5. Nume ical esul s
In his sec ion we p esen some nume ical expe iences sol ing
he median line p oblem. To his end, we employed he geome ic
b anch-and-bound echnique as well as he lowe bounds p e-
sen ed in he p e ious sec ions.
We andomly gene a ed some demand poin s a
k
2{1.0,0.9,
...,0.9,1.0}
3
and all selec ed boxes we e spli in o s= 2 cong uen
small subboxes, i.e. all selec ed boxes we e bisec pe pendicula
o he di ec ion o he maximum wid h componen , see Sec ion 3.
Fu he mo e, in ou algo i hm we used h ee ini ial boxes as ol-
lows. We s a ed wi h X¼ X
1
;X
2
;X
3
gwhe e
X
i
¼½1:74;1:74½1:74;1:74½1;1½1;1;
see Theo em 6, and each box X
i
o i= 1, 2, 3 was only assigned o
he unc ion
i
.
Ou code was w i en in Fo an, compiled by In el Visual Fo -
an Compile P o essional 11.1.051, and an on a 2.67 GHz com-
pu e wi h 8 GB o memo y unde Windows 7. In he ollowing,
we p esen h ee di e en s udies.
5.1. Randomly inpu da a
Fo a ious alues o n, we sol ed 10 p oblem ins ances wi h
andomly gene a ed inpu da a as gi en abo e and
e
=10
6
.As
lowe bound, we used he maximum o he lowe bounds LB
1
(Y)
and LB
2
(Y) as sugges ed in Sec ion 4, i.e. we calcula ed
LB
3
ðYÞ:¼max LB
1
ðYÞ;LB
2
ðYÞg
o all subboxes YX.
Ou esul s a e illus a ed in Table 1. The ein, he minimum,
maximum, and a e age un imes as well as i e a ions h oughou
he b anch-and-bound algo i hm a e epo ed. Mo eo e , Fig. 1
shows he un imes o all sol ed p oblem ins ances.
As can be seen, all p oblem ins ances wi h up o n= 100 de-
mand poin s could be sol ed in less han a ew minu es o compu -
ing ime. Howe e , i should be men ioned ha he s anda d
de ia ion in he un imes is qui e high. Fo example, al hough nine
ou o en p oblem ins ances wi h n= 5 demand poin s we e sol ed
in less han 2 s, he e was one ins ance wi h a un ime o 14.91 s.
Simila obse a ions can also be ound o o he alues o n.
5.2. Compa ison o lowe bounds
In his subsec ion ou aim is o compa e he sugges ed lowe
bounds. To his end, we conside p oblem ins ances wi h n= 5 de-
mand poin s which we e sol ed wice. In he fi s un, we made
use o he lowe bound LB
1
, i.e. o he na u al in e al ex ension.
In he second un, we employed he lowe bound LB
2
.Table 2 p e-
sen s he un imes as well as he numbe o i e a ions h oughou
he algo i hm o 20 andomly gene a ed p oblem ins ances and
e
=10
1
.
Fu he mo e, we ema k ha we could no sol e any ins ances
o some smalle alues o
e
. Using e.g.
e
=10
2
, he lowe bound
LB
2
yields almos he same esul s as p esen ed in Table 2. Bu
no ins ance could be sol ed wi h
e
=10
2
and LB
1
since he lis o
boxes filled up wi h ou limi o 24,000,000 boxes wi hou
con e gence.
To sum up, ou esul s demons a e unequi ocally ha he na -
u al in e al ex ension alone does no yield sha p lowe bounds
such ha LB
1
should no o be used h oughou he algo i hm.
Hence, only he sugges ed second lowe bound makes i possible
o sol e he median line p oblem in an e ficien way.
5.3. Sol ing one pa icula p oblem ins ance
Finally, we p esen a pa icula p oblem ins ance wi h n=50
demand poin s. Using he da a gi en in Table 3 and
e
=10
6
again,
we ob ained a e 1,223,403 i e a ions and a un ime o 47.62 s he
op imal line
¼ ðx

;d

Þ¼
1:087929
1:106126
1:129687
0
B
@1
C
Aþ 0:980392
1:000000
0:153610
0
B
@1
C
A
wi h an objec i e alue o 36.893231, see Fig. 2.
6. Discussion
In his pape , we s udied he median line p oblem in h ee
dimensions. Some heo e ical esul s as well as a specific
Table 1
Nume ical esul s o he median line p oblem wi h andomly gene a ed inpu da a
and
e
=10
6
.
nRun ime (sec.) I e a ions
Min Max A e. Min Max A e.
5 0.39 14.91 2.21 96,784 3,274,910 486,212.6
10 1.54 56.05 20.75 185,437 6,649,657 2,498,832.4
15 2.25 32.35 12.25 185,568 2,589,609 1,009,505.1
20 3.18 61.31 22.46 198,271 3,788,279 1,415,919.5
25 3.67 28.80 15.47 184,857 1,442,695 777,971.8
30 5.73 30.73 15.60 248,481 1,302,031 663,204.2
35 11.95 83.57 35.28 438,693 3,009,059 1,277,984.5
40 9.31 49.75 30.14 298,652 1,578,879 977,898.0
45 16.33 124.96 34.71 465,717 3,741,455 1,018,784.2
50 13.23 78.89 34.72 346,308 2,045,602 899,292.3
55 15.83 80.65 37.14 376,639 1,874,345 873,764.9
60 20.14 83.57 41.23 440,004 1,869,197 910,500.1
65 19.61 80.39 46.97 393,906 1,627,484 943,908.1
70 17.67 81.90 44.56 330,381 1,535,738 833,716.2
75 22.99 67.27 43.91 405,202 1,185,531 768,827.1
80 37.02 111.06 68.90 603,655 1,872,381 1,133,722.3
85 19.39 92.04 54.66 297,282 1,411,662 836,951.5
90 33.32 161.76 75.43 498,420 2,342,423 1,107,803.5
95 39.70 154.27 78.53 549,138 2,162,391 1,096,360.5
100 25.68 192.65 76.62 336,837 2,481,556 999,837.8
18 R. Blanque o e al. / Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20

ou -dimensional p oblem pa ame e iza ion we e discussed and a
geome ic b anch-and-bound me hod as solu ion p ocedu e was
sugges ed. To be mo e p ecise, we de i ed some lowe bounds as
well as an ini ial box which con ains a leas one op imal solu ion.
In he nume ical esul s epo ed, i was shown ha we succeeded
in sol ing medium-size p oblem ins ances. Al hough we only
sol ed he unweigh ed median line p oblem, no e ha he p oblem
pa ame e iza ion as well as he p oposed lowe bounds a e s ill
alid o weigh ed demand poin s wi h non-nega i e weigh s.
Fu he mo e, we only conside ed he median line p oblem o
he Euclidean no m. I is u he esea ch o in es iga e some gen-
e al dis ance unc ions. The main ask he e is o de i e a closed o -
mula o o he dis ance unc ions simila o he o mula (1) o he
Euclidean case.
We ema k ha o he pa ame e iza ions o he median line
p oblem a e possible, e.g. sphe ical coo dina es as sugges ed in
Blanque o e al. (2009). We also implemen ed se e al o he lowe
bounds using e.g. echniques om d.c. p og amming, he cen e ed
in e al bounding ope a ion, o making use o bound p ocedu es
simila o hose ones gi en in Blanque o and Ca izosa (2009)
and Schöbel and Scholz (2010b). Howe e , all o he pa ame e iza-
ions as well as all o he lowe bounds we ied we e wo se com-
pa ed o he pa ame e iza ion as gi en in Sec ion 2and he lowe
bounds p esen ed in Sec ion 4.
Re e ences
A iel, M., Diewe , W.E., Schaible, S., Zang, I., 1987. Gene alized Conca i y, fi s ed.
Sp inge , New Yo k.
Blanque o, R., Ca izosa, E., 2009. Con inuous loca ion p oblems and big iangle
small iangle: Cons uc ing be e bounds. Jou nal o Global Op imiza ion 45,
389–402.
Blanque o, R., Ca izosa, E., Hansen, P., 2009. Loca ing objec s in he plane using
global op imiza ion echniques. Ma hema ics o Ope a ions Resea ch 34, 837–
858.
B imbe g, J., Juel, H., Schöbel, A., 2002. Linea acili y loca ion in h ee dimensions –
Models and solu ion me hods. Ope a ions Resea ch 50, 1050–1057.
B imbe g, J., Juel, H., Schöbel, A., 2003. P ope ies o h ee-dimensional median line
loca ion models. Annals o Ope a ions Resea ch 122, 71–85.
Díaz-Báñez, J.M., Mesa, J.A., Schöbel, A., 2004. Con inuous loca ion o dimensional
s uc u es. Eu opean Jou nal o Ope a ional Resea ch 152, 22–44.
D ezne , Z., Suzuki, A., 2004. The big iangle small iangle me hod o he solu ion
o noncon ex acili y loca ion p oblems. Ope a ions Resea ch 52, 128–135.
Fig. 1. Run imes o all p oblem ins ances o he median line p oblem wi h andomly gene a ed inpu da a and
e
=10
6
. The line ep esen s he median o hese alues.
Table 2
Nume ical esul s o he compa ison o he lowe bounds.
Run ime (sec.) I e a ions
Min Max A e. Min Max A e.
LB
1
2.79 64.37 17.19 1,025,080 20,538,265 5,827,158
LB
2
0.17 0.55 0.39 45,145 110,137 84,100
Table 3
Inpu da a A={a
1
,...,a
50
} o he pa icula p oblem ins ance discussed in Sec ion 5.3.
(1.6,0.2,0.0) (0.5,0.4,1.0) (0.3,1.8,1.8) (0.7,1.4,1.5) (1.5,1.8,0.7)
(0.8,2.0,1.2) (2.0,1.8,0.0) (1.3,0.6,0.5) (1.7,0.1,1.6) (0.4,1.4,0.2)
(1.4,1.2,0.1) (1.7,0.3,1.2) (0.7,2.0,1.1) (0.8,1.2,0.8) (1.6,1.7,0.8)
(0.1,1.5,0.2) (1.9,0.6,1.6) (1.9,0.9,1.0) (2.0,0.2,0.1) (2.0,0.6,1.2)
(0.0,0.4,0.8) (1.6,1.0,0.8) (0.7,1.0,2.0) (1.7,0.1,1.9) (0.3,1.5,1.1)
(1.0,1.9,1.4) (0.5,1.5,0.9) (0.4,0.7,1.1) (0.8,0.9,2.0) (1.9,0.2,1.6)
(0.8,1.3,1.4) (1.8,1.8,0.6) (1.5,1.1,1.6) (0.3,0.9,2.0) (0.8,0.1,2.0)
(0.8,1.1,0.3) (2.0,1.8,1.6) (1.6,1.5,0.8) (0.2,2.0,1.2) (1.2,1.6,0.7)
(1.8,1.4,1.8) (0.1,1.2,1.1) (1.1,0.3,0.6) (1.9,1.4,0.3) (0.0,0.9,0.1)
(0.7,1.5,1.1) (1.5,1.2,1.6) (1.6,0.0,1.3) (1.3,1.7,1.3) (0.5,0.0,0.3)
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Fig. 2. Op imal line o he pa icula p oblem ins ance discussed in Sec ion 5.3.
R. Blanque o e al. / Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20 19
D ezne , Z., Klam o h, K., Schöbel, A., Wesolowsky, G., 2001. The Webe p oblem. In:
D ezne , Z., Hamache , H.W. (Eds.), Loca ion Theo y – Applica ions and Theo y.
Sp inge , pp. 1–36.
Fe nández, J., Peleg ín, B., Plas ia, F., Tó h, B., 2006. Reconciling anchiso and
anchisee: A plana biobjec i e compe i i e loca ion and design model. Lec u e
No es in Economics and Ma hema ical Sys ems 563, 375–398.
Fe nández, J., Peleg ín, B., Plas ia, F., Tó h, B., 2007. Plana loca ion and design o a
new acili y wi h inne and ou e compe i ion: An in e al lexicog aphical-like
solu ion p ocedu e. Ne wo ks and Spa ial Economics 7, 19–44.
Hansen, E., 1992. Global Op imiza ion Using In e al Analysis, fi s ed. Ma cel
Dekke , New Yo k.
Hansen, P., Pee e s, D., Richa d, D., Thisse, J.F., 1985. The minisum and minimax
loca ion p oblems e isi ed. Ope a ions Resea ch 33, 1251–1265.
Ko neenko, N.M., Ma ini, H., 1993. Hype plane app oxima ion and ela ed opics.
In: Pach, J. (Ed.), New T ends in Disc e e and Compu a ional Geome y. Sp inge ,
New Yo k, pp. 135–162.
Ma ini, H., 1994. Minsum k-fla s o fini e poin se s in R
d
. S udies in Loca ional
Analysis 7, 123–129.
Mo is, J.G., No back, J.P., 1980. A simple app oach o linea acili y loca ion.
T anspo a ion Science 14, 1–8.
Mo is, J.G., No back, J.P., 1983. Linea acili y loca ion – Sol ing ex ensions o he
basic p oblem. Eu opean Jou nal o Ope a ional Resea ch 12, 90–94.
No back, J.P., Mo is, J.G., 1980. Fi ing hype planes by minimizing o hogonal
de ia ions. Ma hema ical P og amming 19, 102–105.
Plas ia, F., 1992. GBSSS: The gene alized big squa e small squa e me hod o plana
single- acili y loca ion. Eu opean Jou nal o Ope a ional Resea ch 62, 163–174.
Ra schek, H., Rokne, J., 1988. New Compu e Me hods o Global Op imiza ion, fi s
ed. Ellis Ho wood, Chiches e , England.
Schöbel, A., 1999. Loca ing Lines and Hype planes. Theo y and Algo i hms, fi s ed.
Kluwe Academic Publishe , Do d ech .
Schöbel, A., Scholz, D., 2010a. The big cube small cube solu ion me hod o
mul idimensional acili y loca ion p oblems. Compu e s and Ope a ions
Resea ch 37, 115–122.
Schöbel, A., Scholz, D., 2010b. The heo e ical and empi ical a e o con e gence o
geome ic b anch-and-bound me hods. Jou nal o Global Op imiza ion 48, 473–
495.
Tó h, B., Fe nández, J., Peleg ín, B., Plas ia, F., 2009. Sequen ial e sus simul aneous
app oach in he loca ion and design o wo new acili ies using plana Hu -like
models. Compu e s and Ope a ions Resea ch 36, 1393–1405.
Tuy, H., 1998. Con ex Analysis and Global Op imiza ion, fi s ed. Kluwe Academic
Publishe , Do d ech .
Wesolowsky, G.O., 1975. Loca ion o he median line o weigh ed poin s.
En i onmen and Planning A 7, 163–170.
20 R. Blanque o e al. / Eu opean Jou nal o Ope a ional Resea ch 215 (2011) 14–20