Group for Research in Decision Analysis

Decomposition Approaches for the Capacitated Lot Sizing Problem

Raf Jans Full Professor, Department of Logistics and Operations Management, HEC Montréal, Canada

We study two alternative Dantzig-Wolfe reformulations for the Capacitated Lot Sizing Problem with Set Up Times (CLST). In the textbook Dantzig-Wolfe decomposition for the CLST the capacity constraints are the complicating constraints and the problem is split up into single-item uncapacitated lot sizing problems. This reformulation has an important structural deficiency as imposing integrality constraints on the columns will not necessarily give the optimal IP solution. Only extreme point production plans which satisfy the Wagner-Whitin condition can be selected and it is well known that the optimal solution to a capacitated lot sizing problem will usually not have the Wagner-Whitin property. We propose the correct Dantzig-Wolfe decomposition reformulation separating the set up and production decisions. Column generation is speeded up by a combination of simplex and subgradient optimization for finding the dual prices. The implementation of a Branch-and-Price algorithm is discussed. Subsequently, we improve the lower bound obtained by the previous decomposition. In this new approach, Dantzig-Wolfe decomposition is applied to the network reformulation of the lot sizing problem. The demand constraints are now the linking constraints and the problem decomposes into subproblems per period which contain the capacity and set up constraints. A comparison is made with other lower bounds from the literature.