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

Continuous Optimization A global optimization procedure for the location of a median line in the three-dimensional space q Rafael Blanquero a , Emilio Carrizosa a , Anita Schöbel b , Daniel Scholz b, ⇑ a Facultad de Matematicas, Universidad de Sevilla, Avda Reina Mercedes s/n, 41012 Sevilla, Spain b Institut für Numerische und Angewandte Mathematik, Georg-August-Universität Göttingen, Lotzestraße 16-18, 37083 Göttingen, Germany article info Article history: Received 4 August 2010 Accepted 18 May 2011 Available online 1 June 2011 Keywords: Global optimization Geometric branch-and-bound methods Line location abstract A global optimization procedure is proposed to find a line in the Euclidean three-dimensional space which minimizes the sum of distances to a given finite set of three-dimensional data points. Although we are using similar techniques as for location problems in two dimensions, it is shown that the problem becomes much harder to solve. However, a problem parameterization as well as lower bounds are suggested whereby we succeeded in solving medium-size instances in a reasonable amount of computing time. Ó2011 Elsevier B.V. All rights reserved. 1. Introduction In this work, we consider the median line problem in the Euclidean three-dimensional space, i.e. we seek a line which minimizes the sum of Euclidean distances to some given data or demand points in R 3 . The median line problem in two dimensions and in the context of location theory was first analyzed by Wesolowsky (1975). Therein, it was shown that there exists an optimal line intersecting two data points which leads to a polynomial-time solution algorithm. Many generalizations such as general distance measures, line segments, and restrictions were studied e.g. in Morris and Norback (1983, 1980), Norback and Morris (1980), and Korneenko and Martini (1993) as well as in Schöbel (1999) and references therein. An overview about locating lines as well as more general dimensional facilities on the plane can be found in Díaz-Báñez et al. (2004). Moreover, also the recent work (Blanquero et al., 2009) addresses the optimal location of structures in the plane by means of d.c. optimization tools. This paper uses a similar approach to the median line location problem in the Euclidean three-dimensional space. Although the Euclidean two-dimensional median line problem is well-studied and exact polynomial time algorithms are available, the three-dimensional problem becomes much harder and only a few references can be found in the literature. In Brimberg et al. (2002), the authors discussed the problem of locating a vertical line as well as vertical line segments for any ‘ p norm. It was shown that these problems can be essentially reduced to classical planar Weber problems. The work was extended in Brimberg et al. (2003). Therein, the three-dimensional median line problem was studied with some restrictions, e.g. that all data points and/or the line to be located are contained in a given hyperplane. Furthermore, some heuristics for the general problem were presented, but without any numerical results. Summarizing, to the best of our knowledge no algorithm for the general three-dimensional median line problem has been reported in the literature. The remainder of this paper is structured as follows. In Section 2, we discuss the problem formulation and some theoretical results are given. Furthermore, we present a problem parameterization which is of fundamental importance for the following sections. Next, geometric branch-and-bound solution methods are briefly summarized in Section 3. To apply this technique to the median line problem, lower bounds are derived in Section 4. Some numerical results can be found in Section 5where it is shown that the geometric branch-and-bound leads to solutions for the median line problem with data sets of moderate size in a reasonable amount of computing time. Finally, a discussion as well as some further research ideas are given in Section 6. 2. Problem formulation A line rin R 3 has the form r¼rðx;dÞ¼fxþtd :t2Rg; where d2R 3 nf0gis the direction of rand x2R 3 . Moreover, we will use the following notation. 0377-2217/$ - see front matter Ó2011 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2011.05.030 q Partially supported by Grants FQM329, MTM2009-14039, P08-TIC-03518, Spain. ⇑ Corresponding author. Tel.: +49 551 394513. E-mail addresses: [email protected] (R. Blanquero), [email protected] (E. Carrizosa), [email protected] (A. Schöbel), [email protected] gen.de (D. Scholz). European Journal of Operational Research 215 (2011) 14–20 Contents lists available at ScienceDirect European Journal of Operational Research journal homepage: www.elsevier.com/locate/ejor Notation 1. For any a2R 3 and x;d2R 3 with d–0 denote by d a ðx;dÞ:¼min t2R kxþtd ak 2 the Euclidean distance from ato the line r(x,d). This notation leads to the following analytical expression for the distance from a point to a line. Lemma 1. Let a 2R 3 and x;d2R 3 with 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 v u u t:ð1Þ Proof. Define the scalar function gðtÞ:¼kxþtd ak 2 2 : Note that gis differentiable, strictly convex, and that g 0 (t ⁄ ) = 0 for t  ¼d T ðaxÞ d T d: Hence, t ⁄ minimizes gand we obtain d a ðx;dÞ¼ ffiffiffiffiffiffiffiffiffiffiffi gðt  Þ p. Furthermore, easy calculations lead to ððxaÞþt  dÞ T ððxaÞþt  dÞ¼kxak 2 2  d T ðaxÞ  2 d T d; which proves the claim. h In the remainder of this paper our goal is to locate a line r=r(x,d) in the three-dimensional Euclidean space which minimizes the sum of distances between rand a given set of data points. To this end, let A¼fa 1 ;...;a n gR 3 be a set of data points. Then we consider the median line problem 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 v u u t:ð2Þ 2.1. Properties Obviously, the line r(x,d) is not uniquely defined by the pair (x,d). Indeed, r(x,d)=r(x+ m d,d) for any m 2R. Hence, we can assume without loss of generality that xis the intersection of rwith the hyperplane H d ¼fy2R 3 :d T y¼0g:ð3Þ Lemma 1 directly leads to the following corollary. Corollary 2. For any a 2R 3 and x;d2R 3 with d –0 and d T x=0we have 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 v u u t:ð4Þ Next, let us consider the median line problem with fixed direction d2R 3 nf0gand the hyperplane H d as defined in (3). We want to show that the median line problem with fixed dis equivalent to a planar Weber problem. This problem is to locate a point in the plane minimizing the sum of distances to a given set of demand points, see Drezner et al. (2001) for an overview. To this end, define the mapping p d :R 3 !H d with p d ðxÞ¼xd T x d T dd and note that p d (x) is the projection of xonto H d . Lemma 3. Consider a fixed direction d 2R 3 nf0g. Then d a ðx;dÞ¼kp d ðxÞp d ðaÞk 2 for all x;a2R 3 . Proof. 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 to Lemma 1, see Eq. (1).h We remark that the same result for the special case of a vertical line, i.e. for d= (0,0,1), can also be found in Brimberg et al. (2002). Moreover, Lemma 3 directly leads to the following corollary which is a special case of the results in Martini (1994). Corollary 4. The (three-dimensional) median line problem with fixed direction d 2R 3 nf0gis equivalent to a (two-dimensional) Weber problem. To be more precise, for any d2R 3 nf0gone 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 following basic property will be important in order to restrict our search to a compact set. Corollary 5. There exists an optimal solution ðx  ;d  Þ2R 6 to the median line problem such that the line r = r(x ⁄ ,d ⁄ ) intersects the convex hull of A. Proof. Recall that for any fixed d2R 3 nf0gthe median line problem is equivalent to a planar Weber problem, see Corollary 4. Moreover, it is well-known that there exists an optimal solution x ⁄ to the Weber problem which intersects the convex hull of the (projected) demand points A d ¼fp d ða 1 Þ;...;p d ða n Þg; see e.g. Drezner et al. (2001), i.e. x ⁄ is the median of p d (a 1 ),...,p d (a n )2H d . Hence, for any fixed d2R 3 nf0gthere exists a x ⁄ 2H d such that 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, it exists an optimal line r=(x ⁄ ,d) with fixed direction dwhich intersects the convex hull of A. Since this is true for any d2R 3 nf0g, the statement is shown. h 2.2. Problem parameterization The six-dimensional problem, i.e. finding x2R 3 and d2R 3 nf0g, can be reduced to a four-dimensional problem in R. Blanquero et al. / European Journal of Operational Research 215 (2011) 14–20 15 many ways. In the following we present the parameterization which turns out to be the most efficient one for the solution algorithm proposed in the following sections. First, we have that r(x,d)=r(x, s d) for any s –0. Thus, we can also assume without loss of generality that kdk 1 = 1. Hence, we can parameterize any line r=r(x,d) by its associated pair (x,d) with kdk 1 = 1 and d T x= 0. Moreover, since r(x,d)=r(x,d), we can assume that max i¼1;2;3 jd i j¼max i¼1;2;3 d i ¼1:ð6Þ Let d¼ðd 1 ;d 2 ;d 3 Þ2R 3 satisfying (6) and let us first assume that d 3 = 1 is fixed. We only need to consider x¼ðx 1 ;x 2 ;x 3 Þ2R 3 such that d T x= 0 as discussed at the beginning of this section. If we do so, we easily obtain x 3 ¼ðx 1 d 1 þx 2 d 2 Þ: With a k =( a k ,b k , c k ) for k=1,...,nand making use of Corollary 2,we obtain the objective function (in the case that d 3 =1) f 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; where 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 the same way we can also fix d 1 = 1 and d 2 = 1 which yields (renaming the four remaining variables always as x 1 ,x 2 ,d 1 , and d 2 ) f 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; f 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; where 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, the six-dimensional problem (2) is equivalent to the four-dimension problem min x 1 ;x 2 ;d 1 ;d 2 2R fðx 1 ;x 2 ;d 1 ;d 2 Þð7Þ with fðx 1 ;x 2 ;d 1 ;d 2 Þ:¼min f 1 ðx 1 ;x 2 ;d 1 ;d 2 Þ;f 2 ðx 1 ;x 2 ;d 1 ;d 2 Þ;f f 3 ðx 1 ;x 2 ;d 1 ;d 2 Þg: 3. Geometric branch-and-bound algorithm To solve the median line problem, we suggest a geometric branch-and-bound algorithm summarized below which is a popular solution technique for non-convex location problems. One of the first geometric branch-and-bound approaches in the area of facility location problems was suggested by Hansen et al. (1985), the big square small square technique for some facility location problems on the plane. Plastria (1992) generalized this method to the generalized big square small square technique. Using triangles instead of squares, Drezner and Suzuki (2004) proposed the big triangle small triangle method. Since all these techniques are branchand-bound solution methods for problems with two variables, Schöbel and Scholz (2010a) suggested the big cube small cube technique for facility location problems with multiple variables. In general, assume an objective function f:X!R; where Xis a box with sides parallel to the axes, i.e. a Cartesian product of intervals. Moreover, denote by c(Y) the center of any subbox YXand let LB(Y) be a lower bound for Y, i.e. LBðYÞ6fðzÞfor all z2Y: Then, under certain assumptions on fand the bounding procedure, the following algorithm finds a global minimum of fup to any absolute accuracy of e > 0, see e.g. Tuy (1998) or Schöbel and Scholz (2010a). (1) Calculate a lower bound LB(X) and set UB =f(c(X)) and X¼fXg. (2) Choose a box with the lowest lower bound in X, split it into scongruent smaller boxes Y 1 ,...,Y s , delete the selected box from X, and add Y 1 ,...,Y s to X. Calculate lower bounds LB(Y 1 ),...,LB(Y s ) and update UB ¼minfUB;fðcðY 1 ÞÞ;...;fðcðY s ÞÞg: Delete all boxes Yfrom Xwith LB(Y)+ e PUB. (3) When there are no boxes left, i.e. X¼;, the algorithm terminates and UB is within the absolute accuracy of e from the global minimum. If there are boxes left, return to step (2). Before we can apply this geometric branch-and-bound technique to the median line problem, we have to discuss some more details. Note that we consider the four-dimensional parameterization as defined in Eq. (7). Some lower bounds can be found in the following section. Moreover, we have to ensure that the initial box Xcontains at least one optimal solution. Theorem 6. Without loss of generality assume that A [1,1] 3 . Then the initial box X¼½ ffiffiffi 3 p;ffiffiffi 3 p½ ffiffiffi 3 p;ffiffiffi 3 p½1;1½1;1 contains at least one optimal solution to the median line problem using the four-dimensional parameterization given in (7). Proof. Let r(x,d) be an optimal solution to the median line problem with x=(x 1 ,x 2 ,x 3 ) and d=(d 1 ,d 2 ,d 3 ) such that d T x= 0. According to Corollary 5 we can further assume that r(x,d) intersects the convex hull of the demand points. (1) Choose s2{1,2,3} such that 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 obtain ~ d s ¼1 and j~ d i j61 for i= 1, 2, 3. Since r(x,d) and rðx;~ dÞrepresent the same line, we have shown that there is an optimal solution (x 1 ,x 2 ,d 1 ,d 2 ) to the median line problem using the parameterization (7) such that d 1 ,d 2 2[1,1]. 16 R. Blanquero et al. / European Journal of Operational Research 215 (2011) 14–20 (2) Next, assume that x 1 R½ ffiffiffi 3 p;ffiffiffi 3 por x 2 R½ ffiffiffi 3 p;ffiffiffi 3 p. We know that d T x= 0. Hence, by Corollary 2, the Euclidean distance from 0 2R 3 to the line r(x,d) is given 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: However, since kak 2 6ffiffiffi 3 pfor all a2[1,1] 3 , the line r(x,d) does not intersect the convex hull of the demand points, a contradiction. h 4. Calculating lower bounds Before we present lower bounds for the median line problem, we recall some general concepts for the calculation of lower bounds. 4.1. Natural interval extension We assume that the reader is familiar with interval analysis, see Hansen (1992) or Ratschek and Rokne (1988), which leads to simple but in general not very sharp lower bounds. Applications of this bounding procedure to location problems can be found for example in Fernández et al. (2007), Fernández et al. (2006), and Tóth et al. (2009) where some competition location models were solved. Let g:R m !Rbe a function such that the natural interval extension exists. For any box Y¼X 1 X m R m we then obtain the lower bound LBðYÞ¼GðYÞ L ; where G(Y)=G(X 1 ,...,X m ) is the natural interval extension of g(x) and the superindex L denotes the left endpoint of the interval G(Y). For a second, more sophisticated lower bound, we will use the general bounding operation of order two as introduced in Schöbel and Scholz (2010b) which is summarized in the following subsection. 4.2. General bounding operation Assume a differentiable function g:R m !Rand calculate some lower bounds on the partial derivatives using the natural interval extension, i.e. calculate the vector LðYÞ:¼ðG 1 ðYÞ L ;...;G m ðYÞ L Þ; where G k (Y) is the natural interval extension of g k ðxÞ:¼@g @x k ðxÞfor k¼1;...;m: Furthermore, let ‘¼‘ðYÞ¼ðX L 1 ;...;X L m Þbe the left point of Y¼X 1 X m R m and define the linear function mðxÞ:¼gð‘ÞþLðYÞ T ðx‘Þ: As shown in Schöbel and Scholz (2010b), we obtain m(x)6g(x) for all x2Y. Hence, we get the lower bound LBðYÞ¼min v2VðYÞ mð v Þ; where V(Y) it the set of the 2 m vertices of Y. 4.3. Lower bounds for the median line problem Recall that for any subbox Y¼X 1 X 2 D 1 D 2 R 4 ; we want to find a lower bound on the median line objective function fðx 1 ;x 2 ;d 1 ;d 2 Þ¼min f 1 ðx 1 ;x 2 ;d 1 ;d 2 Þ;f 2 ðx 1 ;x 2 ;d 1 ;d 2 Þ;f 3 ðx 1 ;x 2 ;d 1 ;d 2 Þ fg ; where f 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 for i= 1, 2, 3 as defined before. One obtains a first lower bound for this problem using the natural interval extension, i.e. LB 1 ðYÞ:¼FðYÞ L ;ð8Þ where F(Y)=F(X 1 ,X 2 ,D 1 ,D 2 ) is the natural interval extension of f(x 1 ,x 2 ,d 1 ,d 2 ). For a second lower bound, we make use of the general bounding operation as follows. Note that for i= 1, 2, 3 and k=1,...,nthe functions g k i are differentiable, define the linear function 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 Þ‘ðÞ derived from the general bounding operation, and define M k i ðYÞ:¼min v2VðYÞ m k i ð v Þ: Using these definitions, we obtain the following result. Lemma 7. For i = 1, 2, 3 and k = 1,...,n, the functions h k i ðx 1 ;x 2 ;d 1 ;d 2 Þ:¼ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi m k i ðx 1 ;x 2 ;d 1 ;d 2 Þ qif M k i ðYÞP0 0ifM k i ðYÞ<0 8 < : are concave in Y and satisfy h k i ðx 1 ;x 2 ;d 1 ;d 2 Þ6ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi g k i ðx 1 ;x 2 ;d 1 ;d 2 Þ q for all (x 1 ,x 2 ,d 1 ,d 2 )2Y. Proof. Obviously, 0 is a concave function. Next, if M k i ðYÞP0 then m k i ðx 1 ;x 2 ;d 1 ;d 2 ÞP0 for all ðx 1 ;x 2 ;d 1 ;d 2 Þ2Y; since m k i is linear. Moreover, since the scalar function uðtÞ¼ ffiffit pis concave and monotone increasing for tP0, we know that 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 concave. Finally, since m k i ðx 1 ;x 2 ;d 1 ;d 2 Þ6g k i ðx 1 ;x 2 ;d 1 ;d 2 Þfor all ðx 1 ;x 2 ;d 1 ;d 2 Þ2Y and since uis monotone increasing, we know that 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 proves the claim. h With the help of Lemma 7 we obtain the following second lower bound for the median line problem. Theorem 8. Define the functions 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 Þ for i = 1, 2, 3 and let 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 Þ;f h 3 ðx 1 ;x 2 ;d 1 ;d 2 Þg: Then R. Blanquero et al. / European Journal of Operational Research 215 (2011) 14–20 17 LB 2 ðYÞ:¼min v2VðYÞ hð v Þð9Þ is a lower bound where V(Y) is the set of the 16 vertices of Y. Proof. First of 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 Þ for i= 1, 2, 3. Then, qis a strictly positive and convex function and the functions s i are positive and concave for i=1,2,3byLemma 7. Hence, we conclude that 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 ðÞ are quasiconcave functions for i= 1, 2, 3, see e.g. Avriel et al. (1987). Moreover, since the minimum of quasiconcave functions is quasiconcave again, his quasiconcave on Yand we therefore obtain min x2Y hðxÞ¼min v2VðYÞ hð v Þ: Lemma 7 furthermore states that hðx 1 ;x 2 ;d 1 ;d 2 Þ6fðx 1 ;x 2 ;d 1 ;d 2 Þfor all ðx 1 ;x 2 ;d 1 ;d 2 Þ2Y and the theorem is shown. h 5. Numerical results In this section we present some numerical experiences solving the median line problem. To this end, we employed the geometric branch-and-bound technique as well as the lower bounds presented in the previous sections. We randomly generated some demand points a k 2{1.0,0.9, ...,0.9,1.0} 3 and all selected boxes were split into s= 2 congruent small subboxes, i.e. all selected boxes were bisect perpendicular to the direction of the maximum width component, see Section 3. Furthermore, in our algorithm we used three initial boxes as follows. We started with X¼fX 1 ;X 2 ;X 3 gwhere X i ¼½1:74;1:74½1:74;1:74½1;1½1;1; see Theorem 6, and each box X i for i= 1, 2, 3 was only assigned to the function f i . Our code was written in Fortran, compiled by Intel Visual Fortran Compiler Professional 11.1.051, and ran on a 2.67 GHz computer with 8 GB of memory under Windows 7. In the following, we present three different studies. 5.1. Randomly input data For various values of n, we solved 10 problem instances with randomly generated input data as given above and e =10 6 .As lower bound, we used the maximum of the lower bounds LB 1 (Y) and LB 2 (Y) as suggested in Section 4, i.e. we calculated LB 3 ðYÞ:¼maxfLB 1 ðYÞ;LB 2 ðYÞg for all subboxes YX. Our results are illustrated in Table 1. Therein, the minimum, maximum, and average run times as well as iterations throughout the branch-and-bound algorithm are reported. Moreover, Fig. 1 shows the run times for all solved problem instances. As can be seen, all problem instances with up to n= 100 demand points could be solved in less than a few minutes of computing time. However, it should be mentioned that the standard deviation in the run times is quite high. For example, although nine out of ten problem instances with n= 5 demand points were solved in less than 2 s, there was one instance with a run time of 14.91 s. Similar observations can also be found for other values of n. 5.2. Comparison of lower bounds In this subsection our aim is to compare the suggested lower bounds. To this end, we consider problem instances with n= 5 demand points which were solved twice. In the first run, we made use of the lower bound LB 1 , i.e. of the natural interval extension. In the second run, we employed the lower bound LB 2 .Table 2 presents the run times as well as the number of iterations throughout the algorithm for 20 randomly generated problem instances and e =10 1 . Furthermore, we remark that we could not solve any instances for some smaller values of e . Using e.g. e =10 2 , the lower bound LB 2 yields almost the same results as presented in Table 2. But no instance could be solved with e =10 2 and LB 1 since the list of boxes filled up with our limit of 24,000,000 boxes without convergence. To sum up, our results demonstrate unequivocally that the natural interval extension alone does not yield sharp lower bounds such that LB 1 should not to be used throughout the algorithm. Hence, only the suggested second lower bound makes it possible to solve the median line problem in an efficient way. 5.3. Solving one particular problem instance Finally, we present a particular problem instance with n=50 demand points. Using the data given in Table 3 and e =10 6 again, we obtained after 1,223,403 iterations and a run time of 47.62 s the optimal line r¼rðx  ;d  Þ¼ 1:087929 1:106126 1:129687 0 B @1 C Aþt0:980392 1:000000 0:153610 0 B @1 C A with an objective value of 36.893231, see Fig. 2. 6. Discussion In this paper, we studied the median line problem in three dimensions. Some theoretical results as well as a specific Table 1 Numerical results for the median line problem with randomly generated input data and e =10 6 . nRun time (sec.) Iterations Min Max Ave. Min Max Ave. 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. Blanquero et al. / European Journal of Operational Research 215 (2011) 14–20 four-dimensional problem parameterization were discussed and a geometric branch-and-bound method as solution procedure was suggested. To be more precise, we derived some lower bounds as well as an initial box which contains at least one optimal solution. In the numerical results reported, it was shown that we succeeded in solving medium-size problem instances. Although we only solved the unweighted median line problem, note that the problem parameterization as well as the proposed lower bounds are still valid for weighted demand points with non-negative weights. Furthermore, we only considered the median line problem for the Euclidean norm. It is further research to investigate some general distance functions. The main task here is to derive a closed formula for other distance functions similar to the formula (1) for the Euclidean case. We remark that other parameterizations of the median line problem are possible, e.g. spherical coordinates as suggested in Blanquero et al. (2009). We also implemented several other lower bounds using e.g. techniques from d.c. programming, the centered interval bounding operation, or making use of bound procedures similar to those ones given in Blanquero and Carrizosa (2009) and Schöbel and Scholz (2010b). However, all other parameterizations as well as all other lower bounds we tried were worse compared to the parameterization as given in Section 2and the lower bounds presented in Section 4. References Avriel, M., Diewert, W.E., Schaible, S., Zang, I., 1987. Generalized Concavity, first ed. Springer, New York. Blanquero, R., Carrizosa, E., 2009. Continuous location problems and big triangle small triangle: Constructing better bounds. Journal of Global Optimization 45, 389–402. Blanquero, R., Carrizosa, E., Hansen, P., 2009. Locating objects in the plane using global optimization techniques. Mathematics of Operations Research 34, 837– 858. Brimberg, J., Juel, H., Schöbel, A., 2002. Linear facility location in three dimensions – Models and solution methods. Operations Research 50, 1050–1057. Brimberg, J., Juel, H., Schöbel, A., 2003. Properties of three-dimensional median line location models. Annals of Operations Research 122, 71–85. Díaz-Báñez, J.M., Mesa, J.A., Schöbel, A., 2004. Continuous location of dimensional structures. European Journal of Operational Research 152, 22–44. Drezner, Z., Suzuki, A., 2004. The big triangle small triangle method for the solution of nonconvex facility location problems. Operations Research 52, 128–135. Fig. 1. Run times for all problem instances of the median line problem with randomly generated input data and e =10 6 . The line represents the median of these values. Table 2 Numerical results for the comparison of the lower bounds. Run time (sec.) Iterations Min Max Ave. Min Max Ave. 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 Input data A={a 1 ,...,a 50 } for the particular problem instance discussed in Section 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. Optimal line for the particular problem instance discussed in Section 5.3. R. Blanquero et al. / European Journal of Operational Research 215 (2011) 14–20 19 Drezner, Z., Klamroth, K., Schöbel, A., Wesolowsky, G., 2001. The Weber problem. In: Drezner, Z., Hamacher, H.W. (Eds.), Location Theory – Applications and Theory. Springer, pp. 1–36. Fernández, J., Pelegrín, B., Plastria, F., Tóth, B., 2006. Reconciling franchisor and franchisee: A planar biobjective competitive location and design model. Lecture Notes in Economics and Mathematical Systems 563, 375–398. Fernández, J., Pelegrín, B., Plastria, F., Tóth, B., 2007. Planar location and design of a new facility with inner and outer competition: An interval lexicographical-like solution procedure. Networks and Spatial Economics 7, 19–44. Hansen, E., 1992. Global Optimization Using Interval Analysis, first ed. Marcel Dekker, New York. Hansen, P., Peeters, D., Richard, D., Thisse, J.F., 1985. The minisum and minimax location problems revisited. Operations Research 33, 1251–1265. Korneenko, N.M., Martini, H., 1993. Hyperplane approximation and related topics. In: Pach, J. (Ed.), New Trends in Discrete and Computational Geometry. Springer, New York, pp. 135–162. Martini, H., 1994. Minsum k-flats of finite point sets in R d . Studies in Locational Analysis 7, 123–129. Morris, J.G., Norback, J.P., 1980. A simple approach to linear facility location. Transportation Science 14, 1–8. Morris, J.G., Norback, J.P., 1983. Linear facility location – Solving extensions of the basic problem. European Journal of Operational Research 12, 90–94. Norback, J.P., Morris, J.G., 1980. Fitting hyperplanes by minimizing orthogonal deviations. Mathematical Programming 19, 102–105. Plastria, F., 1992. GBSSS: The generalized big square small square method for planar single-facility location. European Journal of Operational Research 62, 163–174. Ratschek, H., Rokne, J., 1988. New Computer Methods for Global Optimization, first ed. Ellis Horwood, Chichester, England. Schöbel, A., 1999. Locating Lines and Hyperplanes. Theory and Algorithms, first ed. Kluwer Academic Publisher, Dordrecht. Schöbel, A., Scholz, D., 2010a. The big cube small cube solution method for multidimensional facility location problems. Computers and Operations Research 37, 115–122. Schöbel, A., Scholz, D., 2010b. The theoretical and empirical rate of convergence for geometric branch-and-bound methods. Journal of Global Optimization 48, 473– 495. Tóth, B., Fernández, J., Pelegrín, B., Plastria, F., 2009. Sequential versus simultaneous approach in the location and design of two new facilities using planar Huff-like models. Computers and Operations Research 36, 1393–1405. Tuy, H., 1998. Convex Analysis and Global Optimization, first ed. Kluwer Academic Publisher, Dordrecht. Wesolowsky, G.O., 1975. Location of the median line for weighted points. Environment and Planning A 7, 163–170. 20 R. Blanquero et al. / European Journal of Operational Research 215 (2011) 14–20