Strong Formulations for Multi-Item Capacitated Lot Sizing

Multi-item capacitated lot-sizing problems are reformulated using a class of valid inequalities, which are facets for the single-item uncapacitated problem. Computational results using this reformulation are reported, and problems with up to 20 items and 13 periods have been solved to optimality using a commercial mixed integer code. We also show how the valid inequalities can easily be generated as part of a cutting plane algorithm, and suggest a further class of inequalities that is useful for single-item capacitated problems.