Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities

摘要

We study the nonuniform capacitated multi-item lot-sizing problem. In this problem, there is a set of demands over a planning horizon of T discrete time periods, and all demands must be satisfied on time. We can place an order at the beginning of each period s, incurring an ordering cost K-s. In this order, we can order up to C-s units of products. On the other hand, carrying inventory from time to time incurs an inventory holding cost. The goal of the problem is to find a feasible solution that minimizes the sum of ordering and holding costs. Levi et al. [Levi R, Lodi A, Sviridenko M (2008) Approximation algorithms for the capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res. 33(2):461-474.] gave a two-approximation for the problem when the capacities C-s are the same. Extending the result to the case of nonuniform capacities requires new techniques as pointed out in the discussion section of their paper. In this paper, we solve the problem by giving a 10-approximation algorithm for the capacitated multi-item lot-sizing problem with general capacities. The constant approximation is achieved by adding an exponential number of new covering inequalities to the natural facility location-type linear programming (LP) relaxation for the problem. Along the way of our algorithm, we reduce the lot-sizing problem to two generalizations of the classic knapsack-covering problem. We give LP-based constant approximation algorithms for both generalizations via the iterative rounding technique.