LP-based Approximation Algorithms for Capacitated Facility Location 3 Retsef Levi 1 , David B. Shmoys 2,and Chaitanya Swamy 1 School of ORIE, Cornell University, Ithaca, NY 14853. rl227@cornell.edu 2 School of ORIE and Department of Computer Science, Cornell University Ithaca, NY 14853. shmoys@cs.cornell.edu 3 Department of Computer Science, Cornell University, Ithaca, NY 14853. swamy@cs.cornell.edu 1 Introduction There has been a great deal of recent work on approximation algorithms for facility location problems [9]. We consider the capacitated facility location problem with hard capacities. We are given a set of facilities, F, and a set of clients D in a common metric space. Each facility i has a facility opening cost fi and capacity ui that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set F and assign each client to an open facility so that at most ui clients are assigned to any open facility i.The cost of assigning client j to facility i is given by their distance cij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The recent work on facility location problems has come in two varieties: LP- based algorithms, and local search-based algorithms. For the problem described above, no constant approximation algorithm based on LP is known, and in fact, no LP relaxation is known for which the ratio between the optimal integer and fractional values has been bounded by a constant. Surprisingly, constant performance guarantees can still be proved based on local search, but these have the disadvantage that on an instance by instance basis, one never knows anything stronger than the guarantee itself (without resorting to solving an LP relaxation anyway). We present an algorithm that rounds the optimal fractional solution to a natural LP relaxation by using this solution to guide the decomposition of the input into a collection of single-demand-node capacitated facility location problems, which are then solved independently. In the special case that all facility opening costs are equal, we show that our algorithm is a 5-approximation algorithm, thereby also providing the first constant upper bound on the integrality gap of this formulation in this important special case. One salient feature of our algorithm is that it relies on a decomposition of the input into instances of the single-demand capacitated facility location problem; in this way, the algorithm Research suported partially by a grant from Motorola and NSF grant CCR-9912422. Research supported partially by NSF grant CCR-9912422. mirrors the work of Aardal [1], who presents a computational polyhedral approach for this problem which uses the same core problem in the identification of cutting planes. There are several variants of the capacitated facility location problem, which have rather different properties, especially in terms of the approximation algorithms that are currently known. One distinction is between soft and hard capacities: in the latter problem, each facility is either opened at some location or not, whereas in the former, one may specify any integer number of facilities to be opened at that location. Soft capacities make the problem easier; Shmoys, Tardos, & Aardal [11] gave the first constant approximation algorithm for this problem based on an LP-rounding technique; Jain & Vazirani [4] gave a general technique for converting approximation algorithm results for the uncapacitated problem into algorithms that can handle soft capacities. Korupolu, Plaxton, & Rajaraman [5] gave the first constant approximation algorithm that handles hard capacities, based on a local search procedure, but their approach worked only if all capacities are equal. Chudak & Williamson [3] improved this performance guarantee to 5.83 for the same uniform capacity case. P´al, Tardos, & Wexler [8] gave the first constant performance guarantee for the case of non-uniform hard capacities. This was recently improved by Mahdian & P´al [6] and Zhang, Chen, & Ye [13] to yield a 5.83-approximation algorithm. There is also a distinction between the case of unsplittable assignments and splittable ones. That is, suppose that each client j has a certain demand dj to be assigned to open facilities so that the total demand assigned to each facility is at most its capacity: does each client need to have all of its demand served by a unique facility? In the former case, the answer is yes, whereas in the latter, the answer is no. All approximation algorithms for hard capacities have focused on the splittable case. Note that once one has decided which facilities to open, the optimal splittable assignment can be computed by solving a transportation problem. A splittable assignment can be converted to an unsplittable one at the cost of increasing the required capacity at each facility (using an approximation algorithm for the generalized assignment problem [10]). Of course, if there are integer capacities and all demands are 1, there is no distinction between the two problems. For hard capacities, it is easy to show that the natural LP formulations do not have any constant integrality ratio; the simplest such example has two facility locations, one essentially free, and one very expensive. In contrast, we focus on the case in which all facility opening costs are equal. For ease of exposition, we will focus on the case in which each demand is equal to 1. However, it is a relatively straightforward exercise to extend the algorithm and its analysis to the case of general demands. We will use the terms “assignment cost” and “service cost” interchangeably. Our Techniques. The outline of our algorithm is as follows. Given the optimal LP solution and its dual, we view the optimal primal solution as a bipartite graph in which the nodes correspond to facility locations and clients, and the edges correspond to pairs (i, j) such that a positive fraction of the demand at client j is assigned to facility i by the LP solution. We use this to construct a partition of the demand and facilities into clusters: each cluster is “centered” at a client, and the neighbors of this client contained in the cluster are opened (in the fractional solution) in total at least 1/2. Each fractionally open facility location will, ultimately, be assigned to some cluster (i.e., not every facility assigned to this cluster need be a neighbor of the center), and each cluster will be expected to serve all of the demand that its facilities serve in the fractional solution. Each facility i that is fully opened in the fractional solution can immediately be opened and serve all of its demand; we view the remaining demand as located at the cluster center, and find a solution to the single-demand capacitated facility location problem induced by this cluster to determine the other facilities to open within this cluster. Piecing this together for each cluster, we then solve a transportation problem to determine the corresponding assignment. To analyze this procedure, we show that the LP solution can also be decomposed into feasible fractional solutions to the respective single-demand problems. Our algorithm for the single-node subproblems computes a rounding of this fractional solution, and it is important that we can bound the increase in cost incurred by this rounding. Furthermore, note that it will be important for the analysis (and the effectiveness of the algorithm) that we ensure that in moving demand to a cluster center, we are not moving it too much, since otherwise the solution created for the single-node problem will be prohibitively expensive for the true location of the demand. One novel aspect of our analysis is that the performance guarantee analysis comes in two parts: a part that is related to the fact that the assignment costs are increased by this displacement of the demand, and a part that is due to the aggregated effect of rounding the fractional solutions to the single-node problems. One consequence of this is that our analysis is not the “client-by-client” analysis that has become the dominant paradigm in the recent flurry of work in this area. Finally, our analysis relies on both the primal and dual LPs to bound the cost of the solution computed. In doing this, one significant difficulty is that the terms in the dual objective that correspond to the upper bound for the hard capacity have a -1 as their coefficient; however, we show that further structure in the optimal primal-dual pair that results from the complementary slackness conditions is sufficient to overcome this obstacle (in a way similar to that used earlier in [12]). Although our analysis applies only to the case in which the fixed costs are equal, our algorithm is sufficiently general to handle arbitrary fixed costs. Furthermore, we believe that our approach may prove to be a useful first step in analyzing more sophisticated LP relaxations of the capacitated facility location problem; in particular, we believe that the decomposition into single-node problems can be a provable effective approach in the more general case. Specifically, we conjecture that the extended flow cover inequalities of Padberg, Van Roy, and Wolsey [7] as adapted by Aardal [1] are sufficient to insure a constant integrality gap; this raises the possibility of building on a recent result of Carr, Fleischer, Leung, and Phillips [2] that showed an analogous result for the single-demand node problem. 2 A Linear Program We can formulate the capacitated facility location problem as an integer program and relax the integrality constraints to get a linear program (LP). We use i to index the facilities in F and j to index the clients in D. min fiyi + dj cij xij (P) i ji s.t. xij ≥ 1 ∀j (1) i xij ≤ yi ∀i, j (2) dj xij ≤ uiyi ∀i (3) j yi ≤ 1 ∀i (4) xij ,yi ≥ 0 ∀i, j. Variable yi indicates if facility i is open and xij indicates the fraction of the demand of client j that is assigned to facility i. The first constraint states that each client must be assigned to a facility. The second constraint says that if client j is assigned to facility i then i must be open, and constraint (3) says that at most ui amount of demand may be assigned to i. Finally (4) says that a facility can only be opened once. A solution where the yi variables are 0 or 1 corresponds exactly to a solution to our problem. The dual program is, max αj − zi (D) ji s.t. αj ≤ dj cij + βij + dj γi ∀i, j (5) βij ≤ fi + zi − uiγi ∀i (6) j αj ,βij ,γi,zi ≥ 0 ∀i, j. Intuitively αj is the budget that j is willing to spend to get itself assigned to an open facility. Constraint (5) says that a part of this is used to pay for the assignment cost dj cij and the rest is used to (partially) pay for the facility opening cost. For convenience, in what follows, we consider unit demands, i.e., dj =1 for all j. The primal constraint (3) and the dual constraint (5) then simplify to, xij ≤ uiyi,and αj ≤ cij + βij + γi, and the objective function of the primal j program (P) is min fiyi + All our results continue to hold in i j,i cij xij . the presence of arbitrary demands dj if the demand of a client is allowed to be assigned to multiple facilities. 3 Rounding the LP In this section we give a 5-approximation algorithm for capacitated facility location when all facility costs are equal. We will round the optimal solution to (P) to an integer solution losing a factor of at most 5, thus obtaining a 5-approximation algorithm. 3.1 The Single-Demand-Node Capacitated Facility Location Problem The special case of capacitated facility location where we have just one client or demand node (called SNCFL) plays an important role in our rounding algorithm. This is also known as the single-node fixed-charge problem [7] or the single-node capacitated flow problem. The linear program (P) simplifies to the following. min fivi + ciwi (SN-P) ii s.t. wi ≥ D i wi ≤ uivi ∀i (7) vi ≤ 1 ∀i (8) wi,vi ≥ 0 ∀i. Here D is the total demand that has to be assigned, fi ≥ 0 is the fixed cost of facility i,and ci ≥ 0 is the per unit cost of sending flow, or distance, to facility i. Variable wi is the total demand (or flow) assigned to facility i,and vi indicates if facility i is open. We show that a simple greedy algorithm returns an optimal solution to (SN-P) that has the property that at most one facility is fractionally open, i.e., there is at most one i such that 0 0into clusters each of which will be “centered” around a client that we will call the cluster center. We denote the cluster centered around client kby Nk. The cluster Nk consists of its center k, the set of facilities assigned to it, and the fractional demand served by the these facilities, i.e., j xij .The i∈Nk clustering phase maintains two properties that will be essential for the analysis. It ensures that, (1) each cluster contains a fractional facility weight of at least 12 , i.e., i∈Nk yi ≥ 12 , and (2) if some facility in cluster N k fractionally serves a client j, then the center kis not “too far” away from j(we make this precise in the analysis). To maintain the second property we require a somewhat more involved clustering procedure than the one in [11]. In the second phase of the algorithm we decide which facilities will be (fully) opened in each cluster. We consider each cluster separately, and open enough facilities in Nk to serve the fractional demand associated with the cluster. This is done in two steps. First, we open every facility in Nk with yi = 1. Next, we setupaninstanceof SNCFL. The instance consists of all the remaining facilities, and the entire demand served by these facilities, Dk = xij , considered as concentrated at the i∈Nk :yi<1 j center k. Now we use the greedy algorithm above to obtain an optimal solution to this instance with the property that at most one facility is fractionally open. Since the facility costs are all equal and each cluster has enough facility weight, we can fully open this facility and charge this against the cost that the LP incurs in opening facilities from Nk. Piecing together the solutions for the different clusters gives a solution to the capacitated facility location instance, in which every facility is either fully open or closed. Now we compute the min-cost assignment of clients to open facilities by solving a transportation problem. We now describe the algorithm in detail. Let F = {i: yi >0} be the (partially) opened facilities in (x,y), and Fj = {i: xij >0}be the facilities in Fthat fractionally serve client j. 1. Clustering. This is done in two steps. C1. At any stage, let C be the set of the current cluster centers, which is initially empty. We use Nk to denote a cluster centered around client k∈C. For each client j/∈C, we maintain a set Bj of unclustered facilities that are closer to it than to any cluster center, i.e., Bj = {i∈Fj : i/∈ Nk and cij ≤mink∈C cik}. (This definition of Bj is crucial in our k∈C analysis that shows that if client jis fractionally served by Nk,then kis not “too far” from j.) We also have a set S containing all clients that could be chosen as cluster centers. These are all clients j/∈C that send at least half of their demand to facilities in B j , i.e., S = {j/∈C : i∈Bj x ij ≥ 12 } . Of course, initially S= D,since C= ∅. While S is not empty, we repeatedly pick j ∈S with smallest αj value and form the cluster Nj = Bj around it. We update the sets C and S accordingly. (Note that for any cluster Nk, wehavethat i∈Nk yi ≥ xik ≥1 .) i∈Nk 2 C2. After the previous step, there could still be facilities that are not as signed to any cluster. We now assign these facilities in U = F− Nk k∈C to clusters. We assign i∈U to the cluster whose center is nearest to it, i.e., we set Nj = Nj {i}where j =argmink∈C cik. In addition, we assign to the cluster all of the fractional demand served by facility i.(After this step, the clusters Nj ,j ∈C partition the set of facilities F.) 2. Reducing to the single-node instances. For each cluster Nk,wefirst open each facility i in Nk with yi = 1. We now create an instance of SNCFL on the remaining set of facilities, by considering the total demand assigned to these facilities as being concentrated at the cluster center k.So our setof facilities is Lk = {i∈Nk : yi <1},each ci is the distance cik, and the total demand is Dk = xij . We use the greedy algorithm of Section 3.1 i∈Lk j ∗ to find an optimal solution (w(k),v(k)) to this linear program. Let O be k the value of this solution. We call the facility i such that 0 0 (including the extra facility). Note that the facilities opened (including each i such that yi = 1) have enough capacity to satisfy all the demand xij . Piecing together the solutions for all i∈Nk j the clusters, we get a solution where all the y variables are assigned values in {0,1}. 3. Assigning clients. We compute a minimum cost assignment of clients to open facilities by solving the corresponding transportation problem. 3.3 Analysis The performance guarantee of our algorithm will follow from the fact that the decomposition constructed by the algorithm of the original problem instance into single-node subproblems, one for each cluster, satisfies the following two nice properties. First, in Lemma 3.5, we show that the total cost of the optimal solutions for each of these single-node instances is not too large compared to OPT . We prove this by showing that the LP solution induces a feasible solution to (SN-P) for the SNCFL instance of each cluster and that the total cost of these feasible solutions is bounded. Second, in Lemma 3.7, we show that the optimal solutions to each of these single-node instances obtained by our greedy algorithm in Section 3.1, can be mapped back to yield a solution to the original problem in which every facility is either opened fully, or not opened at all, while losing a small additive term. Piecing together these partial solutions, we construct a solution to the capacitated facility location problem. The cost of this solution is bounded by aggregating the bounds obtained for each partial solution. We note that this bound is not based on a “client-by-client” analysis, but rather on bounding the cost generated by the overall cluster. Observe that there are two sources for the extra cost involved in mapping the solutions to the single-node instances. We might need to open one fractionally open facility in the optimal fractional solution to (SN-P). This is bounded in Lemma 3.6, and this is the only place in the entire proof which uses the assumption that the fixed costs are all equal. In addition, we need to transfer all of the fractional demand that was assumed to be concentrated at the center of the cluster, back to its original location. To bound the extra assignment cost involved, we rely on the important fact that if a client jis fractionally served by some facility i∈Nk, then the distance cjk is bounded. Since the triangle inequality implies that cjk ≤cij + cik, we focus on bounding the distance cik. This is done in Lemmas 3.3 and 3.4. In Lemma 3.8, we provide a bound on the facility cost and assignment cost involved in opening the facilities with yi =1, which, by relying on complementary slackness, overcomes the difficulties posed by the −zi term in the dual objective function. We then combine these bounds to prove our main theorem, Theorem 3.9, which states that the resulting feasible solution for the capacitated facility location problem is of cost at most 5 ·OPT . We first prove the following lemma that states a necessary condition for a facility ito be assigned to cluster Nk. Lemma 3.2. Let ibe a facility assigned to cluster Nk in step C1 or C2. Let C be the set of cluster centers just after this assignment. Then, kis the cluster center closest to iamong all cluster centers in C; that is, cik =mink ∈C cik . Proof. Since k∈C, clearly we have that cik ≥mink ∈C cik .If iis assigned in step C1, then it must be included when the cluster centered at kis first formed; that is, i∈Bk and the lemma holds by the definition of Bk.Otherwise,if iis assigned in step C2, then C is the set of all cluster centers, in which case it is again true by definition. For a client j, consider the point when jwas removed from the set S in step C1, either because a cluster was created around it, or because the weight of the facilities in Bj decreased below 12 when some other cluster was created. Let Aj = Fj \Bj be the set of facilities not in Bj at that point. Recall that there are two reasons for removing a facility ifrom the set Bj : it was assigned to some cluster Nk, or there was some cluster center k ∈C, such that cik 12 . Lemma 3.3. Consider any client jand any facility i∈Aj .If iis assigned to cluster Nk,then cik ≤αj . Proof. If k= j,(jcould be a cluster center), then we are done since Aj ⊆Fj and xij >0 implies that cij ≤αj (by complementary slackness). Otherwise, consider the point when jwas removed from Sin step C1, and let C be the set of cluster centers just after jis removed. Note that jcould belong to C if it is a cluster center. Since i/∈Bj at this point, either i∈Nk for some k ∈C or we have that cij >mink ∈C −{j} cik . In the former case, it must be that k = k, since the clusters are disjoint. Also, cik ≤αk,since Nk ⊆Fk,and αk ≤αj ,since kwas picked before jfrom S(recall the order in which we consider clients in S). In the latter case, consider the set of cluster centers C just after iis assigned to Nk (either in step C1 or step C2), and so k∈C . It must be that C ⊇C, since iwas removed from Bj before it was assigned to Nk, and by Lemma 3.2, cik =mink ∈C cik . Hence, cik ≤mink ∈C −{j} cik 0then w>0, so yˆ =1, and xˆ= w ≤ ui = uiyˆ .The ijii jiji i service cost is, (k)(k)(k)(k) cij xˆ ≤ cikxˆ+ cjk xˆ ≤ ciw +(cij + cik )xij . ij ij iji j,i∈Lk i∈Lk ,j j,i∈Lk i∈Lk j,i∈Lk Lemma 3.8. The cost of opening facilities i with yi =1,and for each such i,of sending xij units of flow from j to ifor every client j,is at most αj xij − j,i:yi=1 i zi. Proof. This follows from complementary slackness. Each facility i with zi > 0 has yi = 1. For any such facility we have, αj xij = cij xij + βij xij + γixij xij > 0 ⇒αj = cij + βij + γi j jjj βij > 0 ⇒xij = yi, = cij xij + βij yi + uiγiyi γi > 0 ⇒ = uiyi jj j xij yi > 0 ⇒ j βij + uiγi = cij xij + fi + zi. = fi + zi j Summing over all i with yi = 1 proves the lemma. Putting the various pieces together, we get the following theorem. Theorem 3.9. The cost of the solution returned is at most 5 ·OPT. Proof. To bound the total cost, it suffices to give a fractional assignment (ˆxij ) such that (ˆx, yˆ) is a feasible solution to (P) and has cost at most 5 ·OPT .We construct the fractional assignment as follows. First we set xˆij = xij for every facility i with yi =1= yˆi. This satisfies constraints (2)–(4) for i such that yi =1. By the previous lemma we have, fiyˆi + cij xˆij = αj xij − zi. (9) i:yi=1 j,i:yi=1 j,i:yi =1 i (k) x(k) Now for each cluster Nk,weset xˆij =ˆxij for i ∈Lk where (ˆ ,yˆ(k))is the partial solution for cluster Nk given by Lemma 3.7. All other xˆij variables are 0. Applying parts (i) and (ii) of Lemma 3.7 for all k ∈C,we get that (ˆx, yˆ)satisfies (2)–(4) for every i such that yi < 1, and xˆij = xij for every i:yi<1 i:yi<1 client j Hence, (ˆx, yˆ) satisfies constraints (2)–(4) and xˆij = xij + ii:yi=1 xij = 1, showing that (ˆx, yˆ) is a feasible solution to (P). Since the i:yi<1 clusters Nk are disjoint, from part (iii) of Lemma 3.7, we have, O∗ fiyˆi + cij xˆij ≤ k +2 fiyi + cij xij + cik(i)xij i:yi<1 j,i:yi<1 k∈C i j,i:yi<1 j,i:yi<1 ≤ 3 fiyi + cij xij +2 cik(i)xij . i j,i:yi<1 j,i:yi<1 where the last inequality follows from Lemma 3.5. For any client j and facility i ∈ Fj ,if i ∈Aj ,then wehave cik(i) ≤αj by Lemma 3.3; otherwise, by Lemma 3.4, cik(i) ≤cij ≤cij + αj for j ∈C,and cik(i) ≤cij + ci∗(j)j + αj for j/∈C. Plugging this in the above expression we get, fiyˆi + cij xˆij ≤ 3 fiyi + cij xij +2 αj xij i:yi<1 j,i:yi<1 i j,i:yi<1 j,i:yi<1 +2 cij xij +2ci∗(j)j xij . ji:yi<1 j/∈C i:yi<1 i/∈Aj i/∈Aj For j/∈C, i/∈Aj xij <12 .So 2ci∗(j)ji:yi <1,i/∈Aj xij is at most, cij xij ci∗(j)j =min cij ≤ i∈Aj < 2 cij xij . i∈Aj i∈Aj xij i∈Aj This implies that, fiyˆi + cij xˆij ≤ 3 fiyi + cij xij +2 αj xij i:yi <1 j,i:yi <1 i j,i:yi <1 j,i:yi<1 +2 cij xij +2 cij xij ji:yi <1 j/∈C i∈Aj i/∈Aj ≤ 2 αj xij +3 fiyi + cij xij . (10) j,i:yi<1 i j,i Finally, combining (9) and (10), we obtain that Total Cost ≤ αj xij − zi +2 αj xij +3 fiyi + cij xij j,i:yi=1 i j,i:yi<1 i j,i ≤ 2 αj xij − zi + αj xij +3 ·OPT =5 ·OPT . j,i:yi =1 i j,i:yi <1 References [1] K. Aardal. Capacitated facility location: separation algorithms and computational experience. Mathematical Programming, 81:149–175, 1998. [2] R. Carr, L. Fleischer, V. Leung, and C. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 106–115, 2000. [3] F. A. Chudak and D. P. Williamson. Improved approximation algorithms for capacitated facility location problems. In G. Cornu´ejols, R. E. Burkard, and G. J. Woeginger, editors, Integer Programming and Combinatorial Optimization, volume 1610 of Lecture Notes in Computer Science, pages 99–113, Graz, 1999. Springer. [4] K. Jain and V.V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48:274–296, 2001. [5] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146–188, 2000. [6] M. Mahdian and M. P´al. Universal facility location. In Proceedings of the 11th ESA, pages 409–421, 2003. [7] M. W. Padberg, T. J. Van Roy, and L. A. Wolsey. Valid linear inequalities for fxed charge problems. Operations Research, 33:842–861, 1985. ´ [8] M. P´al, E. Tardos, and T. Wexler. Facility location with nonuniform hard capacities. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 329–338, 2001. [9] D. B. Shmoys. Approximation algorithms for facility location problems. In Pro ceedings of 3rd APPROX, pages 27–33, 2000. ´ [10] D. B. Shmoys and E. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming A, 62:461–474, 1993. [11] D. B. Shmoys, E.´ Tardos, and K. I. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265–274, 1997. [12] C. Swamy and D. B. Shmoys. Fault-tolerant facility location. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 735–736, 2003. [13] J. Zhang, B. Chen, and Y. Ye. A multi-exchange local search algorithm for the capacitated facility location problem. Submitted to Mathematics of Operations Research, 2003.