Andrea
Lodi
Title:
Approximation algorithms for the multi-item capacitated
lot-sizing problem via flow-cover inequalities
Abstract:
We study the classical multi-item capacitated lot-sizing
problem with
hard capacities. There are N items, each of which has specified
sequence of demands over a finite planning horizon of discrete T
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, being the
first constant approximation algorithm for the problem. We also
describe an interesting on-the-fly variant of the algorithm that does
not require to solve 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.