Lagrangian relaxation and bounded variable linear programs to solve a two level capacitated lot sizing problem

摘要

In this work, we attempt an NP-hard problem called multi item, multi period two level capacitated lot sizing problem with considerations of backorders and setup times. To be close to reality, the demand is considered to be dynamic. With the use of Lagrangian relaxation, the problem is reduced to a continuous knapsack problem which is then solved using bounded variable linear programs. Though the problem is solved close to optimality, the solution is further improved by the use of a branch and bound method in order to obtain a solution closer to optimal. As the procedure makes use of the most basic algebraic computations, it is competent to confront the best available commercial solvers in terms of computational times for large sized problems. The procedure is robust enough to be applicable to a variety of real life problems with a similar formulation structure.