Solving multi-item lot-sizing problems using strong cutting planes

The authors consider two classes of multi-item lot-sizing problems. The first is a class of single stage problems involving joint machine capacity constraints and/or start up costs, and the second is a class of multistage problems with general product structure. The problems are solved as mixed integer programs based on (i) an appropriate choice of the initial problem formulation and (ii) the addition of cuts which are generated automatically by a mathematical programming system (MPSARX). The present results extend and complement those of Karmarkar and Schrage, Afentakis and Gavish, Eppen and Martin and Van Roy and Wolsey. A major advantage of this approach is its robustness or flexibility. By using just a matrix generator and a mathematical programming system with automatic cut generation routines, model variants can be formulated and solved without incurring the costs of adapting an algorithm.