A global optimization procedure for the location of a median line in the three-dimensional space

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