Analysis of Lagrangian decomposition for the multi-item capacitated lot-sizing problem

The multi-item capacitated dynamic lot-sizing problem consists of determining the quantity and the timing of production for several products in a finite number of periods so as to satisfy a known demand in each period and minimize the sum of the set-up, production and inventory costs without incurring backlogs. A production capacity is imposed in each period. Lagrangian decomposition is applied to two formulations of the problem. Using standard subsets of constraints, it is shown that Lagrangian decomposition yields only five genuinely different relaxations. Their values and computational complexities are compared. As the number of items grows, the five relaxations merge into two families that contrast sharply by their values, their computing times and the quality of the feasible solutions that they generate.