New results on minimax regret single facility ordered median location problems on networks

New Results on Minimax Regret Single Facility OrderedMedianLocationProblemson Networks Justo Puerto, Antonio M. Rodriguez-Chia, and Arie Tamir 1Facultad de Matem´aticas. Universidad de Sevilla 2Facultad de Ciencias. Universidad de C´adiz 3School of Mathematical Sciences. Tel Aviv University Abstract. We consider the single facility ordered median location problem with uncertainty in the parameters (weights) defining the objective function. We study two cases. In the first case the uncertain weights belong to a region with a finite number of extreme points, and in the second case they must also satisfy some order constraints and belong to some box, (convex case). To deal with the uncertainty we apply the minimax regret approach, providing strongly polynomial time algorithms to solve these problems. Keywords: Analysis of algorithms, networks, facility location. 1 Introduction The definition of an instance of an optimization problem requires the specification of the problem parameters, like resource limitations and coefficients of the objective function in a linear program, or edge capacities in network flow problems, which may be uncertain or imprecise. Uncertainty/imprecision can be structured through the concept of a scenario which corresponds to an assignment of plausible values to the model parameters. In general, the set of all admissible scenarios may depend on the properties of the underlying model, and on some possible known relationships between the model parameters. Nevertheless, we note that in most published studies it has been assumed that each parameter can independently take on values in some prespecified interval. This is the so called interval data approach. One of the most common approaches to deal with uncertain data is throughout the minimax absolute regret criterion. In this approach the goal is to minimize the worst case opportunity loss, defined as the difference between the achieved objective-function value and the optimal objective-function value under the realized scenario. We refer the reader to [2,3,5,8,12,17], where recent results on this subject for general optimization problems are described. Partially supported by grants n. MTM2004-0909, SAB2005-0095, P06-BFM-01366, MTM2007-67433-C02. L. Arge and E. Welzl (Eds.): ESA 2007, LNCS 4698, pp. 230–240, 2007. c Springer-Verlag Berlin Heidelberg 2007 New Results on Minimax Regret Single Facility OM Location Problems 231 We were motivated by facility location optimization problems where the exact nature of the optimality criteria was uncertain. Consider, for example, a location model in which the central administration subsidizes the transportation cost of the users only after the establishment of a server. Hence, at the moment when the facility has to be established, it is not yet clear what is the cost function that the central administration will apply for determining the magnitude of the subsidy. The administration may decide that the subsidy will be proportional to the distances traveled to the facility by all the customers with the exception of some unknown subset of outliers, e.g., those customers who are too close or too far to the server. The uncertainty is in the size or the exact definition of the set of outliers. In such a case, the criterion to be chosen ‘a priori’ for the location of the server might be taken as minimizing the regret of the decision among a certain family of criteria. The approach that we suggest to deal with this uncertainty is to limit ourselves to certain families of objective functions, and apply the approach of minimizing the maximum regret with respect to the selection of an objective within the prespecified. Our approach is different from the approach in the existing literature on minimax regret facility location models, where the objective function used is usually assumed to be known and certain ([4,5]). Specifically, in this paper, we will restrict ourselves to the family of ordered median functions (OMF) which has been studied extensively in the last decade in location theory, see [9,15]. This family unifies large variety of criteria used in location modeling. The OMF is a real function defined on Rnand characterized by a sequence of reals, λ=(λ1, ..., λn). For a given point z∈Rn,let¯z∈Rnbe the vector obtained from zby sorting its components in nondecreasing order. In the context of a single facility (server) location model with ndemand points, the OMF objective is applied as follows. Let xdenote the location of the server in the respective metric space, and let z(x) denote the vector of the nweighted distances of the demand points to the server at x. The value of the ordered median objective at xis then defined as the scalar product of λwith ¯z(x). As noted above, this function unifies and generalizes the classical and most common criteria, i.e., center and median, used in location modeling. (We get the median objective when λi=1,i=1, ..., n, and the center objective when λi=0,i=1, ..., n −1 and λn= 1.) Another important case is the k-centrum objective, where the goal is to minimize the sum of the k-largest weighted distances to the server. This case is characterized by λi=0,i=1, ..., n −k,andλi=1,i=n−k+1, ..., n. In addition to the above examples, the ordered median objective generalizes other popular criteria often used in facility location studies, e.g., centdian and (k1,k 2)-trimmed mean. In this paper, we solve a variety of single facility minimax regret ordered median problems on general networks finding best solutions on each edge. The reader can find further details in [16]. A summary of the results is given in Table 1. The paper is organized as follows. In Section 2, we present the single facility ordered median problem in general networks. Section 3 introduces the minimax 232 J.Puerto,A.M.Rodr´ıguez-Ch´ıa, and A. Tamir Table 1. Summary of results Objective function Complexity OMF with lower and upper bounds O(m2n4log n) (k1,k 2)-trimmed mean O(mn4) k-centrum O(mn2log2n) Convex OMF with lower and upper bounds O(m2n6log4n) Convex OMF with lower and upper bounds on trees O(n6log4n) regret ordered median problem and some results concerning the convexity of the objective function. In Section 4, we develop strongly polynomial algorithms for this type of problems when the feasible region of the λ-weights has a finite number of extreme points. Section 5 is devoted to analyze the convex case, which is defined by the property that the λ-weights are given in nondecreasing order; for this case a strongly polynomial algorithm is developed. 2Notation Let G=(V,E) be an undirected graph with node set V={v1, ..., vn}and edge set E,|E|=m.Eachedgee∈E, has a positive length le,andisassumedto be rectifiable. In particular, an edge eis identified as an interval of length le,so that we can refer to its interior points. Let A(G) denote the continuum set of points on the edges of G. Each subgraph of Gis also viewed as a subset of A(G), e.g., each edge e∈Eis a subset of A(G). We refer to an interior point on an edge by its distance along the edge to the nodes of the edge. The edge lengths induce a distance function don A(G) and thus A(G)isa metric space , see [18]. We consider a set of nonnegative weights {w1,...,w n}, called w-weights, where wi,i=1,...,n, is associated with node viand represents the intensity of the demand at this node. For any x∈A(G), let σ=σ(x) be a permutation of the set {1,...,n} satisfying wσ1d(vσ1,x)≤... ≤wσnd(vσn,x).For i=1,...,n,denoted(i)(x)= wσid(vσi,x). (d(i)(x)isani-th smallest element in the set {wjd(vj,x)}j). For a given vector λ=(λ1,...,λ n) with real components, called λ-weights, the ordered median function on A(G) is defined as fλ(x):= n  i=1 λiwσid(vσi,x). The single facility ordered median problem is to minimize fλ(x)overA(G), [15]. An ordered median function is called convex if 0 ≤λ1≤...≤λn. Apointx∈A(G)isanequilibrium point with respect to a pair of nodes vk, vl,k=l,ifwkd(vk,x)=wld(vl,x). A point x∈A(G)isabottleneck point if for some i=1,...,n,withwi>0, and e∈E,xis the unique maximum point of the (concave) function wid(vi,y)whenyis restricted to be in e.DenotebyEQ the set of all equilibrium and bottleneck points. This set can be a continuum set New Results on Minimax Regret Single Facility OM Location Problems 233 even in the case of a tree network when two nodes are equally weighted. Let EQ be the set consisting of the nodes of Gand all the boundary points of EQ.LetB be the subset consisting of the nodes of Gand the bottleneck points in EQ.For each e∈Edefine EQ(e)=EQ∩eand B(e)=B∩e.Notethat|EQ(e)|=O(n2) and |B(e)|=O(n). For each e∈Ethe points in EQ(e)(B(e)) induce a partition of the edge e into |EQ(e)|−1(|B(e)|−1) subedges. These subedges (subinterals) are viewed as consecutive subintervals of the rectified edge (interval) e. After computing the distances between all the nodes, the effort to compute and sort the points in EQ(e)(B(e)) for each e∈Eis O(n2+|EQ(e)|logn) (O(n+|B(e)|log n)). Note that for each subinterval in the partition induced by B(e), each function wid(vi,x) is linear. Moreover, for each open subinterval in the partition induced by EQ(e), no pair of functions in the collection {wid(vi,x)}i intersect. 3 The Minimax Regret Ordered Median Problem We assume that the vector λis unknown and can take on any value in some compact set Λ⊂Rn.Anyλ∈Λis called a scenario and represents a possible λ−weight instance. The minimax regret ordered median optimization problem is formally defined by: min x∈A(G)R(x):=max λ∈Λmax y∈A(G)fλ(x)−fλ(y). For any choice of the λ-weights, EQ contains at least one optimal solution for the respective ordered median problem, [15]. Thus, for a given x∈A(G) max y∈A(G)fλ(x)−fλ(y)=max y∈EQ fλ(x)−fλ(y)=fλ(x)−fλ(y∗(λ)), where y∗(λ)∈EQ is a minimizer of fλ(u)withu∈A(G). For each fixed y∈A(G) define Ry(x)=max λ∈Λfλ(x)−fλ(y).(1) By definition, for a given pair x, y ∈A(G) the function fλ(x)−fλ(y) is linear in λ. Therefore, Ry(x)= max λ∈ext(CH(Λ)) fλ(x)−fλ(y),where CH(Λ) is the convex hull of Λand ext(CH(Λ)) is the set of extreme points of CH(Λ). With this notation R(x)=max y∈EQ Ry(x).(2) Consider an edge e∈Eand let xe 1< ... < x e q(e), be the sequence of equilibrium points in EQ(e). (q(e)=|EQ(e)|.) Similarly, let ¯xe 1< ... < ¯xe b(e),be the sequence of bottleneck points in B(e). (b(e)=|B(e)|.) (See Figure 1). From the definition of equilibrium and bottleneck points and the above notation, we clearly have the following results. 234 J.Puerto,A.M.Rodr´ıguez-Ch´ıa, and A. Tamir Lemma 1. Consider a subedge [xe k,x e k+1],1≤k<q(e). For any λ∈Λ,the function fλ(x)is linear on the subedge. For any y∈EQ the function Ry(x)is continuous and convex on the subedge. Moreover, if the number of extreme points of CH(Λ)is finite Ry(x)is also piecewise linear on the subedge. Lemma 2. For any y∈EQ, the function fλ(y)is linear in λ.LetP⊆A(G) be a path such that fλ(x)is convex on Pfor any λ∈Λ. Then for any y∈EQ the function Ry(x)is convex on P. Moreover, the function R(x)is convex on P. To solve the minimax regret ordered median problem on a general network we will find the best local solution on each edge, i.e., we will solve msubproblems. We refer to each local subproblem as a restricted subproblem. d(1)(y) d(2)(y) d(3)(y) d(4)(y) d(1)(x) d(2)(x) d(3)(x) d(4)(x) d(1)(x) d(2)(x) d(3)(x) d(4)(x) d(1)(x) d(2)(x) d(3)(x) d(4)(x) x1x2x4 x3x5x6 ¯x1¯x3 ¯x2¯x4 z1 1z1 2z1 3z2 1z2 2z2 3z5 1z5 2 vivj || || || | ||||||| Fig. 1. Equilibrium and bottleneck points 4 Specific Models In this section, we focus on solving restricted subproblems for a variety of sets Λ, where the number of extreme points of the convex hull of Λis finite. As noted above, we concentrate on finding the best solution on each edge. Hence, we focus on optimizing R(x)onagivenedgee. We start with the case where Λ={(λ1,...,λ n):ai≤λi≤bi,i=1,...,n}. The reader may notice that this type of sets is the most common one used in the literature on regret analysis, see [12]. Here, we can strengthen the result in Lemma 1. Consider an edge e∈E. Lemma 3. For each 1≤k<q(e),andanyy∈EQ the function Ry(x)is the maximum of nlinear functions in [xe k,x e k+1]. New Results on Minimax Regret Single Facility OM Location Problems 235 Lemma 4. For each 1≤k<q(e), the function R(x)is the upper envelope of O(n|EQ|)linear functions for all x∈[xe k,x e k+1]. To solve the restricted problem on an edge e,wefirstdosomepreprocessingon this edge. Assume that we have already computed and sorted the equilibrium points in EQ(e). For each triplet y∈EQ,vi,v j∈V, we compute the at most two roots of the equation wid(x, vi)=wjd(y,vj)one. Define BP(e)tobethe set consisting of EQ(e) and all these roots. |BP(e)|=O(n2|EQ|). Moreover, for each ilet zk i(y) be the solution, if it exists, to the equation d(i)(x)=d(i)(y)(in the variable x), in the interval [xe k,x e k+1]. Each point zk i(y), is in BP(e).) Finally, we sort the elements in BP(e). The total preprocessing effort is O(n2|EQ|log n). Corollary 1. After spending O(n2|EQ|logn)time on preprocessing, for each 1≤k<q(e)the local minimizer of R(x)over the interval [xe k,x e k+1]can be computed in O(n|EQ|)time. The optimal solution to the minimax regret ordered median problem on the edge ecan be computed in O(n|EQ||EQ(e)|)time. The above result implies that for a general network the total time to solve the minimax regret ordered median problem over a box is O(m2n5). The latter bound can be further improved. Focusing on a given edge, we dynamically maintain [11] the upper envelope of O(|EQ|) linear functions which define the function R(x) over a refined subinterval defined by two consecutive elements in the set BP(e). Specifically, following the ordering of the elements in BP(e)weupdate this envelope. For a given element u∈BP(e), if u∈EQ(e) we may need to update O(|EQ|) linear functions since the ordering or some of the slopes of the functions {d(i)(x)}change. (For each y∈EQ we need to update at most two elements, per pair of indices j, k such that wjd(vj,u)=wkd(vk,u), in the sequence {d(i)(x)−d(i)(y)}i, or change the slope of a d(i)(x) function, per each jsuch that uis the maximum of the function wjd(vj,x)one.) If ucoincides with some element zk i(y) defined above, we need to update one function, per each y∈EQ and j, k such that wjd(vj,u)=d(i)(u)=d(i)(y)=wkd(vk,y), in the collection. Thus, the total number of insertions and deletions of functions to the collection of O(|EQ|) functions in the upper envelope is O(|EQ|n2). Using the data structure in Hershberger and Suri [11], each insertion and deletion can be performed in O(log n) time. Also, the minimum of R(x) over each subinterval connecting two consecutive elements of BP(e) can be computed in O(log n)time. Since there are O(n2)pointsinEQ(e)andO(n2|EQ|)pointsinBP(e)the overall effort to find the best solution on eis O(n2|EQ|log n). Theorem 1. The total time to solve the single facility minimax regret ordered median problem over a box on a general graph is O(m2n4logn). We note that in some important cases the number of extreme points of the convex hull of Λis relatively small. Hence, it may be advantageous to consider these extreme points explicitly. This is the case of the family of (k1,k 2)-trimmed mean functions [15], mentioned in the introduction. (Other cases are analyzed in the next section.) For this family Λ={(λ1,...,λ n):∃k1,k 2;k1+k2<n,λ 1=...= 236 J.Puerto,A.M.Rodr´ıguez-Ch´ıa, and A. Tamir λk1=λn−k2+1 =... =λn=0,λ k1+1 =...=λn−k2=1}.The extreme points of the convex hull of Λare the vectors of the form (0,...,0,1, ...,1,0,...,0). Therefore, in total there are O(n2)extremepoints. Consider an edge e∈E. We claim that for this family, on each interval defined by two consecutive points of EQ(e), the function R(x) can be described as an upper envelope of O(n2) linear functions. To facilitate the discussion, for each k=1,...,n,letSk(x)=n i=n−k+1 d(i)(x). For each 1 ≤s<q(e), and for each x∈[xe s,x e s+1], we have R(x)= max k1,k2;k1+k2<n n−k2  i=k1+1 d(i)(x)−k1,k2,where k1,k2=min y∈EQ n−k2  l=k1+1 d(l)(y). Hence, R(x)= max k1,k2;k1+k2<n Sn−k1(x)−Sk2(x)−min y∈EQ Sn−k1(y)−Sk2(y). Since R(x) is the upper envelope of O(n2) linear functions, its minimum on the interval [xe s,x e s+1] can be computed in O(n2) time using the algorithm in [14]. Hence, the solution to the minimax regret ordered median problem on a given edge efor this family of functions, can be obtained in O(n2|EQ(e)|)time. Theorem 2. The total time to solve the single facility minimax regret (k1,k 2)- trimmed mean problem on a general graph is O(mn4). 5 Minimax Regret Convex Ordered Median Problem In this section we analyze the minimax regret convex ordered median problem which includes several interesting and most common families of functions used in Location Theory. The first is the family of k-centrum functions where kcan vary between 1 and n(see [19]). We have Λ={(λ1,...,λ n):λ1≤... ≤λnand λi∈{0,1},i= 1, ..., n}.Thenextreme points of the convex hull of Λare the vectors of the form (0,...,0,1,...,1). Consider an edge e∈E. We claim that for this family, on each interval defined by two consecutive points of B(e), the function R(x) can be described as an upper envelope of nconvex functions. Indeed, for each 1 ≤s<b(e), and for each x∈[¯xe s,¯xe s+1], R(x)= max k=1,...,n n  i=n−k+1 d(i)(x)−ζk,where ζk=min y∈EQ n  l=n−k+1 d(l)(y). Hence, R(x)= max k=1,...,n Sk(x)−min y∈EQ Sk(y). Note that for each i=1,...,n, the function d(vi,x) is linear over the subinterval [¯xe s,¯xe s+1]. Therefore, for each k=1,...,n, the function n l=n−k+1 d(l)(x) is convex over the subinterval [¯xe s,¯xe s+1]. (See [15,19]). New Results on Minimax Regret Single Facility OM Location Problems 237 To evaluate R(x)foragivenx, it is sufficient to sort the elements {wid(x, vi)} in order to compute the terms {Sk(x)}k, and finally find maxk=1,...,n Sk(x)− miny∈EQ Sk(y). The minimum of R(x)ontheinterval[¯xe s,¯xe s+1]canthenbe computed in O(nlog2n) time by using the parametric approach of Megiddo [13] with the modification in Cole [7]. Hence, the solution to the minimax regret ordered median problem on a given edge efor this family of functions can be obtained in O(nlog2n|B(e)|) time. (We assume that in the preprocessing phase of the algorithm we have already calculated the terms {ζk}k. The total effort for this phase is O(mn2log n), see [15]). Theorem 3. The total time to solve the minimax regret k-centrum problem on a general graph is O(mn2log2n). The above analysis and algorithm are also applicable to the more general convex case defined by Λ={(λ1,...,λ n):λ1≤...≤λnand λi∈[a, b],i=1,...,n}, where aand bsatisfy 0 ≤a≤b,see[15].Inthiscasewehave Λ=CH({(λ1,...,λ n):λ1≤...≤λnand λi∈{a, b},i=1,...,n}). As another example of a convex family of ordered median functions with a small number of extreme points, consider the model corresponding to the αcentdian problem, see [15]. In this case, Λ={(λ1,...,λ n):∃0≤α≤1,λ 1= ...=λn−1=α, and λn=1}.We have ext(Λ)={(0,...,0,1),(1,...,1)}. 5.1 The Case of Interval Weights and Order Constraints In this section, we consider the minimax regret convex ordered median problem where the λ−weights are in the set, Λ≤={(λ1,...,λ n):λi∈[ai,b i]fori=1,...,n, and 0 ≤λ1≤...≤λn}. Without loss of generality, we may assume that both sequences {ai}and {bi} are nonnegative and nondecreasing. We note that the components of each extreme point of Λ≤are elements of the set AB ={a1,...,a n,b 1,...,b n}. Indeed, let λbe an extreme point and suppose without loss of generality that some λi∈ AB.Let1≤s≤i≤t≤nbe such that λs−1<λ s=λi=λt<λ t+1. For ε>0 sufficiently small, consider the vector λ(ε+) defined by setting λj(ε+) = λj+εfor s≤j≤tand λj(ε+) = λjotherwise. Similarly, consider the vector λ(ε−) defined by setting λj(ε−)=λj−εfor s≤j≤tand λj(ε−)=λjotherwise. The vector λis the midpoint of the interval connecting λ(ε+) and λ(ε−), contradicting the fact that λis an extreme point of Λ≤. Recall that for a given y∈EQ,Ry(x)=max λ∈Λ≤fλ(x)−fλ(y),see(1). Evaluating R(x)foragivenxamounts to computing the |EQ|values Ry(x)for all y∈EQ,see(2). We propose an algorithm to compute Ry(x) for any fixed y∈EQ.Consider an edge e∈E.Let¯xe kand ¯xe k+1 be two consecutive elements of B(e). fλ(x)isa 238 J.Puerto,A.M.Rodr´ıguez-Ch´ıa, and A. Tamir convex function on [¯xe k,¯xe k+1], see [15]. By Lemma 2, the functions {Ry(x)}y∈EQ, as well as R(x), are all piecewise linear and convex on [¯xe k,¯xe k+1]. For a fixed y∈EQ and x∈[¯xe k,¯xe k+1] the evaluation of Ry(x) can be done by solving the following linear program: Ry(x)=maxcT(x)λ−hT(y)λ s.t. λi−λi+1 ≤0,∀i=1,...,n−1, ai≤λi≤bi,∀i=1,...,n, where cT(x)=(d(1)(x),...,d (n)(x)) and hT(y)=(d(1)(y),...,d (n)(y)). (Recall that the optimal solution λ∗satisfies λ∗ i∈AB for i=1,...,n). Defining μi=λi−ai,βi=bi−ai,fori=1,...,n,αn=0,andαi=ai+1 −ai for i=1,...,n−1, the formulation above reduces to: n  i=1 ai(d(i)(x)−d(i)(y))+ max cT(x)μ−hT(y)μ s.t. μi−μi+1 ≤αi,∀i=1,...,n−1, μi≤βi,∀i=1,...,n, μi≥0,∀i=1,...,n. Setting u0=un= 0, the formulation of its corresponding dual problem is: n  i=1 ai(d(i)(x)−d(i)(y))+ min n  i=1 αiui+ n  i=1 βiti s.t. ui−ui−1+ti≥d(i)(x)−d(i)(y),∀i=1,...,n, ui,t i≥0,i=1,...,n. Notice that the matrix defining the above linear program is totally unimodular since it is a flow matrix augmented by the identity matrix. The above model corresponds to the following single commodity min-cost flow problem. (See Figure 2.) For each i=1,...,n−1, uiis the flow on the arc (i+1,i), and for each i=1,...,n,tiis the flow on left-arc (0,i). For i=1,...,n, the demand at node iis d(i)(x)−d(i)(y). Note that the demand can be of any sign. To account for the sign of the demand for i=1,...,n, define δ+ i(x)=max{0,d (i)(x)−d(i)(y)}and δ− i(x)=max{0,−(d(i)(x)−d(i)(y))}.The label attached to each edge in the graph has two coordinates. The left coordinate is the capacity upper bound on the flow, and the right one is the per unit cost of flow on the edge. The min-cost flow problem is to find the minimum cost of transporting n i=1 δ+ i(x) units from the source node 0 to the destination n+1. The fastest known strongly polynomial algorithm to solve a single commodity min-cost flow problem on a network with nnodes and medges is O(mS(n, m)logn), where S(n, m) is the time to solve the single source shortest path problem on a network with nnodes and medges, having nonnegative lengths. (See Ahuja et al. [1].) This algorithm has O(mlog n) scaling phases, where in each phase a shortest path problem is solved in S(n, m)time.Fora