Primal-Dual Schema for Capacitated Covering Problems? Tim Carnes and David Shmoys Cornell University, Ithaca NY 14853, USA Abstract. Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr, Fleischer, Leung & Phillips for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achieve the same performance guarantees as the LP-rounding algorithms of Carr et al., which rely on applying the ellipsoid algorithm to an exponentially-sized LP. Furthermore, we introduce new fow-cover inequalities to strengthen the LP relaxation of the more general capacitated single-item lot-sizing problem; using just these inequalities as the LP relaxation, we obtain a primal-dual algorithm that achieves a performance guarantee of 2. 1 Introduction Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr, Fleischer, Leung & Phillips [5] for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achieve the same performance guarantees as the LP-rounding algorithms of Carr et al., which rely on applying the ellipsoid algorithm to an exponentially-sized LP. Furthermore, we introduce new fow-cover inequalities to strengthen the LP relaxation of the more general capacitated single-item lot-sizing problem; using just these inequalities as the LP relaxation, we obtain a primal-dual algorithm that achieves a performance guarantee of 2. We say an algorithm is an approximation algorithm with a performance guarantee of when the algorithm runs in polynomial time and always produces a solution with cost within a factor of of optimal. Primal-dual algorithms are able to gain the benefts of LP-based techniques, such as automatically generating a new lower bound for each problem instance, but without having to solve ? Research supported partially by NSF grants CCR-0635121, CCR-0430682 & DMI0500263. an LP. Primal-dual approximation algorithms were developed by Bar-Yehuda & Even and Chv´atal for the weighted vertex cover and set cover problems, respectively [3, 7]. Subsequently, this approach has been applied to many other combinatorial problems, such as results of Agrawal, Klein & Ravi [2], Goemans & Williamson [10], Bertsimas & Teo [4] and Levi, Roundy & Shmoys [12] for other related covering problems. Other recent work has been done on covering problems with capacity constraints by Even, Levi, Rawitz, Schieber, Shahar & Sviridenko [8], Chuzhoy & Naor [6] and Gandhi, Halperin, Khuller, Kortsarz & Srinivasan [9]. In developing primal-dual (or any LP-based) approximation algorithms, it is important to have a strong LP formulation for the problem. However, there are cases when the LP relaxation of the natural IP formulation for a problem has a large integrality gap. When this happens, one can mend the situation by introducing extra valid inequalities that hold for any solution to the problem, but restrict the feasible region of the LP. One class of valid inequalities that has proved useful for a variety of problem are called fow-cover inequalities. A large class of fow-cover inequalities was developed by Aardal, Pochet & Wolsey [1] for the capacitated facility location problem. Carr et al. [5] developed a di erent style of fow-cover inequalities for simpler capacitated covering problems which we use in developing our primal-dual algorithms. Levi, Lodi & Sviridenko [11] used a subset of the fow-cover inequalities of Aardal et al. [1] to develop a LP-rounding algorithm for the multiple-item lot-sizing problem with monotone holding costs. Our model is not a special case of theirs, however, since our result allows time-dependent order capacitites whereas their result assumes constant order capacities across all periods. Following this work and the development of our own fow-cover inequalities for lot-sizing problems, Sharma & Williamson [13] demonstrated that the result of Levi et al. [11] has an analogue based on our fow-cover inequalities as well. Finally, it is worth noting that Van Hoesel & Wagelmans [14] have a FPTAS for the single-item lot-sizing problem that makes use of dynamic programming and input data rounding. The disadvantage of this result is that the running time of the algorithm can be quite slow for particular performance guarantees. Although the primal-dual algorithm we develop is a 2-approximation algorithm, this is a worst-case bound and we would expect it to perform much better on average in practice. Also this is the frst LP-based result for the case of time-dependent capacities. The three models studied in this paper are generalizations of one another. That is to say, the minimum knapsack problem is a special case of the single- demand capacitated facility location problem, which is a special case of the single-item lot-sizing problem. We present the result in order of generality with the aim of explaining our approach in the simplest setting frst. The minimum knapsack problem gives a set of items, each with a weight and a value. The objective is to fnd a minimum-weight subset of items such that the total value of the items in the subset meets some specifed demand. In the single-demand facility location problem there is a set of facilities, each with an opening cost and a capacity, as well as a per-unit serving cost that must be paid for each unit of demand a facility serves. The goal is to open facilities to completely serve a specifed amount of demand, while minimizing the total service and facility opening costs. Finally the single-item lot-sizing problem considers a fnite planning period of consecutive time periods. In each time period there is a specifed level of demand, as well as a potential order with a given capacity and order opening cost. A feasible solution must open enough orders and order enough inventory so that in each time period there is enough inventory to satisfy the demand of that period. The inventory is simply the inventory of the previous time period plus however much is ordered in the current time period, if any. However, a per-unit holding cost is incurred for each unit of inventory held over a given time period. The straightforward LP relaxations for these problems have a bad integrality gap, but can be strengthened by introducing valid fow-cover inequalities. The inequalities Carr et al. [5] developed for the minimum knapsack problem are as follows X ui(A)yi D − u(A) 8A F, i2F \A where the yi are the binary decision variables indicating if item i is chosen, u(A) is the total value of the subset of items A, and the ui(A) can be thought of as the e ective value of item i with respect to A, which is the minimum of the actual value and the right-hand-side of the inequality. These inequalities arise by considering that if we did choose all items in the set A, then we still have an induced subproblem on all of the remaining items, and the values can be truncated since we are only concerned with integer solutions. Our primal- dual algorithm works essentially as a modifed greedy algorithm, where at each stage the item is selected that has the largest value per cost. Instead of the actual values and costs, however, we use the e ective values and the slacks of the dual constraints as costs. Similar to the greedy algorithm for the traditional maximum-value knapsack problem, the last item selected and everything selected beforehand, can each be bounded in cost by the dual LP value, yielding a 2approximation. The remainder of this paper is organized as follows. In Section 2 we go over the minimum knapsack result in more detail. In Section 3 we generalize this result to apply to the single-demand capacitated facility location problem. Finally in Section 4 we generalize the fow-cover inequalities to handle the lot-sizing problem, and then present and analyze a primal-dual algorithm for the single-item lot-sizing problem. 2 Minimum Knapsack In the minimum knapsack problem one is given a set of items F , and each item i 2 F has a value ui and a weight fi. The goal is to select a minimum weight subset of items, S F, such that the value of S, u(S), is at least as big as a specifed demand, D. The natural IP formulation for this problem is X optMK := min fiyi (MK-IP) i2FX s.t. uiyi D (1) i2F yi 2 {0, 1} 8i 2 F, where the yi variables indicate if item i is chosen. The following example from [5] demonstrates that the integrality gap between this IP and the LP relaxation is at least as bad as D. Consider just 2 items where u1 = D − 1, f1 = 0, u2 = D and f2 = 1. The only feasible integer solution chooses both items and has a cost of 1, whereas the LP solution can set y1 = 1 and y2 =1/D and incurs a cost of only 1/D. To remedy this situation we consider using the fow-cover inequalities introduced in [5]. The idea is to consider a subset of items A F such that u(A) 0, and once we fnish we call our fnal set of items S, which is our integer solution. This is a feasible solution to (MK-IP) since D(S) 0, which implies u(S) D. Algorithm 1: Primal-Dual for Minimum Knapsack y, v 0 A ; while D(A) > 0 do Increase v(A) until a dual constraint becomes tight for item i yi 1 AA [{i} SA Theorem 1. Algorithm 1 terminates with a solution of cost no greater than 2 · optMK . Proof. Let ` denote the fnal item selected by Algorithm 1. Then because the algorithm only continues running as long as D(A) > 0 we have that D(S \{`}) > 0 ) D − u(S \{`}) > 0 ) u(S \{`}) < D. Also, the variable v(A) is positive only if A S \{`}. Thus, since the algorithm only selects items for which the constraint (3) has become tight, we have that the cost of the solution produced is X XXX fiyi = fi = ui(A)v(A). i2Fi2Si2SA F :i62A The expression on the right-hand side is summing over all items, i, in the fnal solution S, and all subsets of items, A, that do not contain item i. This is the same as summing over all subsets of items, A, and all items in the fnal solution that are not in A. Thus we can reverse the order of the summations to obtain X XX fiyi = v(A) ui(A) i2FA Fi2S\A X = v(A)(u(S \{`}) − u(A)+ u`(A)) A F X 0 do Increase v(F1,F2,A) until a dual constraint becomes tight for facility i if i 2F1 then /* i tight on (8) but not on (9) */ Move i from F1 into F2 else /* else i tight on (8) and (9) */ xi ui(A)/D yi 1 Move i from F2 into A SA Clearly Algorithm 2 terminates with a feasible solution to (FL-IP) since all of the demand is assigned to facilities that are fully opened. Theorem 2. Algorithm 2 terminates with a solution of cost no greater than 2 · optFL. Proof. Let ` denote the fnal facility selected by Algorithm 2. By the same reasoning as in Section 2 we have D(S \{`}) > 0 ) D − u(S \{`}) > 0 ) u(S \{`}) < D. The variable v(F1,A) is positive only if A S \{`}. If a facility is in S then it must be tight on both constraints (8) and (9) so XX (fiyi + Dcixi)= (fi + Dcixi) i2Fi2S 23 XX X = 4 ui(A)v(F1,F2,A)+ xi Dv(F1,F2,A)5 , i2S (F1 ,F2,A)2F:i2F2 (F1,F2,A)2F:i2F1 as in Section 2 we can simply reverse the order of summation to get "# X XXX (fiyi + Dcixi)= v(F1,F2,A) ui(A)+ Dxi . i2F (F1,F2 ,A)2F i2S\F2 i2S\F1 Recall that at the last step of Algorithm 2, facility ` was assigned D(S \{`}) amount of demand. Since D(A) only gets smaller as the algorithm progresses, we have that regardless of what summation above the facility ` is in, it contributes no more than D(A). All of the other terms can be upper bounded by the actual capacities and hence XX (fiyi + Dcixi)= v(F1,F2,A)[u(S \{`}) − u(A)+ D(A)] i2F (F1,F2,A)2F X < 2D(A)v(F1,F2,A) 2 · optF LD, (F1,F2,A)2F where the strict inequality above follows from the observation made earlier. ut 4 Single-Item Lot-Sizing with Linear Holding Costs In the single-item lot-sizing problem, one is given a planning period consisting of time periods F := {1,...,T}. For each time period t 2 F , there is a demand, dt, and a potential order with capacity ut, which costs ft to place, regardless of the amount of product ordered. At each period, the total amount of product left over from the previous period plus the amount of product ordered during this period must be enough to satisfy the demand of this period. Any remaining product is held over to the next period, but incurs a cost of ht per unit of product stored. If we let t−1 X hst = hr r=s and set htt = 0 for all t 2 F , then we obtain a standard IP formulation for this problem as follows TX TTX X optLS := min fsys + hstdtxst (LS-IP) s=1 s=1 t=s tX s.t. xst = 1 8t (10) s=1 TX dtxst usys 8s (11) t=s xst ys 8s t (12) ys 2 {0, 1} xst 0 8s 8s t. where the ys variables indicate if an order has been placed at time period s, and the xst variables indicate what fraction of the demand dt is being satisfed from product ordered during time period s. This formulation once again su ers from a bad integrality gap, which can be demonstrated by the same example as in the previous two sections. We introduce new fow-cover inequalities to strengthen this formulation. The basic idea is similar to the inequalities used in sections 2 and 3. We would like to consider a subset of orders, A, where even if we place all the orders in A and use these orders to their full potential, there is still unmet demand. In the previous cases, the amount of unmet demand was D(A)= D − u(A). Now, however, that is not quite true, since each order s is capable of serving only the demand points t where t s. Instead, we now also consider a subset of demand points B, and defne d(A, B) to be the total unmet demand in B, when the orders in A serve as much of the demand in B as possible. More formally XX d(A, B) := min d(B) − dtxst (RHS-LP) s2At s:t2B t X s.t. xst 1 8t (13) s=1 T X dtxst us 8s (14) t=s xst 0 8s t. As before, we would also like to restrict the capacities of the orders not in A. To do this, we defne us(A, B) := d(A, B) − d(A [{s},B), (15) which is the decrease in remaining demand that would result if order s were added to A. (This reduces to the same us(A) as defned in the previous sections when considered in the framework of the earlier problems.) We once again partition the remaining orders in F \ A into two sets, F1 and F2, and count the P contribution of orders in F1 as dtxst and orders in F2 as us(A, B)ys. This t leads to the following LP, where once again F is the set of all 3-tuples that partition F into three sets. T TT X XX optLSP := min fsys + hstdtxst (LS-P) s=1 s=1 t=s XX s.t. dtxst + us(A, B)ys d(A, B) (16) s2F1,s2F2 8(F1,F2,A) 2F,B F t2B xst,ys 0 8s, t. Lemma 1. Any feasible solution to (LS-IP) is a feasible solution to (LS-P). Proof. Consider a feasible integer solution (x, y) to (LS-IP) and let S := {s : ys =1}. Now for any (F1,F2,A) 2F and B F we know X dtxst d((F2 \ S) [ A, B), s2F1, t2B since there is no way to assign demand from B to orders in (F2 \ S) [ A without leaving at least d((F2 \ S) [ A, B) amount of demand unfulflled. Thus at least that amount of demand must be served by the other orders in S, namely those in F1. Let k := |F2 \S| and let s1,...,sk denote the elements of that set in some order. Furthermore let Si := {s1,...,si} for each 1 i k, so Sk = F2 \ S. Then by repeated use of (15) we have X dtxst d((F2 \ S) [ A, B) s2F1, t2B = d(((F2 \ S) [ A) \ S1,B) − us1 (((F2 \ S) [ A) \ S1,B) k X = d(((F2 \ S) [ A) \ Sk,B) − usi (((F2 \ S) [ A) \ Si,B) i=1 k X = d(A, B) − usi (((F2 \ S) [ A) \ Si,B) i=1X d(A, B) − us(A, B) s2F2\S X d(A, B) − us(A, B)ys, s2F2 where the inequalities follow since us(A, B) is increasing as elements are removed from A. Thus (x, y) satisfes all of the fow-cover inequalities (16). ut The dual of (LS-P) is X optLSD := max d(A, B)v(F1,F2, A, B) (LS-D) (F1,F2,A)2F X s.t. v(F1,F2, A, B) hst 8s t (17) (F1,F2,A)2F,B F : s2F1,t2B X us(A, B)v(F1,F2, A, B) fs 8s (18) (F1,F2,A)2F,B F : s2F2 v(F1,F2, A, B) 0 8(F1,F2,A) 2F,B F, where we simply divided constraint (17) by dt. Before we get to a primal-dual algorithm, we must frst introduce some notation and associated machinery. "# t X et := dt 1 − xrt -amount of demand currently unsatisfed in period t r=1 We defne Fill(A, B) to be the following procedure that describes how to assign demand from B to orders in A. We consider the orders in A in arbitrary order, and for each order we serve as much demand as possible, processing demands from earliest to latest. In the previous two sections, there was e ectively only one demand, and so we never had to be concerned about how demand is assigned once an item or facility is chosen. Now there are many demand points, and so we must be careful that as we maintain our solution set A, we are serving as much demand as possible from the orders in A. The way the primal-dual algorithm will assign demand will correspond with how the Fill procedure works, and we show that this is a maximal assignment. Lemma 2. If we start from an empty demand assignment and run Fill(A, B), then we obtain a demand assignment such that e(B)= d(A, B). Thus, Fill produces an assignment that is optimal for (RHS-LP). Proof. Consider the latest time period t 2 B where e(t) > 0. All orders at time periods at or before t must be serving up to capacity, since otherwise they could have served more of demand dt. All orders after time period t could not have served any more demand in B since all demand points in B after t are fully served. ut Just as in the previous two sections, the primal-dual algorithm initializes the variables to zero and the set A to the empty set. As in Section 3, we initialize F1 to be the set of all orders, and an order will become tight frst on constraint (17), when it will be moved to F2, and then tight on (18), when it will be moved to A. Unlike in Section 3, however, constraint (17) consists of many di erent inequalities for the same order. This diÿculty is averted since all the constraints (17) for a particular order will become tight at the same time, as is proved below in Lemma 3. This is achieved by slowly introducing demand points into the set B. Initially, B will consist only of the last demand point, T . Every time an order becomes tight on all constraints (17), it is moved from F1 into F2, and the demand point of that time period is added to B. In this way we always maintain that F1 is a prefx of F, and B is the complementary suÿx. When an order s becomes tight on constraint (18), we move it to A and assign demand to it by running the procedure Fill(s, B). Additionally we create a reserve set of orders, Rs, for order s, that consists of all orders earlier than s that are not in F1 at the time s was added to A. Finally, once all of the demand has been assigned to orders, we label the set of orders in A as our current solution, S , and now enter a clean-up phase. We consider the orders in the reverse order in which they were added to A, and for each order, s, we check to see if there is enough remaining capacity of the orders that are in both the reserve set and our current solution, S \ Rs, to take on the demand being served by s. If there is, then we reassign that demand to the orders in S \ Rs arbitrarily and remove s from our solution S . When the clean-up phase is fnished we label the nodes in S as our fnal solution, S. Algorithm 3: Primal-Dual for Single-Item Lot-Sizing xst,ys 0 F1 F F2,A ; B {T } while d(A, F ) > 0 do Increase v(F1,F2, A, B) until dual constraint becomes tight for order s if s 2F1 then /* s tight on (17) but not on (18) */ Move s from F1 into F2 BF \F1 else /* else s tight on (17) and (18) */ ys 1 Fill(s, B) Move s from F2 into A Rs {r 2F \F1 : r 0, we have X XX us(A, B)+ dtxst