Groupe d’études et de recherche en analyse des décisions

Primal and dual bounds for the capacity constrained lot size problem with setup times

Silvio Alexandre de Araujo Acadia University, Canada

The aim of this paper is to design a fast heuristic for the capacity constrained lot size problems with setup times (CLST) that provides good solutions and a strong lower bound to assess their quality. Per-period Dantzig-Wolfe decompositions of strong reformulations of the CLST are proposed. The main advantage of these decompositions is that they provide lower bounds which are stronger than those obtained by most other approaches. We propose a novel fast subgradient-based hybrid scheme that combines Lagrange relaxation and column generation. This scheme outperforms simplex-based column generation, Lagrange relaxation and subgradient-based column generation (in which the restricted master programs are solved with subgradient optimization). The new hybrid scheme is embedded in a branch-and-price framework, designed specifically to obtain good feasible solutions fast. To achieve this, we recover a primal solution of the restricted master using the volume algorithm, and branch on the resulting fractional setup variables. Moreover, we integrate in customized fashion recent MIP-based heuristic approaches. Computational experiments show that the branch-and-price heuristic performs very well against other competitive approaches.