An application of Lagrangean decomposition to the capacitated multi-item lot sizing problem

In this paper the authors present a Lagrangean decomposition technique for solving the capacitated multi-item lot sizing problem (CMLSP). The approach decomposes the problem into a transportation problem and N independent single-item uncapacitated lot sizing problems. The algorithm applies subgradient optimization to update the Lagrangean multipliers. Each iteration of the Lagrangean procedure generates two primal feasible solutions: one from the transportation subproblem, and the other from the network flow problem resulting from a primal partition produced by the solution to the N single-item problems. The Lagrangean algorithm proves to be quite effective and stable in producing good primal and dual solutions to the CMLSP.