A novel mixed integer programming formulation and progressively stochastic search for capacitated lot sizing

The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods. To advance techniques of solving this class of problems, this paper proposes a new mixed integer programming formulation. Theoretical proofs and computational tests are provided to show that this formulation is able to provide better linear programming relaxation lower bounds than a previously-proposed strong mixed integer programming formulation. Based on the new strong formulation, a progressively stochastic search approach is proposed for solving the problem. Computational results showed that the approach generates high quality solutions, especially for problems of large sizes.