Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems

Despite the significant attention they have drawn, big bucket lot-sizing problems remain difficult to solve computationally. Previous research indicates that the embedded multi-period, multi-item, capacitated submodels are also challenging to analyze (from a theoretical) and solve (from a computational) perspective. We introduce a minimal submodel that captures the complexity of capacitated multi-period, multi-item lot-sizing structures, namely a two-period, multi-item, capacitated polyhedron with single and two-period (l,S) inequalities and relaxed demand constraints. We propose a methodology that can approximate the convex hulls of all multi-item, multi-period relaxations by generating valid inequalities, guaranteed to be violated from the original problem's LP relaxation. To generate such inequalities, we separate two-period projections of fractional LP solutions from the convex hulls of the two-period closure we study. The convex hull representation of the two-period closure is generated dynamically using column generation. Contrary to regular column generation, our method is an outer approximation, and therefore can be used efficiently in a regular branch-and-bound procedure. We present computational results that illustrate how these two-period models could be effective in solving complicated problems.

Registration to the secretary's office of the econometric institute, eb-secr@ese.eur.nl, is required for availability of lunch.