Branch and price algorithms for production lot sizing

In this paper, we present two algorithms for the multi-item capacitated lot-sizing problem with setup times. In this problem we aim at finding a production plan for several items over a number of time periods that minimizes the production, inventory and setup costs and satisfies all demand requirements without exceeding capacity limits. Both of the algorithms are based on the application of the Dantzig–Wolfe principle to a classical model of Mixed Integer Programming. In one case, we apply item decomposition and in the other case we apply a period decomposition. In both cases the reformulated models are stronger than the original one. These reformulated models are solved by branch-and-price, which is a combination of column generation and branch-and-bound methods. We present computational results for a set of instances with different characteristics, to establish comparisons between the two decomposition models. These results are then compared with the classic Mixed Integer Programming formulation solved by the commercial solver Cplex 8.1.