We present new lower bounds for the Capacitated Lot Sizing Problem with Set Up Times. We improve the lower bound obtained by the textbook Dantzig-Wolfe decomposition where the capacity constraints are the linking constraints. In our approach, Dantzig-Wolfe decomposition is applied to the network reformulation of the problem. The demand constraints are the linking constraints and the problem decomposes into subproblems per period containing the capacity and set up constraints. We propose a customized branch-and-bound algorithm for solving the subproblem based on its similarities with the Linear Multiple Choice Knapsack Problem. Further we present a Lagrange Relaxation algorithm for finding this lower bound. To the best of our knowledge, this is the first time that computational results are presented for this decomposition and a comparison of our lower bound to other lower bounds proposed in the literature indicates its high quality.

Dantzig-Wolfe decomposition, Lagrange relaxation, capacitated lot sizing, lower bounds
Optimization Techniques; Programming Models; Dynamic Analysis (jel C61), Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)
ERIM Report Series Research in Management
Erasmus Research Institute of Management

Degraeve, Z, & Jans, R.F. (2003). Improved Lower Bounds For The Capacitated Lot Sizing Problem With Set Up Times (No. ERS-2003-026-LIS). ERIM Report Series Research in Management. Retrieved from http://hdl.handle.net/1765/326