Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities
Authors:
- 1 May 2008
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 33 (2) , 461-474
Abstract
We study the classical capacitated multi-item lot-sizing problem with hard capacities. There are N items, each of which has a specified sequence of demands over a finite planning horizon of T discrete periods; the demands are known in advance but can vary from period to period. All demands must be satisfied on time. Each order incurs a time-dependent fixed ordering cost regardless of the combination of items or the number of units ordered, but the total number of units ordered cannot exceed a given capacity C. On the other hand, carrying inventory from period to period incurs holding costs. The goal is to find a feasible solution with minimum overall ordering and holding costs. We show that the problem is strongly NP-hard, and then propose a novel facility location type LP relaxation that is based on an exponentially large subset of the well-known flow-cover inequalities; the proposed LP can be solved to optimality in polynomial time via an efficient separation procedure for this subset of inequalities. Moreover, the optimal solution of the LP can be rounded to a feasible integer solution with cost that is at most twice the optimal cost; this provides a 2-approximation algorithm which is the first constant approximation algorithm for the problem. We also describe an interesting on-the-fly variant of the algorithm that does not require solving the LP a priori with all the flow-cover inequalities. As a by-product we obtain the first theoretical proof regarding the strength of flow-cover inequalities in capacitated inventory models.Keywords
This publication has 16 references indexed in Scilit:
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costsACM Transactions on Algorithms, 2008
- Primal-Dual Schema for Capacitated Covering Problems2008
- A Constant Approximation Algorithm for the One-Warehouse Multiretailer ProblemManagement Science, 2008
- Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing ProblemsOperations Research, 2007
- Primal-Dual Algorithms for Deterministic Inventory ProblemsMathematics of Operations Research, 2006
- Shipping Multiple Items by Capacitated Vehicles: An Optimal Dynamic Programming ApproachTransportation Science, 2005
- On capacitated network design cut?set polyhedraMathematical Programming, 2002
- Capacitated facility location: Separation algorithms and computational experienceMathematical Programming, 1998
- The convex hull of two core capacitated network design problemsMathematical Programming, 1993
- Valid inequalities and facets of the capacitated plant location problemMathematical Programming, 1989