Comparing Dantzig–Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem

Abstract

In this article, we consider the multi-item capacitated lot sizing problem with setup times. Starting from an original mixed integer programming model, we apply the standard Dantzig–Wolfe decomposition (DWD) in two different ways: defining the subproblems by items and defining the subproblems by periods. A third decomposition is developed in which the subproblems of both types are integrated in the same model. The linear relaxation of this last approach, which we denote as multiple DWD, provides lower bounds (equal to or) better than the bounds obtained by the other decompositions, which in turn, provide lower bounds (equal to or) better than the ones given by the original model. For solving the three decomposition models, we implemented three branch-and-price algorithms. We describe their main aspects and report on their computational results in instances from the literature.

Keywords:

• production planning
• mixed integer programming
• branch-and-price and Dantzig–Wolfe decomposition

Acknowledgements

We thank the referees for their helpful comments and insightful suggestions.

This work was partially supported by the Portuguese Science and Technology Foundation (Project POSI/SRI/ 48873/2002) and by the Algoritmi Research Centre of the University of Minho.