Lagrangian Relaxation for the Capacitated Dynamic Lot Sizing Problem

In this paper, we consider the capacitated dynamic lot-sizing problem and assume that all conditions of Wagner-Whitin (1958) model apply except the capacity restriction. We give three different formulation of the problem. We relax the capacity constraint and initiate the Lagrangian procedure. At each Lagrangian iteration, we solved the uncapacitated lot-sizing problem by the Wagner-Whitin method that runs in O(n²) time. We compare the quality of bounds so obtained. In particular, we find that the Lagrangian procedure that modified the setup cost turned out to be inferior to the Lagrangian procedure that modified only the holding cost.