Location and shape of a rectangular facility in ℝn. Convexity properties. Convexity properties

Mathematical Programming 83 (1998) 277-290 Location and shape of a rectangular facility in R". Convexity properties 1 E. Carrizosa a, M. Mufioz-M~irquez b,*, J. Puerto a a Departamento de Estadlstica e Investigaci6n Operativa, Facultad de Matemdticas, c/Tarfia s/n, 41012-Sevilla, Spain b Departamento de Matemhticas, Escuela Politdcnica de Cddiz, c/Sacramento 82, llO02-Cddiz, Spain Received 12 October 1995; revised manuscript received 22 December 1997 Abstract In this paper we address a generalization of the Weber problem, in which we seek for the center and the shape of a rectangle (the facility) minimizing the average distance to a given set (the demand-set) which is not assumed to be finite. Some theoretical properties of the average distance are studied, and an expression for its gradient, involving solely expected distances to rectangles, is obtained. This enables the resolution of the problem by standard optimization techniques. 9 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. Keywords. Regional location; Facilities; Average distance 1. The model In the classical Weber Problem there exists a finite set of demand points that request some kind of service, and the problem is to locate a new point, called facility, minimizing the weighted sum of distances to the demand points, see [1]. If the demand set is not discrete or the facility has non-void area, then the problem is the Regional Weber Problem [2,3]. The problem with regional demand has been addressed in [4,5], while the regional server case is studied in [6]; other papers such as [7,8] are devoted to the evaluation of the expected distances to some regions. The problem of locating regional facilities has been previously addressed, but a new insight can be added to it if the shape of the facility is considered to be a decision variable. This case appears, for example, when one wants to locate an industrial park in a city or a chip in an integrated circuit. These examples show that, as a consequence of technological or infrastructure constraints, modelling the facility to be located as a region may be more accurate than modelling it as a single point. * Corresponding author. E-mail: [email protected]. a The research of the authors is partially supported by Spanish DGICYT grant PB93-0927, 0025-5610/98/$19.00 9 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. PHS00255 6 l 0(9 8)00006-9 278 E. Carrizosa et al. / Mathematical Programming 83 (1998) 277-290 The classical approach to solve the location of regional facilities consists of replacing each region by its centroid. Nevertheless, Aly [9] and Vaughan [8] have shown that this methodology is not satisfactory, since it strongly depends on the norm in use, (for example, usually good for the Euclidean norm and not so good for the ll norm), and the shape of the demand region. In addition what is even worse is that through this methodology there is no way to incorporate the shape of the region as a decision variable into the problem. In this paper we address the problem of determining the location and shape of an oriented rectangle, that is, a rectangle parallel to the axes of the coordinate system. The goal is to minimize the expected distance to the demand, distributed over a region A C ~" according to a probability measure p, when a lower bound k/> 0 is given for the volume of the rectangle. If the location of the server is uniformly distributed over a set S, then the expected distance between the demand and the server is given by where ~ is a gauge, see [10], that measures the distance between two points and p is the Lebesgue measure in ~". The use of gauges instead of norms as a distance measure is discussed in detail in [1 I]. To formulate the problem we need to introduce some notation. Given c E ~" and n E ~+ consider the rectangle RIc, = 1-I[c, - c, + i=1 Under the above assumptions, the problem can be formulated as min RA (c, ~) (c.~) n s.t. 2nH~i>/k , (1) i=l where RA(c, ~) is the average distance between A and the rectangle R(c, ~), i.e., 1 -RA(c,c~) -- 2" ~i=i c~i fa f(c,~) 7(x2. Properties of the average distance to a rectangle 2.1. General properties First of all, we must note that Problem 1 is well defined if and only if E(A) exists and is finite, see [12], E(A) being the mathematical expectation of the random vector A. Thus, hereafter, we impose this condition. E. Carrizosa et aLI Mathematical Programming 83 (1998) 277-290 279 For a given set S consider S(C, 00 = {(Cl .at_ 0{ISI,.. " ,C a ._~ O~nSn) ~ ~n: (SI,... ,Sn) ~ S}. In particular, if S is a sphere centered at the origin, then the family obtained, defines all the ellipsoids with symmetrical edges parallel to the coordinate axis, while taking S as the unit cube centered at the origin, gives all the rectangles with sides parallel to the coordinate axis. The following result holds. Theorem 1. Given a compact set S contain&g the origin in its interior, the function l fa / ,(x-a)dxdp(a) (c, ~) E R" x ~+ ~ ~(S(c, ~)) (~,~) is convex. Proofi The function 7 : x E R ~ ~ y(x) is a gauge, thus convex. For a, u fixed denote u. ~ = (ulal,...,u,a~). The function (c,a)~ c+ u. ~-a is linear. Thus (c,a) y(c + ua - a) is convex. Integrating, one concludes that (c,~) ~--~ -~(-(-~ / 7(c + u. ~ - a) du (2) is convex. Now 1/ _ 1 / 7(x_a)dx #(S) 7(c + u. a - a) du Iz(S) I-Ii~l c~, (c,~) _ 1 / y(x - a) dx ~(S(c, a))(c,~) and integrating again, one concludes that the function l / / 7(x-a)dxdp(a) (c, ~) ~ ~(S(c, ~)) (~,~) is convex. n 1 Taking S as Hi=l[- , 1] in Theorem 1, one has the following Theorem 2. The function -RA is convex. Corollary 3. Problem 1 is a convex program. Proof. An equivalent formulation of Problem 1 is min RA(c, a) (c,~) k 1~<0, a~>0, cE0~"; s.t. 2n I-[/=l 0~i 280 E. Carrizosa et al. I Mathematical Programming 83 (1998) 277-290 in this formulation both the objective function and the constraints are convex. Thus the problem is a convex program. Theorem 2 shows that Problem 1 is a convex program, thus solvable by a variety of algorithms available for convex programs in the literature, see [13], as soon as one can evaluate the average distance to a rectangle, see [12,7]. Remark 4. The convexity properties of the objective function enable the resolution of the problem also under convex constraints. An interesting special case of this problem is the following: the location of a rectangle with area at least of k units fully inside a convex set. This can be easily written as convex constraints. Since we have already shown that the objective function is convex this is also a convex program. 2.2. As a function of the shape The functional expression of the expected distance to a rectangle is only known for some particular gauges, see [14,7,8]. For this reason, the use of an explicit form of the objective function is a technique unavailable in a general approach to this problem. This fact makes the study of the problem a hard task. This section is devoted to develop further properties of the average distance function to a rectangle in order to ease the practical resolution of the problem. Observe that Rx(c, ~) equals R0(c - x, e), Where 0 is the null vector in N". If the demand A is a degenerate random vector (in short A is degenerated) at the point x, this means A is equal to x with probability 1, the expected distance reduces to 1 f 7(r - x) dr -Rx(c, ~) - 2" I-[in=l ~ii (c,~) -- 2 n l-I" 7(c + r - x) dr 1 .I.i= 1 (0,~) ~1 $tn / .... drl 2.1-I/=l c~i where r = (rl,..., r,). If A is not degenerate then the expected distance between R and A is given by -RA(c, ~) = .L" "Ra(c, a) dp(a). For simplicity in the expressions the following notation is introduced. Let V(c,a) = c+ [-a~,~l] x ... • {-a,} x ... x [- ~,,~,], L;(c, a) = c -4- [ - al, al] • • {0~,} x... • [ -- an, an] be the facets of R(c, c~), for i = 1,..., n. Or equivalently, t;(c,~) = R(c,a) n {x E An: x i = ciai} , L+(c, a) = R(c, c~) N {x E ~": xi = c~ + a,}. E. Carrizosa et al. I Mathematical Programming 83 (1998) 277-290 281 First of all, we study some properties of the objective function with respect to the variable e. Theorem 5. The function -R~ & non-decreasing and differentiable with respect to each cq, the partial derivatives being given by ai 2 ' Proof. The proof will be made for cq, for the remaining indices it runs analogously. First of all, the partial derivatives are calculated. By definition one has 1 f y(u - x) du -Rx(c, a) - 2" 1--[i~=, ai (c.=) _ 1 f --:t I Taking partial derivatives ~n f y(c + u-x)du .... dul. 0 Rx(c,~)= 0 1 0cq ~ 2"l-r" ... y(c+ u-x) du,...dul 11i=1 0~i and taking into account that 7 is continuous, one has O I (i~. y(c+u-x)du .... du2 1Rx(c, c~) - 2" uin=l o[ i (c,~) / ) 1 + 7(c + u - x) du..., du 2 n " 7(u - x) du = --0~ ( ~x(L~( (c' c@ + -dx(L{ (c' c@ - -~x(c' ~) Showing that Rx is non-decreasing with respect to c~ reduces to show that the partial derivatives, with respect to each cq, are non-negative. Indeed, for i = 2 .... , n, let ui be in [-c~, c~i], 2 be in [0, 1] and take 2' = 1 - 2. Consider the convex combination /~"(C + (--0~1, U2,... , Un) -- X) -~- ~.(C + (0~1, U2,... , b/n) -- X). Since 7 is convex then one has ?(,~'(c At-(-0~1, u2,... ,Un)- X) -~- 2(C -~-(~1, U2,... ,Un) -- X)) < 2'7(c + (-~, u:,..., u,) - x) + 27(r + (a~, u2,..., uo) - x) and integrating with respect to 2 282 E. Carrizosa et aLI Mathematical Programming 83 (1998) 277-290 1 f ~(~'(C'~-(--O~,,U2,...,Un)--X)-IV /*(C"t- (O~I,U2,...,Un) --x))d). 0 I ~ f (~.'7(C-t-(-Oq;u2,...,un)-x)-t-A,(C-t-(Oq,u2,...,un)-x))d).; 0 then making the change of variable u~ = -:q + 22el and integrating 1/ 2~t 7(c+ u-x) dul <~ 89 + (-cq,u2,...,u,) -x) +7(c + (~,,, u~,..., u,) - x)}. Now integrating with respect to the remaining ui and dividing by 2" 1-[i~__l ~i 9 1 ~tn / ...... an, 2~12" 1-I~i _~, -~. i=I ~< 2 2" r-I" ... "/(c .q!_ (--~l, U2, 9 9 9 , Un) -- X) du .... du2 1 li=l ~i -:~2 --:tn ~2 :ln ' / .... + e 2. 1-I;~l :~; or equivalently, 1 -Rx(c,~) <<. 4@l(-d.~(L[(c,~)) +3~(L~'(c, 7))), 2~1 that is to say b-~ RZ(c, ~) >/O. Thus R~ is non-decreasing with respect to el. The above theorem can be generalized to the case in which the demand is regional. Corollary 6. The function -RA & non-decreasing and differentiable with respect to each ~i, the partial derivatives being given by - ~, - ' + ~A (L; (c, ~)) _ -d~ (c, ~)) ~-~iRA(c,~) =I ( dA(L[(c'~)) 2 Proofi The function Ra is non-decreasing, since the integral operator is monotone and Rx is non-decreasing with respect to ~. s Carrizosa et aLI Mathematical Programming 83 (1998) 277-290 283 Theorem 1, Section 2, of [15] allows to exchange the integral and differential operators, since Rx is convex, so that O~i-RA(c,c~)= fAO@i-R~(c,c~)dp(a) = 1 fA { d~(L~-(c, c~))+2 -da(LT(c' c~))_ da(c, c~)) dp(a) and the equality is proved. As a consequence, one has the following Corollary 7. The optimal solution for Problem 1 for k = 0 & some rectangle degenerate to a point. Thus Problem 1 with k = 0 becomes the standard Regional Weber Problem [2,12]. This result has been previously shown in [12,16] by a different procedure. Hereafter, we suppose that k is strictly positive. 2.3. As a function of the location Now let us study the differentiability with respect to the location variable c. Theorem 8. The function Rx is differentiable with respect to each ci, the partial derivatives being given by ~) 2~g Proof. By definition Rx(c, c~) - 2, 1-j, ... 7(c+u-x)du .... dul 1 Ii=l (~i --51 --~n Cl "b~tl --X l Cn 4-Otn --Xn 1 / / -- . . ... 7(u) du .... dul. 2 1-Ii=~ ~ c I --~t 1 --X I r --x n The proof is analogous for each index. Then we take i = 1; differentiation in the previous expression yields 284 E. Carrizosa et al. / Mathematical Programming 83 (1998) 277-290 O-~lR--~(c,~) (+v ) 0 1 / .. 7(u) dun dul -- n .... OCl 2n I-L=l ~i Cl -~1 -xI Cn -r -Xn 12 n 1-'[7=10~i (fT(u)du,...duz-/7(u)du,...du2) \ L? (c,~t)-x Ll(c,rt)-x = -dx(L+(c, ~)) - ~(L;(c, ~)) 2~ Again, in the case of regional demand a similar result is obtained. Corollary 9. The function -RA is differentiable with respect to each ci, the partial derivatives being given by ~ rc,~,A, ~) = G(L?(c, ~)) - G(L;(c, ~)) OC i 2ai Proof. Using the equality RA (c, c~) = f Ra(c, ~) dp(a) and taking derivatives, one has 0 -RA(c,~)= 0 fNa(C,~)dp(a), o%5i since Rx is convex, the above-mentioned theorem of [15], enables us to exchange the integral and differential operators = f o~-Ra(C,~)dp(a) A f -d~(L+(c, ~) ) - -d~(LT (c, a) ) = ~idp(a) A _ ~ (U(c, ~)) - ~(L;(r ~)) 2~i which proves the corollary. Remark 10. The condition of optimality with respect to c is, from the above theorem, RA(c,o 0=0 i=l,...,n. This expression admits a remarkable interpretation: in the optimal rectangle the expected distance to every pair of opposite facets must be equal. The convexity property enables us to extend the previous theorems. E. Carrizosa et al. / Mathematical Programming 83 (1998) 277-290 Theorem 11. The functions Rx and-RA are differentiable. 285 Proof. By Theorem 25.2 of [17] a convex function is differentiable if its partial derivatives exist and are finite. The partial derivatives of RA are given by Corollaries 6 and 9, and are finite as soon as E(A) exists and is finite. Since this condition was taken as assumption, the result holds. 2.4. Uniqueness properties Some conditions must be imposed in order to guarantee the uniqueness of the solution. Following [18], we recall that 7 is said to be a strict gauge or round gauge if its unit ball does not contain segments not reduced to a point. Recall that a segment is called degenerate if it reduces to a point. Theorem 12. If 7 & a strict gauge, then the function -RA is increasing in ~. Proof. The proof is analogous to Theorem 5 and Corollary 6. One only needs to prove that Rx(c, e) is increasing in e and then take integral. Given e there exist noncollinear x, (-el, u2,..., u,) and (el, u2,..-., Un). Then V2 C (0, 1), 4'= 1-4: - x) + 2((e,,.2 .... ,.n) - x)) < 2t~((--el,b/2,... ,un) --X) "~- 2'~((el,U2,... ,un) --X). Thus the first inequality of the proof of Theorem 5 is strict. Since 7 is continuous the inequality holds strictly in a neighbourhood of such point. This enables us to assure that the strict inequality is kept after integration. Consequently ~Rx(c, e) > 0. Thus Rx(c, e) and RA(c, e) are increasing with respect to e. Theorem 13. If3' is a strict gauge, then the function RA is strictly convex in the interior of its domain. Proof. Given x and e, there exists u such that x and (ulel,..., u,e,) are not coUinear with 0, then (x, u) H 7((ulex,..., u,e,) - x) is strictly convex. By continuity, there is also a neighbourhood of u where the non-collinearity holds. This guarantees the strict inequality of 7 regarding any strictly convex combination in a set of non-zero Lebesgue measure and this implies the strict convexity of the expected distance function. Theorems 12 and 13, together with the property of inf-compactness, enable us to obtain sufficient conditions for the uniqueness of the solutions.