On Exact Solvability of the Restricted Capacitated Facility Location Problem Edward Kh. Gimadi Anna Kurochkina Oxana Tsidulko Sobolev Institute Siberian State University Sobolev Institute of Mathematics Of Telecommunications of Mathematics 630090 Acad. Koptug av. 4; And Information Sciences 630090 Acad. Koptug av. 4; Novosibirsk State University 630102, Kirova 86, Novosibirsk State University 630090, Pirogova 1; Novosibirsk, Russia 630090, Pirogova 1; Novosibirsk, Russia a.potapova@ngs.ru Novosibirsk, Russia gimadi@math.nsc.ru tsidulko.ox@gmail.com Abstract Consider a graph G = (V, E). At the vertices of G there are consumers of some product and the possible places of its production. For each vertex i in V the demand volume b(i), the cost f (i) for opening a facility and the restriction a(i) on the facility’s capacity are given. For each edge e in E, there are given the cost of the transportation of the product unit ce and the maximum quantity qe of a product that can be transported along this edge. It is required to place the facilities in a way they satisfy all demand with minimal total cost of opening facilities and delivering the product to consumers. We propose a pseudo-polynomial time algorithm solving the problem with restrictions on facility and edge capacities on a tree graph, and dis- cuss a polynomial time algorithm solving the problem with restrictions on edge capacities in the case of a line graph given. 1 Introduction Facility location problems are the core problems in the operations research. As the name suggests, these problems are to determining the best location for one or more facilities in such a way that a certain set of demand points, or customers, are serviced in a satisfactory way. In order to evaluate a certain constellation of facilities and determining the best one, we require objectives or criteria and constraints on the system to be modeled. Numerous models have been proposed for a variety of different problems in the literature. We refer the reader to the survey paper [Klose & Drexl, 2005] and the book [Laporte et al., 2015] for a detailed overview of the results for different facility location problems and their applications. Perhaps the best known problem of this kind is the Uncapacitated Simple Plant Location Problem (USPLP) or the Uncapasitated Facility Location Problem (UFLP) [Krarup & Pruzan, 1983]. In this problem it is required to select the places to open the facilities from a finite feasible set of m elements so that the total cost of serving a Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org 209 finite number n of customers is minimized. One of the first surveys on the exact and approximation algorithms for solving such problems is [Cornuejols et al., 1990]. The UFLP is well-known to be NP-hard, since the Vertex Cover Problem reduces to it evidently. Nevertheless, in the case of a line and a tree graphs the problem is polynomially solvable with the following running-times: for the line graph – O(mn) [Beresnev et al., 1978], O(n2 ) [Cornuejols et al., 1990], for the tree graph – O(n3 ) [Trubin, 1976, Kolen, 1983], O(n2 ) [Kolen, 1983], O(mn) [Gimadi, 1983, Mirchandani & Francis, 1990, Billionet & Costa, 1994]. A more complicated problem is the Capacitated Facility Location Problem (CFLP) with restrictions on the facility capacities. More formally, in the CFLP each facility i has a capacity ai specifying the maximum amount of goods it can produce. There are two variants of this problem: CFLP with unsplittable demands (the demand of a client must be served by only one facility) or the single allocation CFLP [Laporte et al., 2015] and CFLP with splittable demands (the demand of a client can be split and assigned to multiple open facilities) or the multiple allocation CFLP[Laporte et al., 2015] . When the capacities of all the facilities are identical, the problem is known as the Uniform Capacitated Facility Location Problem (UCFLP). When the facility capacities are different, the problem is called the Non-Uniform Capacitated Facility Location problem or just the Capacitated Facility Location Problem. Let’s consider an even more hard case of the facility location problem the Restricted Capacitated Facility Location Problem (RCFLP) which has restrictions on the capacities of facilities and on the capacities of edges. Let G = (V, E) be a given graph, and let n = |V |. At each node of the graph there are consumers, and there is a set of nodes M ⊆ V where a facility might be placed. For each edge e ∈ E, the cost ce for the transportation of a unit of product along the edge is specified. The restrictions on the edge capacities mean that for each edge e ∈ E there is a maximum quantity qe of a product which can be transported along this edge. The problem is to minimize the sum of facility opening costs, plus the consumer allocation costs, having restrictions on the consumer’s demand, capacities of the facilities, and edge transportation capacities: ∑ ∑ ∑ p p fi yi + cij xij → minp (1) yi ,xij i∈V i∈M,j∈V p∈Pij subject to ∑ ∑ xpij ≤ ai yi , i ∈ M, |M | = m, (2) j∈V p∈Pij ∑ ∑ xpij = bj , j ∈ V, |V | = n, (3) i∈M p∈Pij ∑ xpij ≤ qe , e ∈ E, (4) i∈M,j∈V, p∈Pij : e∈p 0 ≤ xpij ≤ bj yi , i ∈ M , j ∈ V, (5) xpij ≥ 0, yi ∈ {0, 1}, (6) where bj is a size of demand at site j ∈ V ; ai is a capacity of the facility at site i ∈ M ; fi is a fixed cost of opening a facility at site i ∈ M ; Pij is a set of all paths from the facility at site i to customer at site j; ce is a∑transportation cost of a unit of product along the edge e; cpij = ce is a transportation cost of a unit of product along the path p from site i to site j; e∈p qe is capacity of the edge e ∈ E; yi are the variables of choosing whether to open a facility at site i or not, i ∈ V ; xpij is the quantity of the product transported from the facility at site i to the customer at site j along the path p ∈ Pij . Constrains (3) stand for each consumer’s demand is satisfied, capacity constrains (2) make sure that the capacity of the open facility cannot be exceeded, and transportation capacity constrains (4) guarantee that the 210 capacity of each edge e is not exceeded. Constrains (5) state that the allocation to the facility i is possible only if it is open. The problem (1), (3), (5) – (6) (that is, without taking into account the restrictions on the fa- cility and edge capacities) is called the Unbounded Facility Location Problem (UFLP or simply FLP) [Mirchandani & Francis, 1990]. The problem (1) – (3), (6) (that is, without taking into account the restictions on the edge capacities) is called the Capacitated Facility Location Problem (CFLP) [Mirchandani & Francis, 1990]. The problem (1), (3) – (6) (that is, without taking into account the restrictions on the facility capacities) is called the Restricted Facility Location Problem (RFLP) [Voznuk, 1999]. The RCFLP is known to be NP-hard on a graph of a general type. In [Ageev et al., 2009] the CFLP with uniform facility capacities on a line-graph is solved in time O(m4 n2 ). In [Voznuk, 1999] the RFLP on a tree graph (1), (3)–(6) was solved in O(n3 b2 ), where b = max bj . In this paper we consider a metric version of the j∈V RCFLP problem and show that it has a pseudo-polynomial algorithm if the input graph G is a tree. We also propose a polynomial dynamic programming algorithm for two statements of the RFLP on a line. 2 The RCFLP on a Tree Graph Assume that the graph G in the considered problem is a tree. Given that between any pair (i, j) of vertices of the tree there is a unique path Pij , the problem (1), (3)–(6) on an arbitrary tree graph can be stated as follows. ∑ ∑∑ fi yi + cij xij → min (7) yi ,xij i∈V i∈V j∈V subject to ∑ xij ≤ ai yi , i ∈ V, (8) j∈V ∑ xij = bj , j ∈ V, (9) i∈V ∑ ∑ xij ≤ qe , e ∈ E, (10) i∈V j|e∈Pij xij ≥ 0, yi ∈ {0, 1}, (11) ∑ where cij = ce for any i ∈ V , and j ∈ V . Here we consider a situation where a facility can be placed in e∈Pij any node of the graph G. If at site i ∈ V a facility cannot be placed, we set the cost fi of opening a facility to be equal to infinity. ∑ Statement 1 The RCFLP on a tree can be solved in O(nB 2 )-running time, where B = bj is the total j∈V demand. Let us describe the algorithm which consists of two preliminary stages and the dynamic programming. Preliminary Stage 1. First, we are going to reduce the problem with facility capacity (8) and edge capacity (10) constrains to a problem with only edge capacity constrains (10) by transferring the possible places for facilities to the new dummy vertices and transforming the facility’s productive capacity into the transportation capacity of the edge that connects the dummy and the initial vertices. For each vertex i ∈ G such that the cost of opening a facility at i is fi < ∞ we will add a dummy vertex i′ and an edge (i′ , i). We are going to move the places where a facility might be opened from all such vertices i to the corresponding i′ . Set the cost of opening a facility at i′ equal to fi′ = fi and then set fi = ∞. The demand at i′ is bi′ = 0, the cost of transportation of a unit of product along the edge (i′ , i) is c(i′ ,i) = 0. Finally, the transportation capacity of the edge (i′ , i) is equal to the facility capacity at i in the graph G : q(i′ ,i) = ai . Denote this new graph by G′ . The problem (7) on the graph G′ with constrains (9), (10), and (11) is equivalent to the problem on the graph G with constrains (8)–(11). While in the graph G a facility at site i cannot produce more 211 then ai units of product, in the graph G′ a facility at site i′ produces any number of product, but the edge (i′ , i) that connects the facility with the rest of the graph can transfer at most ai units. Note that G′ has at most 2n vertices. Preliminary Stage 2. Next we are going to reduce a problem on an arbitrary tree to a problem on a binary tree, which is an oriented rooted tree and each node has at most two children. Choose a vertex r that will be a root of the tree graph. Starting from the root for each vertex v that has more than 2 sons do the following. Let u1 , . . . , uk be the sons of v. Replace v by a path of k − 1 vertices v1 , . . . , vk−1 , and add edges (v1 , u1 ), (v2 , u2 ) . . . , (vk−1 , uk−1 ) and (vk−1 , uk ). Set the values of the demand bv1 = bv , bv2 = . . . = bvk−1 = 0, the costs of the facility opening fv1 = fv2 = . . . = fvk−1 = ∞, since at Stage 1 we made the vertices with finite cost of the facility opening to have only one neighbor. Set the cost of transportation for each edge ∑ in the path (v1 , . . . , vk−1 ) to be zero, and the edge capacities to be the highest possible, i.e. to be equal to v∈V bv . For each edge (vi , ui ), 1 ≤ i ≤ k − 1, set c(vi ,ui ) = c(v,ui ) and q(vi ,ui ) = q(v,ui ) . Lemma 1 [Voznuk, 1999]. The problem (7), (9)–(11) on an arbitrary tree graph reduces to a problem on a binary tree graph with at most twice the number of vertices. Stage 3. The dynamic programming. As a result of two previous stages we have a problem with no facility capacity constrains on a rooted binary tree graph G0 = (V0 , E0 ) with a root r = 0 and the number of vertices V0 ≤ 4n, where n is the number of vertices in the initial tree graph G. Consider a subtree Gi rooted at i. Let j be the parent of i and let z be the total amount of product transported along the edge e = (j, i). Denote by Fi (z) the optimum of the subproblem on a subtree Gi , assuming z units of product are transported along the edge e. Recall that in (6) yi ∈ {0, 1} are the variables of choosing whether or not to open a facility at site i. So each time in the Bellman equations we decide whether to open a facility at site i and satisfy the consumer’s demand in a subtree using it’s productivity, or not to open a facility and thus use the flow z to satisfy the demand∑at i and to pass the rest of the flow to the subtree. Note that we can assume qe ≤ B for all e ∈ E0 , where B = bi i∈V0 is the total demand, since B is the largest possible amount of product we would ever need to transfer along an edge in solving this problem. Set qee = min{qe , B}. For each z ∈ [−e qe , qee ] and i ∈ V0 : 1. If the vertex i is a leaf of the tree:   ce z, if bi ≤ z ≤ qee , Fi (z) = fi − ce z, if − qee ≤ z ≤ 0, (12)  ∞, otherwise 2. If the vertex i has one son k: { ( )} Fi (z) = ce |z| + min (1 − yi )Fk (z − bi ) + yi fi + ′ min Fk (z ′ ) = yi ∈{0,1} z ∈[0,e q(i,k) ] { } = ce |z| + min Fk (z − bi ); fi + ′ min Fk (z ′ ) . (13) z ∈[0,qi,k ] 3. If the vertex i has two sons k and ℓ: { Fi (z) = ce |z| + min (1 − yi ) ′ min {Fk (z ′ ) + Fk (z − bi − z ′ )} + yi ∈{0,1} z ∈[−e q(i,k) ,e q(i,k) ] ( )} ′ ′ + yi fi + ′ min Fk (z ) + ′ min Fℓ (z ) = z ∈[0,e q(i,k) ] z ∈[0,e q(i,ℓ) ] { } ce |z| + min ′ min {Fk (z ′ ) + Fk (z − bi − z ′ )}; fi + ′ min Fk (z ′ ) + ′ min Fℓ (z ′ ) . (14) |z |≤q(i,k) z ∈[0,q(i,k) ] z ∈[0,q(i,ℓ) ] ( ) Calculating Fi (z), z ∈ [−e qe , qee ], i ∈ V0 , takes O n(max qee )2 or O(n min{B 2 , qmax 2 } time, where qmax = max, e∈E0 e∈E0 and recovering of the solution (yi , xij ) takes O(n) time. Corollary 1. In the case of unit demands, the proposed algorithm runs in O(n3 ) time. 212 Corollary 2. In the case of line graph and a common statement of the problem with at most m possible sites for the facilities, the running-time of our algorithm is O(m min{B 2 , qmax 2 }). For vertices i ∈ / M , in which facility cannot be placed, in the dynamic programming procedure for the line graph there are no recurrence relations of the third type (14) and the relations (13) turn into Fi (z) = ce |z| + Fk (z − bi ). Note, that for the CFLP (with no edge capacity restrictions) on a line graph there is an algorithm from [Mirchandani et al., 1996] that runs in O(mB min{amax , B}), where m is the number of facilities that can be opened. In this case our algorithm will give almost the same time complexity O(m min{a2max , B 2 }), since amax transforms to qmax at the Preliminary Stage 1. 3 The RFLP on a Line Graph In this section we are going to discuss the metric RFLP (7), (9)–(11) on a line graph. Let the vertices of the line graph be numbered by 1, . . . , n in the order ∑ of its bypass. The cost cij of transportation of the unit of product from i to j is naturally defined as cij = e∈Pij ce . These transportation costs satisfy the conditions of central-connectivity: for each i1 , i2 , v ∈ V if ci1 v < ci2 v then ci1 j < ci2 j for all nodes j in the shortest path from i1 to v. Statement 2. [Gimadi, 1984] For the unbounded FLP on a graph with centrally-connected transportation costs, there exists an optimal solution such that for each opened facility the service area is a connected subgraph. Solutions of this type will be referred to as centrally-connected. Thus, for the RFLP on a line graph there exists an optimal solution, where the given line is broken into continuous segments and in each segment there is one open facility that fully serves the customers of this segment. For the RFLP we can also consider statements with single and multiple allocation conditions. In the case of single allocation each customer must be served by only one facility. Thus in the optimal centrally- connected solution the neighbor segments do not intersect. In the multiple allocation statement of the RFLP each consumer demand can be satisfied by several facilities. This implies that the neighbor segments in the optimal centrally-connected solution may have one common vertex, if the edge capacity restrictions do not allow to cover full demand of this vertex by the corresponding facility with the cheapest transportation cost. Both problems on a line can be solved in polynomial time by the dynamic programming in a similar way. 3.1 The Dynamic Programming Procedure Add the dummy vertices 0, n + 1 and the edges e′ = (0, 1), e” = (n, n + 1) to the line. Set the following numerical characteristics for the new elements of the line: qe′ = qe” = 0, ce′ = ce” = ∞, f0 = fn+1 = 0, b0 = bn+1 = 0. Single allocation case. Consider the single allocation RFLP on a line. Denote by g(i, j) the minimum cost of serving the segment [i, j], assuming that there is one open facility k in the segment that satisfies full demand of [i, j]. Consider a matrix (bcxy ), where bcxy is the total transportation cost necessary to satisfy the demand in all points of the path from x to y, if the product is supplied from the facility at site x.  ∑y  t=x+1 c(t,t+1) (bt+1 + bt+2 + . . . + by ), if x ≤ y, and (15), ∑ x b cxy = t=y c(t,t+1) (bt + bt+1 + · · · + bx−1 ), if y ≤ x, and (16),  ∞, otherwise, where we have the following system of restrictions due to the constraints on the capacity of edges. For x < y:    bx+1 + . . . + bx+t + . . . + by ≤ q(x,x+1) ,    ... bx+t + . . . + by ≤ q(x+t,x+t+1) , (15)     ...  by ≤ q(y−1,y) . And for y < x: 213    by + . . . + by+t + . . . + bx−1 ≤ q(y,y+1)    ... by+t + . . . + bx−1 ≤ q(y+t,y+t+1) (16)     ...  bx−1 ≤ q(x−1,x) . The matrix (bcij ) can be calculated in O(n3 ) time or in O(mn2 ) time, if we consider the statement of the RFLP with restriction m on the number of possible places for opening a facility. Then each g(i, j) can be found in O(j − i) time: g(i, j) = min {fk + b cki + b ckj }. i≤k≤j Now, according to the Statement 2 and the reasoning above, our problem reduces to the problem of finding an optimal segment decomposition of the line graph: ∑ s+1 g(ik , ik+1 ) → min, (17) {ik } k=1 s.t. 0 = i0 < i1 < . . . < is < is+1 = n + 1, s = 1, . . . , n. (18) The problem (17) – (18) can be solved by the following dynamic programming scheme G(0) = 0; G(j) = min (G(i) + g(i, j)), j = 1, . . . , n + 1. (19) 0≤i 2Ck − Ci ,  bk ∞, if Dj > Di . bxy , 1 ≤ x ≤ y ≤ n, takes O(n3 ). Calculating all Bt and Ct , 1 ≤ t ≤ n, takes O(n2 ) time, and calculating all C Note that first k − i inequalities in (21) do not depend on j, and the last j − k inequalities do not depend on i. So for fixed i and k verifying the first part of the system (21) takes O(k − i) time, similarly for fixed j and k verifying the second part of the system takes O(j − k) time. So it takes O(n3 ) time to verify all such systems. Finally, we can calculate hk (i, j) in O(1), and find h(i, j) in O(j) time: h(i, j) = min hk (i, j). i