Multi-item lot-sizing with joint set-up costs (Q1013968)

A multi-item lot-sizing problem is considered, in which a setup cost is incurred for each batch that may contain at most \(C\) various items. Under the assumption that the storage costs are non-negative, i.e., are non-speculative or Wagner-Whitin costs, and additionally satisfy the dominance condition, the problem is formulated as a compact linear program with \(O(mT^2)\) constraints, where \(m\) is the number of items and \(T\) is the number of periods. The problem therefore is polynomially solvable. The backlogging version of the problem is also considered and formulated as a mixed integer program. In the uncapacitated case a specially constructed relaxation is shown to solve the problem. The results of computational experiments that use standard MIP solvers are reported.