Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities

• 成果类型: Article
• 署名作者: Levi, Retsef; Lodi, Andrea; Sviridenko, Maxim
• 署名单位: Massachusetts Institute of Technology (MIT); University of Bologna; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1070.0305
• 发表日期: 2008
• 页码: 461-474
• 关键词: valid inequalities; Facility Location

摘要

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.