A Lagrangian relaxation-based method and models evaluation for multi-level lot sizing problems with backorders

The capacitated multi-level lot sizing problem with backorders has received a great deal of attention in extant literature on operations and optimization. The facility location model and the classical inventory and lot sizing model with (ℓℓ, S) cuts have been proposed to formulate this problem. However, their comparative effectiveness has not yet been explored and is not known. In this paper, we demonstrate that on linear programming relaxation, the facility location formulation yields tighter lower bounds than classical inventory and lot sizing model. It further shows that the facility location formulation is computationally advantageous for deriving both lower and upper bounds. The results are expected to provide guidelines for choosing an effective formulation during the development of solution procedures. We also propose a Lagrangian relaxation-based heuristic along with computational results that indicate its competitiveness with other heuristics and a prominent commercial solver, Cplex 11.2.