MANAGEMENT SCIENCE inform ® Vol. 54 No. 4 April 2008 pp. 763–776 doi 10.1287/mnsc.1070.0781 issn 0025-1909 · eissn 1526-5501 · 08 · 5404 · 0763 © 2008 INFORMS Copyri ht: INFORM holds copyright to this Articl s in Advanc version, which is made available to institutional subscribers. Thefile may not be posted on any other website, including the author’s site. Please send any questions regarding this policy to permissions@informs.org. A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem Retsef Levi Sloan School of Management Massachusetts Institute of Technology Cambridge Massachusetts 02139 retsef@mit.edu Robin Roundy School of Operations Research and Information Engineering Cornell University Ithaca New York 14853 robin@orie.cornell.edu David Shmoys School of Operations Research and Information Engineering and Department of Computer Science Cornell University Ithaca New York 14853 shmoys@cs.cornell.edu Maxim Sviridenko IBM T. J. Watson Research Center Yorktown Heights New York 10598 sviri@us.ibm.com D D eterministic inventory theory provides streamlined optimization models that attempt to capture trade-offs in managing the flow of goods through a supply chain. We will consider two well-studied deterministic inventory models called the one-wa ehouse multi etaile (OWMR) problem and its special case the joint eplenishment p oblem (JRP) and give approximation algorithms with worst-case performance guarantees. That is for each instance of the problem our algorithm produces a solution with cost that is guaranteed to be at most 1.8 times the optimal cost; this is called a 1.8-app oximation algo ithm. Our results are based on an LP-rounding approach; we provide the first constant approximation algorithm for the OWMRproblem and improve the previous results for the JRP. Key wo ds: deterministic inventory theory; approximation algorithms; linear programming Histo y: Accepted by Dorit Hochbaum optimization and modeling; received July 14 2004. This paper was with the authors 1 year and 5 months for 2 revisions. Published online in A ticles in Advance March 12 2008. 1. Intr ducti n Deterministic inventory theory provides streamlined optimization models that attempt to capture trade- offs in managing the flow of goods through a supply chain. We will consider two well-studied inventory models the one-wa ehouse multi etaile (OWMR) problem and its special case the joint eplenishment p oblem (JRP). Using linear programming (LP)-rounding techniques we provide the first constant approximation algorithm for the OWMRproblem. That is for each instance of the problem our algorithm produces a solution with cost that is guaranteed to be at most C times the optimal cost for some constant C> 1. The constant C is called the wo st-case gua antee of the algorithm. Moreover when specialized to the JRP model our LP-rounding approach provides worst- case guarantees that improve on previous approximation algorithms for this problem by Levi et al. (2006). As the name suggests in the OWMRmodel there is one warehouse that orders a particular commodity from a supplier to serve demand at N distinct retailers. We consider a discrete finite planning horizon of T periods and are given the demand di ≥ 0 required for each retailer i = 1  N in each time period = 1  T . There are two types of costs incurred: o de ing costs (to model that there are fixed costs incurred each time the warehouse replenishes its supply on hand from the supplier as well as the analogous cost for each retailer to be stocked from the warehouse) and holding costs (to model the fact that maintaining inventory at both the warehouse and the retail store incurs a cost). The aim of the model is to provide an optimization framework to balance the fact that ordering too frequently is inefficient for ordering costs whereas ordering too rarely incurs excessive holding costs. The dynamics of the OWMRmodel are as follows. At the beginning of each period s each retailer i can place an order for any number of units from the warehouse to replenish its on-hand inventory. The order is assumed to arrive instantaneously (this is without loss of generality) and can be used to satisfy demand in period s or in subsequent periods. Any such order placed by retailer i incurs a fixed ordering cost Ki which is independent of the size of the order and of the time period in which the order is placed. However all orders placed by the different retailers in 763 Management Science 54(4) pp. 763–776 © 2008 INFORMS each period s must be satisfied only from the on-hand inventory at the warehouse in that period. Then in turn at the beginning of each period r the warehouse can place an order for any number of units from the supplier. This order is again assumed to arrive instantaneously and can be used to satisfy retailer orders in period r or in subsequent periods. Any such order of the warehouse in period r incurs a fixed ordering cost Kr 0 which also is independent of the size of the order and the combination of items being ordered. All demands must be satisfied on time i.e. any unit that is used by retailer i to satisfy its demand in period di must be ordered by the warehouse from the supplier in some period r and then by retailer i from the warehouse in some period s where r ≤ s ≤ . (In the inventory literature these assumptions are usually referred to as “neither back orders nor lost sales are allowed.”) The goal is to find a feasible ordering policy that satisfies all demands on time with minimum total ordering and holding costs. Throughout the paper we will use rs (r ≤ s)to denote a pair of warehouse and retailer orders in periods r and s respectively. We note that while the warehouse ordering cost Kr 0 is time dependent the retailer ordering cost Ki is stationary over time. It is easy to show that if we allow it to be time dependent then the OWMRproblem becomes as hard as the set- cover problem (see Chan et al. 2000 for the details). Thus it is not likely that there exists an approximation algorithm with a sublogarithmic worst-case guarantee (Feige 1998). The standard models for holding cost make two natural linearity assumptions: (1) the cost is proportional to the number of units of the commodity held and (2) there is cost associated with holding inventory from period to 1 which is then additive over the periods held. We use a more general holding-cost structure extending the model that has been introduced by Levi et al. (2006) for the JRP. While still maintaining (1) we generalize (2) in a way that preserves the most useful properties of an optimal solution (as well as of an optimal solution to a natural LP relaxation) but captures much more general phenomena such as the notion of perishable goods (where the holding cost becomes infinite when the good is held too long). Capturing the right generalization is subtle here due to the nature of the interaction between the two levels and this is outlined in §2; we introduce in essence a holding cost hi rs associated with ordering one unit of the demand at retailer i for period according to the pair rs which is assumed to satisfy certain natural monotonicity properties. The one-warehouse multiretailer problem is a generalization of several classical inventory models such as the single-item lot-sizing p oblem (in which there is in effect only one retailer and the warehouse holding and ordering costs are 0) and the JRP (where in effect the holding cost at the warehouse is enormous and hence each unit of demand can be assumed to be satisfied by an order ss ). The general OWMRmodel has been studied extensively and plays a fundamental role in broader planning issues such as the management of supply chains. Arkin et al. (1989) have shown that the OWMR problem is NP-hard even for the special case of the JRP where the warehouse serves only as a cross- docking point (i.e. no inventory is ever held at the warehouse). Federgruen and Tzur (1999) have proposed an interesting heuristic based on dynamic programming. However for the theoretical analysis of the worst-case performance of their algorithm they have assumed that the cost parameters and the demands are bounded by uniform constants. Chan et al. (2000) have considered a variant of the OWMR problem in which the ordering costs are piecewise- linear functions and the holding cost is linear and additive. They considered the class of ze o-invento y o de ing (ZIO) policies in which the warehouse and retailers order if and only if their current on-hand inventory is zero. They established the effectiveness of these policies showing that the cost of the optimal ZIO policy is at most 34 times the cost of the optimal policy. In Chan et al. (2000) and in a subsequent paper by Shen et al. (2002) they have proposed an integer program to find the optimal ZIO policy which is NP-hard. Next they have developed heuristics to round the optimal solution of the LP relaxation to get an approximation algorithm for finding the best ZIO policy. However the performance guarantee of their algorithm is O log N T . For the problem we consider in this paper it is well known that ZIO policies are optimal. This work has been further generalized by Shen et al. (2007). Recently Levi et al. (2004 2006) presented a general primal-dual algorithmic framework that solves the single-location lot-sizing problem and provides a 2-approximation for the JRP and the assembly p oblem which is yet another classical inventory model (see Levi et al. 2004 2006). It is an open question whether the primal-dual approach can be extended to work in the more general OWMRproblem considered in this paper. The main barrier seems to be the more complex structure involved with holding inventory in two “levels” (the warehouse and retailers) which does not seem to preserve several properties that are essential for the analysis in Levi et al. (2004 2006). For the problem we consider in this paper it is well known that ZIO policies are optimal (Schwarz 1973). We propose a natural integer program to find the optimal policy which is different from the one proposed in Chan et al. (2000) and Shen et al. (2002). We first solve the LP relaxation to optimality and then Levi et al.: A Constant App oximation Algo ithm fo the One-Wa ehouse Multi etaile P oblem Management Science 54(4) pp. 763–776 © 2008 INFORMS Copyri ht: INFORM holds copyright to this Articl s in Advanc version, which is made available to institutional subscribers. Thefile may not be posted on any other website, including the author’s site. Please send any questions regarding this policy to permissions@informs.org. introduce techniques to round this optimal solution to a feasible solution for the OWMRproblem which can be proven to be near-optimal. The rounding is done in two phases. In the first phase we determine the warehouse orders; based on that we determine the retailer orders in the second phase and this is done separately for each retailer. Our algorithms are based on new dependent randomized rounding techniques that are similar in spirit to those used for the met ic facility-location p oblem (Shmoys 2004) but are able to exploit the additional special structure of the inventory model. Specifically we show that the solution produced by the randomized algorithms has expected cost that is guaranteed to be at most 1.8 times the cost of an optimal solution to the OWMRproblem. We then show how to derandomize these algorithms and this yields a deterministic 1.8-approximation algorithm for the OWMRproblem. When specialized to the JRP our LP is identical to the one used by Levi et al. (2004 2006). Thus the LP-rounding approach can be applied to the JRP and improves on their primal-dual 2-approximation for the JRP. The inventory models that are discussed in this paper are usually solved in practice via integer programming solution methods such as branch and bound. We believe that our techniques can be naturally incorporated into these methods to generate good feasible solutions and enhance the computational procedures. One note on the relation between deterministic inventory models and the facility location problem is in order. If one thinks of orders as facilities and demands as customers then deterministic inventory models can be viewed as special facility- location problems. Nevertheless the inventory models we consider are significantly different because the holding-cost structure which plays the role of the assignment costs is asymmetric and does not obey the triangle inequality. These are both essential assumptions in all of the existing approximation algorithms for the metric facility-location problem. It is interesting that the additional structure of these inventory problems is sufficient to extend some of these techniques. (For a survey on the approximation techniques that were applied to the metric facility- location problem see Shmoys 2004.) In the appendix we also consider an important extension of the above models. In many real-life applications the ordering cost actually corresponds to t anspo tation cost. Usually the transportation is based on trucks with a given capacity. We model this using soft capacities. Now we can order in batches each of capacity U where for each batch we order (in a given period) we incur an additional fixed cost. We allow different batch capacities for the warehouse and the retailers and then show how to extend the algorithms developed for the OWMRproblem to work in this more general model. In particular we provide a 3.6-approximation algorithm for the JRP and the OWMRproblem with soft capacities and a 2-approximation algorithm for the single-location lot sizing (with time-dependent batch capacities). Here we are using ideas and techniques that were introduced by Jain and Vazirani in their seminal paper on the facility-location problem (Jain and Vazirani 2001). Jin and Muriel (2005) also consider this model and propose several heuristics based on centralized and decentralized approaches. As a by-product of our work we prove upper bounds on the integrality gap of facility location inspired LP relaxations for several variants of the OWMRproblem. Specifically for the special case of the OWMRproblem the single-location lot-sizing problem it can be shown that our rounding approach when applied to the facility location-inspired linear program of this problem yields an optimal solution. (As already mentioned here we have only one retailer and there is no warehouse. There is only one ordering cost Ks in each period s and holding costs as before.) This shows that the corresponding LP has an integer optimum. Other proofs with very different styles were given by Krarup and Bilde (1977) Bárány et al. (1984) Bertsimas et al. (1999) and recently by Levi et al. (2006). Finally for the single-location lot- sizing problem with soft capacities we show (in the appendix) that the natural facility location-inspired LP has an integrality gap of at most two. The rest of this paper is organized as follows. In §2 we discuss the holding-cost structure that we use in this paper. In §3 we present an LP relaxation of the OWMRproblem and discuss some of the properties of fractional optimal solutions of the LP. In §4 we describe our rounding algorithms and their worst- case analysis. The extension to soft capacities is considered in the appendix. In §5 we conclude with some open questions. 2. The H lding-C st Structure In most of the existing literature the holding cost is modeled in the following way. For each period the warehouse and each retailer i have a per-unit cost hi ≥ 0(i = 01  N ) to hold one unit in inventory from period to period 1. The holding cost incurred at the end of each period is a linear function of the on-hand inventory at the end of the period. We model the holding cost in the following more general way. Consider a demand point i and a pair of potential orders rs where again r is the period in which the unit was ordered by the warehouse from the supplier and s is the period in which it was ordered by retailer i from the warehouse Management Science 54(4) pp. 763–776 © 2008 INFORMS r ≤ s ≤  . For each i and rs welet hi rs be the cost of holding one unit in the warehouse location over rs then sending it to retailer i (in period s) and holding it at the premises of retailer i over s . We assume that the holding-cost parameters obey the following natural properties: hi P ope ty 1: Non-negativity. The parameters rs are assumed to be nonnegative. P ope ty 2: Monotonicity with espect to s. Each retailer i = 1  N has exactly one of the following properties that applies to all demand points i (for = 1  T ). For each demand point i and warehouse order in period r (r ≤ ) hi rs is either nonincreasing in s ∈ r or it is nondecreasing in s ∈ r .We partition the retailers into two sets accordingly. Let IJ be the set of retailers i such that hi rs is nondecreasing in s for each and r ≤ and call them J - etaile s and let IW be the rest of the retailers i.e. retailers i such that hi rs is nonincreasing in s for each and r ≤ and call them W - etaile s. In models with the traditional holding-cost structure the set IJ corresponds to retailers for which it is cheaper to hold inventory at the retailer premises (i.e. hi ≤ h0 for each ) and IW corresponds to retailers for which it is cheaper to hold inventory at the warehouse (i.e. hi >h0 for each ). It is straightforward to see that in an optimal policy the warehouse does not hold inventory of J -retailers. Instead in each period in which the warehouse orders some amount of units for J -retailers it is cheapest to distribute the complete amount immediately to these retailers. Thus for these retailers it is sufficient to consider only pairs of orders ss . Moreover the joint replenishment problem is the special case where all of the retailers are J -retailers. We note that the partition of the retailers into these two types is a standard assumption in the literature. In particular the OWMRproblem is traditionally considered under the assumption that hi >h0 for each i and . P ope ty 3: Monotonicity with Respect to r. For each retailer i and some demand point i fix the retailer order in some period s (s ≤ ); we assume that hi rs is nonincreasing in r ∈ 1 s . Moreover for each retailer i ∈ IJ and a demand point i we assume that for each r 0 (1) xi ≤ yi rs s rr≤s i=1  N =1  Ts =1   (2) i 0 xrs ≤ yr sr≤s≤ i = 1  N = 1  Tr = 1   (3) i i xrs yr ∈ 01 i = 0  Ns = 1  T r = 1  s = s T (4) Constraint (1) ensures that each positive demand point i is fully satisfied no later than period . Constraint (2) ensures that no demand di can be satisfied by a retailer order in period s ≤ (and some warehouse order in period r ≤ s) unless retailer i indeed placed an order in period s. Lastly constraint (3) ensures that no demand point di can be satisfied by a warehouse order in period r (and some retailer order r ≤ s ≤ ) unless the warehouse placed an order in period r. It is straightforward to see that the corresponding integer program provides a correct formulation of the OWMRproblem. Hence if we relax the i i i i binary constraints xy ∈ 01 to xy ≥ 0 we get rsr rsr an LP relaxation that provides a lower bound on the cost of any feasible solution to the OWMRproblem. For the rest of this paper we let xˆ yˆ and op LP be the optimal solution and the value of (P) respectively. We note again that for each retailer i in IJ it suffices to consider only the variables xrsi with r = s (the warehouse does not hold inventory of J -retailers). emma 1. There exi t an optimal olution to the OWMR problem where each J-retailer order i placed in a period in which there i al o a warehou e order. Assume that there exists an optimal solution to the OWMRproblem in which a retailer order of some J-retailer i is placed in some period s where there is no warehouse order placed in that period. Let r be the latest warehouse order placed by time period s . That is there is no warehouse order placed in each of the periods r ∈ rs . Because the holding costs are monotonic in r (Property 2 of the holding costs) and the solution is assumed to be optimal we can assume without loss of generality that all the units ordered by retailer i in period s were ordered by the warehouse in period r . Because i is a J -retailer it is clear that canceling the order in period s and placing instead a retailer order at r will not increase the retailer ordering cost and will decrease the overall holding costs incurred by retailer i (Property 3 of the holding costs). The lemma then follows. Consequently for each retailer i ∈ IJ we can adapt accordingly constraints (1)–(3). In particular for each i ∈ IJ and each period s the modified constraints (2) i i i 0 and (3) are x ≤ y and x ≤ y respectively. It is easy sss rrr to see that in an optimal solution we must have ysi ≤ ys 0 for each period s = 1  T . Next we discuss several structural properties of the optimal solution (xˆ yˆ) that will be used throughout the rest of this paper. 3.1. Structural Pr perties fthe Optimal S luti n f(P) The Monge P ope ty. Recall the Monge property of the holding cost i.e. Property 4 of h in §2. We say that a feasible solution (xy) to (P) satisfies the Monge i i property if x> 0(r ≤ s ≤ ) implies that x = 0 for rs r˜ s˜ any r˜ s˜ such that ˜ and ˜ Without loss of rs. generality we assume that xˆ yˆ (the optimal solution of (P)) satisfies the Monge property. We note that because of the Monge property on the holding cost any feasible solution to (P) can be converted in polynomial time to one that satisfies the Monge property and has no greater cost. The G eedy Usage P ope ty. We claim that there exists an optimal solution xˆ yˆ to (P) with the property that for each demand point i and a retailer-i i i order in period s ≤ we have xˆ rs = yˆ s except r∈ 1 s for possibly the earliest retailer-i order that fractionally serves i in the solution xˆ yˆ . (By the earliest retailer-i order that fractionally serves i we i i mean s¯ such that xˆ > 0 and xˆ= 0 r∈ 1 s¯ rs¯ r∈ 1 s rs for each s 0or yˆ si > 0 respectively. Consider some positive demand point i and the sequence of open retailer-i fractional orders in xˆ yˆ over the time interval 1  . Intuitively the g eedy usage p ope ty means that in the optimal solution xˆ yˆ demand point i fractionally uses the open retailer (fractional) orders in a g eedy manner from latest to earliest. One of the implications of this property is that each open fractional retailer-i order s ∈ 1  i i (i.e. yˆ > 0) such that yˆ < 1 is fully used by ss∈ s s i . That is xˆi = yˆi . (In other words con r∈ 1 srs s straint (2) is tight.) The greedy usage property follows from the monotonicity properties of h specifically from Properties 2 and 3. For any feasible solution for (P) that does not satisfy the greedy usage property there exists another feasible solution that does satisfy the property and has an objective values that is not higher. In particular assume that there exist two retailer orders s 0. Let r ≤ s be such that xˆ > 0 and r∈ 1 s rs rs i i i = min xˆ yˆ− xˆ .If i ∈ IW it is straight rss r∈ 1 s rs forward to verify that by increasing xˆ ri s by and Management Science 54(4) pp. 763–776 © 2008 INFORMS decreasing xˆ ri s by we get a feasible solution with objective values that is not higher. (This follows from Property 2.) If i ∈ IJ then r = s and by Property 2 i i it follows that increasing xˆ by and decreasing xˆ ss ss by result in a feasible solution with no greater cost. (This follows from Property 3.) 4. The Rand m Shift Alg rithms In this section we will show how to round the optimal solution of (P) denoted again by xˆ yˆ toa feasible solution to the OWMRproblem with cost at most 1.8 times the optimal cost. We shall first describe two different randomized rounding procedures that we call andom shift with etaile two-sided push and andom shift with etaile one-sided push. Our rounding procedures run in two phases. In the first phase we determine the warehouse orders using a simple mechanism that we call andom shift. In the second phase we use the output of the first rounding phase to determine the orders of each retailer. This phase is done separately for each retailer. We shall show that the expected cost of each one of the algorithms is guaranteed to be at most twice the cost of an optimal policy for the OWMRproblem. In the worst- case analysis we shall bound each part of the cost i.e. the warehouse ordering cost the retailer ordering cost and the holding cost using the respective part of the cost incurred by the optimal fractional solution xˆ yˆ . Moreover we show that the algorithm with the cheapest expected cost among the two is guaranteed to have expected cost at most 1.8 times the optimal cost of the OWMRproblem. Finally we describe how to derandomize the algorithms and get a deterministic approximation algorithm with a worst-case performance guarantee of 1.8. That is for each instance of the problem the algorithm produces a solution that is guaranteed to be at most 1.8 times the cost of an optimal policy. 4.1. The Rand m Shift Pr cedure We first describe the andom shift procedure that is used in the first phase of the algorithms in which we decide in what periods to place warehouse orders. This simple randomized procedure is based on the values yˆ0 yˆ0 1 T . For the description of the random shift procedure T consider the interval 0 r=1 yˆ r 0 which corresponds to the total weight of open fractional warehouse orders in the optimal fractional solution xˆ yˆ . Each period m = 1  T is then associated with the respec m−10 m 0 tive interval Y 0 = yˆ r=1 yˆ which is of mr=1 rr length yˆ m 0 . In particular some periods can correspond to empty intervals of length 0 (if yˆ m 0 = 0). The input for this procedure is a step pa amete c ∈ 0 1 . Given c choose a shift pa amete 0 uniformly at random from 0 c . Let W be the smallest integer multiple of c Figure A Random Shift by 0 T yˆ0 Σ r r = 000 0 yˆ yˆ2 yˆ3 yˆ T ( ](]( ] ( ] α0 α0 α0 α0 0 c 2c 3c (W– )c Wc Notes. Each i terval correspo ds to some period r of le gth of yˆ r 0. The warehouse shift poi ts (black bullets) are ge erated by shifti g the poi ts 0  2 W −1 to right by 0. A warehouse order is placed i period r , if there is at least o e shift poi t withi its correspo di g i terval (e.g.,periods 1 a d 3 i the picture). T that is greater than y0. Specifically W is the r=1 ˆ r upper ceiling of the total accumulated weight of fractional warehouse orders in the optimal LP solution T xˆ yˆ scaled by 1/c; that is W = 1/c r=1 yˆ r 0 . Note T that the interval 0 r=1 yˆ r 0 is contained in the interval 0 cW . Within the interval 0 cW focus on the sequence of points 0 c  cW −1 . The shift parameter 0 induces a sequence of what we call wa ehouse shift points. Specifically the set of warehouse shift points is defined as 0 cw w = 0  W − 1 . This set is constructed through a shift of random length 0 to the right of the points 0 c  cW − 1 . Thus there are W shift points that are all located within the interval 0 cW . Observe that the sequence of warehouse shift points is a priori random and is realized with the shift parameter 0 (see Figure 1). The warehouse shift points determine the periods in which warehouse orders are placed. For each period m = 1  T we place a warehouse order in that period if there is at least one shift point within the interval Ym 0 that is associated with m. That is we place a warehouse order in period m if for some integer 0 ≤ w ≤ W − 1 there exists a warehouse shift point 0 cw that falls within the interval Yr 0. Next we bound the expected warehouse ordering cost incurred by the random shift procedure. emma 2. Con ider the random hift procedure decribed above with input length parameter c ∈ 01 . Then, the total expected warehou e ordering co t of the random hift procedure, denoted by 0 i at mo t 1/c time the total warehou e ordering co t in the optimal LP olution. T 0K0 That i , 0 ≤ 1/c y . r=1 ˆ rr For each w = 0  W −1 the interval cw cw 1 generates at most one warehouse order. Moreover in each interval cw cw 1 there is exactly one warehouse shift point that is uniformly distributed over the interval. Thus the expected cost of the warehouse order generated by the interval cw cw 1 T isatmost 1/c m=1 ·Ym 0 ∩ cw cw 1 ·Km 0 . It follows y0axis Levi et al.: A Constant App oximation Algo ithm fo the One-Wa ehouse Multi etaile P oblem Management Science 54(4) pp. 763–776 © 2008 INFORMS Copyri ht: INFORM holds copyright to this Articl s in Advanc version, which is made available to institutional subscribers. Thefile may not be posted on any other website, including the author’s site. Please send any questions regarding this policy to permissions@informs.org. that the overall expected warehouse ordering cost is at most W−1 T 1 ·Y0 ∩ cw cw 1 ·K0 mm c w=0 m=1 TW−1 T 1 1 0= K0 ·Y0 ∩ cw cw 1 ·= yˆ K0 mm mm cc m=1 w=0 m=1 where the last equality follows from the fact that each interval Ym 0 is partitioned by the intervals cw cw 1 . The proof of the lemma then follows. Let W = r1 0) then yˆ≥1. r=1 r Moreover by the properties of the random shift procedure described above it is straightforward to verify that there will be at least one warehouse order placed in the interval 1  i.e. r1 ∈ 1  . This implies that each positive demand point can be satisfied by at least one warehouse order that is placed earlier in time. Once we decide upon the warehouse orders then the OWMRproblem decomposes into N single-location single-item lot-sizing problems. These problems can be solved optimally using dynamic programming (see for example Wagner and Whitin 1958 Federgruen and Tzur 1991) to achieve the minimum overall retailer ordering cost and holding cost under the assumption that warehouse orders are placed at r1 m . The reason that we add retailer orders by pushing tentative retailer orders both earlier and later in time will be made clear in the following discussion. Intuitively we place additional retailer orders to guarantee that the holding costs incurred by each demand point i are not too high compared to the holding costs this demand point incurs in the fractional optimal solution xˆ yˆ . (This property of the algorithm will be used in the proof of Lemma 4.) Let i be the set of permanent retailer-i orders placed by Algorithm 1. As we have already observed there is a warehouse order placed prior to the earliest period with a positive demand point. We claim that the sets W and i (for i =1  N ) induce a feasible solution to the OWMRproblem. That is for each demand point i the solution produced by Algorithm 1 has at least one pair of warehouse-retailer orders rs that can serve i i.e. r ∈ W s ∈ i and r ≤s ≤ . In particular each demand point i is satisfied by the cheapest pair of orders rs such that r ∈ W and s ∈ i. The proof of this claim is discussed in Lemma 4 in which we show that not only does such a pair of warehouse-retailer orders exist but that the holding costs incurred by i under Algorithm 1 are bounded. From Lemma 2 (for c = 1) it follows that the total expected warehouse ordering cost of Algorithm T 0K0 1 is bounded by 1 yˆ . Next we bound the r= rr total expected retailer ordering cost which is denoted by I . The proof is identical to the proof of Lemma 2. emma 3. The total expected retailer ordering co t of Algorithm 1 i at mo t twice the total retailer ordering co t in xˆ yˆ , the optimal olution of the LP. That i , N T iKi I ≤21 yˆ . i=1 s= s Finally we wish to bound the total expected holding costs incurred by Algorithm 1 which is denoted by . Each demand point i is considered separately (for i = 1  N and = 1  T ) and its expected holding cost is bounded using the holding cost that this demand point incurs in the optimal LP solution xˆ yˆ . In particular focus on some demand point i and let Hi = H be the random holding cost that Algorithm 1 incurs in satisfying this demand point. (Because the following discussion is focused on a fixed demand point we simplify the notation and omit the superscript i whenever possible.) We wish to bound EH the expectation of H. Se vice Points. Consider demand point i and i let = be the set of all pairs of warehouse and retailer-i orders that fractionally serve i in the optimal LP solution xˆ yˆ . Specifically let = rs xˆi > 0 . Let L =· · and without loss of mm rs mm generality assume that = rmsm m = 1  L ≤ hi where hi ≤ ··· ≤ hi . That is the order r1 s1 r2 s2 rL sL pairs r1 s1 rL sL are sorted in an increasing order according to the per-unit holding costs that they incur. We call these L pairs of warehouse-retailer orders the se vice points of i . However because the solution xˆ yˆ is assumed to have the Monge Property we conclude that rs ≤ rs i.e. r ≤r mmmm mm and sm ≤sm for each 1 ≤m c. In particular we have already seen that r ≤ ru u and s ≤ s . mmc mmc Moreover we have already seen that if i is served by a pair of warehouse-retailer orders rs such that r ≥ rm and s ≥ sm then the holding cost it incurs is at most Hm. Thus we focus on this event and show that the probability that it occurs is at least m xi − c u=1 ˆ rs uu max 0 1 − c First consider the case in which i is a J-retailer. Focus on the event in which there is a warehouse order within the interval rmc  and a tentative retailer-i order within the interval ss . Because m mc sm c = rm c and Algorithm 2 aims to shift tentative retailer orders later in time it follows that indeed i will be served by a pair of orders rs such that r ≥ rm and s ≥ sm. It is now sufficient to lower bound the probability of the latter event. However because yˆ0 ≥ c there is a ware r∈ r  r house order placed within mc the time interval rmc  with probability one. Moreover we claim that the probability of having a tentative retailer-i order within the time interval ss is at least 1/ 1−c · m mc m xi − c . Because warehouse orders are deter u=1 ˆ rs uu mined independently of tentative retailer orders the proof of this case will follow. This can be seen as follows: m mmc −1 i i i xˆ= xˆ− xˆ rsrs rs uuuu uu u=mc u=1 u=1 m ≥ xˆi − c rs uu u=1 However constraint (2) implies that the cumulative weight of retailer-i fractional orders over the mi time interval ss i.e. yˆ is at least mmc u=mc su m xi − c from which the claim follows. (Recall u=1 ˆ rs that the uu step parameter in second phase of Algorithm 2 is 1 − c.) Next consider the case in which i is a W-retailer m and let = xˆi − c> 0. Focus on the event in u=1 rs uu which there is a warehouse order within the interval rr and a retailer-i order within s . mm m Because rm ≤ sm it follows that indeed i will be served by a pair of orders rs such that r ≥ rm and s ≥ sm. Using similar arguments we conclude that there is a retailer order placed within the time interval sm  with probability at least -/ 1 − c and that there is a warehouse order placed within the time interval rm rm with probability 1. Moreover the above two events are again independent events. Lemma 7 implies that i is served by a pair of warehouse-retailer orders rs such that r ≥ rL and s ≥ sL with probability one. This implies that the solution induced by the sets W and i is feasible. In particular inequality (6) is valid. (Observe that inequality (6) does not depend on Algorithm 1 but only on the fact that with probability one i is served by a pair of warehouse-retailer orders rs such that r ≥ rL and s ≥ sL.) Similar to the analysis of Algorithm 1 the upper bound obtained by inequality (6) is maintained if for each m = 1  L − 1 one replaces Pr H ≤ Hm by a respective lower bound. Using the lower bounds obtained in Lemma 7 we get that 1 L EH ≤ Hxˆi uu 1 − c urs u=mc L mc i 1 m=1 xˆ− c i mm ≤ xˆ H H rs rsu mc uu 1 − c 1 − c u=mc 1 1 L ≤ xˆi H uu 1 − cu=1 rs u We have obtained the following lemma. emma 8. Let denote the overall expected holding co t incurred by Algorithm 2 with a tep parameter c ∈ 0 05 . Then i at mo t 1/ 1 − c time the holding co t incurred by the optimal LP olution xˆ yˆ . That i , N T i Hi ≤ 1/ 1 − cxˆ . i=1 =1 r sr≤s≤ rs rs Lemmas 6 and 8 imply the following theorem. Theorem 2. The overall expected co t 0 I incurred by Algorithm 2 with a tep parameter c ∈ 0 05 i at mo t T NT NT 1 1 1 0K0 iKi i Hi yˆ yˆ xˆ rr s rsrs c 1 − c 1 − c r=1 i=1 s=1 i=1 =1 r sr≤s≤ It is readily verified that for c = 0 5 Algorithm 2 is a randomized 2-approximation for the OWMR problem. Management Science 54(4) pp. 763–776 © 2008 INFORMS 4.4. C mbining Alg rithms 1 and 2 Next we use Algorithm 1 and Algorithm 2 together. Specifically we shall show that taking the algorithm with the minimum expected cost among Algorithms 1 and 2 yields an improved expected worst-case guarantee of 1.8. We shall achieve this by choosing the step parameter of Algorithm 2 to be c = 1/3. Using the fact that min ab ≤ 0a 1 − 0b for each 0 ≤ 0 ≤ 1 we apply Theorems 1 and 2 (with c = 1/3) and take 0 = 3/5 to conclude that the solution with the smaller expected cost has expected value of at most T NT NT 0 i i Hi 18 yˆ K0 yˆ Ki xˆ rr s rsrs r=1 i=1 s=1 i=1 =1 r sr≤s≤ = 18op LP ≤ 18op Theorem 3. There exi t a randomized 1.8-approximation algorithm for the OWMR problem and it pecial ca e the JRP. Finally we describe how to derandomize the algorithms and get deterministic approximation algorithms with the same guarantee. We have already mentioned that once the warehouse orders are determined the problem decomposes to N single-retailer subproblems that can be solved to optimality via dynamic programming. Thus the expected cost of the solutions obtained by dynamic programming is at most the expected cost of Algorithms 1 and 2. It is now enough to show how to derandomize the first phase of the algorithms. However it is readily verified that in the random shift procedure described above there is only a polynomial number of values of 0 that yield distinct sets of warehouse orders. Specifically there are O T/c such points where c is again the step parameter being chosen. (Observe that we can restrict attention only to sequences of shift points in which one of them is at the right edge of an interval Ym 0 or cw cw 1 . Thus the number of different sequences of shift points to be considered is bounded by T/C .) It is readily verified that these values can be easily enumerated. (For the analysis we have considered the values c = 1 and c = 31.) Specifically the cost of the solution obtained by taking the best (cheapest) choice of warehouse orders is at most the expected cost over all choices. Theorem 4. There exi t a determini tic 1.8-approximation algorithm for the OWMR problem and it pecial ca e the JRP. 5. C nclusi ns In this paper we have demonstrated how strong LP relaxations can be used to construct provably near-optimal solutions for a class of classical deterministic inventory models. We have focused on the classical model known as the one-warehouse multiretailer problem and designed the first constant factor approximation algorithms for several variants of this model. This is yet another example of the potential of LP-based approximation methods as a tool to “attack” inventory problems. We find that this direction is important both theoretically and practically. From the practical aspect we point out that in many real-life cases these inventory problems are solved as integer programs. This emphasizes the importance of techniques that enable us to efficiently round fractional solutions to good feasible integer solutions as a tool for enhancing the computational procedures for solving these IPs. We believe that it would be interesting to test the typical quality of the solutions that our algorithms generate on different inputs and compare them to other known heuristics. A very interesting theoretical open question is related to the approximability of the OWMRproblem. The problem is proven to be NP-hard because the special case of the JRP is NP-hard (Arkin et al. 1989). However we know of no approximability hardness result and one cannot even exclude the existence of a polynomial-time approximation scheme (i.e. one might be able to design a 1-approximation algorithm for any 1> 1). In addition the analysis presented in this paper is not tight that is we do not have bad examples on which the performance of the proposed algorithms matches the upper bound of 1.8. Finally it seems that LP-based approximation techniques can be used to provide high-quality solutions to a class of classical inventory models. It is most interesting to see whether these techniques can be applied to more complicated inventory models. Ackn wledgments The authors thank the associate editor and the two anonymous referees for their constructive comments which significantly improved the exposition of this paper. Preliminary presentations of part of the results in this paper were given in Levi et al. (2005) and Levi and Sviridenko (2006). This research was partially conducted while the first author was a PhD student in the ORIE department at Cornell University. Research was partially supported by a grant from Motorola and NSF Grants CCR-9912422 CCR-0430682 and DMS-0732175. The research of the second author was partially supported by a grant from Motorola and NSF Grants DMI-0075627 and DMI-0500263 and the Querétaro Campus of the Instituto Tecnológico y de Estudios Superiores de Monterrey. The research of the third author was partially supported by NSF Grants CCR-9912422 CCR-0430682 DMI-0500263 CCR-0635121 and DMS-0732196. Appendix. Transp rtati n C sts and Batch Capacities In this appendix we consider the OWMRproblem but with batch capacities and a correspondingly more complex Levi et al.: A Constant App oximation Algo ithm fo the One-Wa ehouse Multi etaile P oblem Management Science 54(4) pp. 763–776 © 2008 INFORMS Copyri ht: INFORM holds copyright to this Articl s in Advanc version, which is made available to institutional subscribers. Thefile may not be posted on any other website, including the author’s site. Please send any questions regarding this policy to permissions@informs.org. cost structure. Instead of ordering costs we consider transportation costs. Usually transportation is based on trucks with given capacities. We model this in the following way. For each warehouse-retailer i segment we consider trucks/batches each with capacity Ui and cost Ki (i = 1  N). In addition in the supplier-warehouse segment we consider trucks/batches each with capacity U0 and cost K0. Each order now consists of several complete batches say w (w ∈ Z ) that can provide a capacity of wUi units and incurs a cost of wKi (i = 0  N). The batch-based ordering structure is sometimes called ordering with soft capacities. We first modify the linear program (P) presented in §3 to capture the new model. For each period r = 1  T N we add the constraint i=1 ≥rs∈ r  xrsi di ≤ yr 0U0. For each i = 1  N and s = 1  T we add the constraint i iUi i 0 x di ≤ y . Observe that the variables y and y ≥sr≤srss sr can be larger than one. Now consider the corresponding dual program: NT maximize b i (D1) i=1 =1 ≤ Hi i subject to bi li z rs s r 5isdi 6rdi i = 1  N = 1  T s = 1   r = 1  s (9) T ls i 5isUi ≤ Ki i= 1  Ns =1  T (10) =s NT iU0 ≤ K0 zr 6r r = 1  T (11) i=1 =r li i z6 ≥ 0 s r 5is r i = 1  N = 1  T s = 1   r = 1   (12) Note that weak duality implies that each feasible solution blz56 for the above dual program (D1) provides a lower bound on the optimal cost of the primal LP; thus it provides a lower bound on the optimal cost of the OWMR problem with batch capacities. Suppose now that we set the value of each dual variable 5is to be equal to Ki/2Ui and of each dual variable 6r to be equal to K0/2U0 and consider the induced modified LP. It is straightforward to verify that the modified LP is the dual program of the following primal = hi LP (recall that Hi ): rs rsdi minimize NT NT 1 1 Ki K0 Xi hi Y iKi (P2) s rsdi rs 22 Ui U0 i=0 s=1 i=1 =1 r sr≤s≤ subject to Xi rs = 1 r sr≤s≤ i = 1  N = 1  T di > 0 (13) Xi ≤ Yi rs s rr≤s i = 1  N = 1  Ts = 1   (14) Xi ≤ Y 0 rs r sr≤s≤ i = 1  N = 1  Tr = 1   (15) Xi rs Yri ≥ 0 i = 0  Ns = 1  T r = 1  s = s T (16) However (P2) is an LP relaxation of an uncapacitated OWMRproblem where the ordering and the holding-cost parameters are modified accordingly. Thus the modified dual program has an optimal solution that we denote by N T ˆ lˆ bˆi bzˆ . In particular by strong duality is equal i=1 =1 to the optimal value of (P2) that we denote by op LP2.Itis also clear that the modified holding-cost parameters hi rs 1 Ki/Ui K0/U0 still obey all of the assumptions discussed 2 in §2. Hence we can use the algorithms described in §4 to find an integer solution to this uncapacitated OWMRproblem denoted by XY with the following property: NT NT 1 1 Ki K0 Xi hi Y iKi s rsdi rs 22 Ui U0 i=0 s=1 i=1 =1 r sr≤s≤ TT bˆi ≤ 18op LP2 = 18 i=1 =1 Next we define a feasible solution to the original OWMR problem with batch capacities. For each i and r ≤ s i Xi 0 we set x¯= . For each r = 1  T we set y¯= rsrs r N Xi 1/U0 . For each i = 1  N and i=1 ≥rs∈ r rs i Xi s ≥sr≤s rs s = 1  T we set y¯= 1/Ui . It follows N 0 Xi that y¯≤ Yr 0 1/U0 ≥rs∈ r (for each r = ri=1 rs i Xi 1  T ) and y¯≤ Yi 1/U i (for each i = ss ≥sr≤s rs 1  N and s = 1  T ). This implies that NT NT iKi i Hi y¯ x¯ s rs rs i=0 s=1 i=1 =1 r sr≤s≤ NT NT 1 Xi Yi ≤ 2 Ki s rsdi 2 i=0 s=1 i=1 =1 r sr≤s≤ 1 Ki K0 hi · rs UiU0 2 TT bˆi ≤ 36 i=1 =1 T T bˆi Finally we claim that provides a lower bound i=1 =1 on the optimal cost of the original OWMRproblem with batch capacities. It is sufficient to show that (D1) has a feasi T T bˆi ble solution with objective value . However by i=1 =1 setting 5ˆ is = Ki/2Ui and 6ˆ r = K0/2U0 the solution bˆ lˆ zˆ is ˆ lˆ ˆˆ mapped to a feasible solution bzˆ 56 to (D1) with the same objective value. We now conclude that the following theorem holds: Theorem 5. The algorithm provide a 3.6-approximation algorithm for the OWMR problem and the JRP with tran portation co t and batche . Finally we observe that by using dynamic programming the single-location lot-sizing problem can be solved optimally for any cost parameters hs . In turn this yields a 2-approximation algorithm for the single-location lot-sizing Management Science 54(4) pp. 763–776 © 2008 INFORMS problem with batches. Here we can allow a time-dependent ordering cost Ks and batch size Us (s = 1  T ).As a byproduct we also prove a lower bound of two on the integrality gap of the corresponding natural LP-relaxations. For the case where Us = U (uniform batch size) Pochet and Wolsey (1993) have shown that the problem can be solved optimally using dynamic programming (applied directly to the problem). Moreover they have observed a linear program for this problem with integrality property (i.e. an LP that describes the convex hall of the integer solutions). This LP has an exponential number of constraints but these constraints are separable. Theorem 6. For the ingle-location lot- izing problem with time-dependent batch ize there exi t a 2-approximation algorithm. Theorem 7. The facility location-in pired LP for the ingle- location lot- izing problem with time-dependent batch ize ha an integrality gap of at mo t two. References Arkin E. D. Joneja R. Roundy. 1989. Computational complexity of uncapacitated multi-echelon production planning problems. Ope . Res. Lett. 8 61–66. Bárány I. T. J. Van Roy L. A. Wolsey. 1984. Uncapacitated lot- sizing: The convex hull of solutions. Math. P og amming Stud. 22 32–43. Bertsimas D. C. Teo R. Vohra. 1999. On dependent randomized rounding algorithms. Ope . Res. Lett. 25 105–114. Chan L. M. A. A. Muriel Z.-J. M. Shen D. Simchi-Levi C.-P. Teo. 2000. Effective zero-inventory-ordering policies for the single- warehouse multiretailer problem with piecewise linear cost structures. Management Sci. 48 1446–1460. Federgruen A. M. Tzur. 1991. A simple forward algorithm to solve general dynamic lot sizing models with n periods in On log n or On time. Management Sci. 37 909–925. Federgruen A. M. Tzur. 1999. Time-partitioning heuristics: Application to one warehouse multi-item multi-retailer lot-sizing problems. Naval Res. Logist. 46 463–486. Feige U. 1998. A threshold of ln(n) for approximating set-cover. J. ACM 45 634–652. Jain K. V. V. Vazirani. 2001. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48 274–296. Jin Y. A. Muriel. 2005. Single-warehouse multi-retailer inventory systems with full truckload shipments. Working paper University of Massachusetts Amherst. Krarup J. O. Bilde. 1977. Plant location set covering and economic lot sizing: An O mn algorithm for structural problems. Nume ische Methoden bei Optimie ungsaufgaben 3 155–180. Levi R. M. Sviridenko. 2006. Improved approximation algorithm for the one-warehouse multi-retailer problem. J. Díaz K. Jansen J. D. P. Rolim U. Zwick eds. App oximation Randomization, and Combinato ial Optimization Algo ithms and Techniques. Springer-Verlag New York 188–199. Levi R. R. O. Roundy D. B. Shmoys. 2004. Primal-dual algorithms for deterministic inventory problems. P oc. 36th Annual ACM Sympos. Theo y Comput. ACM New York 353–362. Levi R. R. O. Roundy D. B. Shmoys. 2006. Primal-dual algorithms for deterministic inventory problems. Math. Ope . Res. 31 267–284. Levi R. D. B. Shmoys R. O. Roundy. 2005. A constant approximation algorithm for the one-warehouse multi-retailer problem. P oc. 15th Annual SIAM-ACM Sympos. Disc ete Algo ithms SIAM Philadelphia 365–374. Pochet Y. L. A. Wolsey. 1993. Lot-sizing with constant batches: Formulation and valid inequalities. Math. Ope . Res. 18 767–785. Schwarz L. B. 1973. A simple continuous review deterministic one- warehouse N -retailer inventory problem. Management Sci. 19 555–566. Shen Z.-J. D. Simchi-Levi C.-P. Teo. 2002. Approximation algorithms for the single-warehouse multi-retailer problem with piecewise linear cost structures. http://citeseer.ist.psu.edu/ 439759.html. Shen Z.-J. D. Simchi-Levi C.-P. Teo J. Zhang. 2007. Approximate solutions to logistical planning problems in one-warehouse multi-retailer systems. Working paper University of California Berkeley. Shmoys D. B. 2004. The design and analysis of approximation algorithms: Facility location as a case study. S. Hosten J. Lee R. Thomas eds. T ends in Optimization. AMS P occedings of Symposia in Applied Mathematics. AMS Providence RI 85–98. Shmoys D. B. E. Tardos K. I. Aardal. 1997. Approximation algorithms for facility location problems. P oc. 29th Annual ACM Sympos. Theo y Comput. ACM New York 265–274. Wagner H. M. T. M. Whitin. 1958. Dynamic version of the economic lot sizing model. Management Sci. 5 89–96.