Despite the significant attention they have drawn, big bucket lot-sizing problems remain notoriously difficult to solve. Previous work of Akartunali and Miller (2012) presented results (computational and theoretical) indicating that what makes these problems difficult are the embedded single-machine, single-level, multi-period submodels. We therefore consider the simplest such submodel, a multi-item, two-period capacitated relaxation that includes a subset of (l,S) inequalities and relaxed demand constraints. We propose a methodology that can approximate the intersection of the convex hulls of all such possible submodels by generating violated valid inequalities. 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.
Citation
Kerem Akartunalı, Ioannis Fragkos, Andrew J. Miller, Tao Wu, Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems, INFORMS Journal on Computing, Volume 28 Issue 4, Fall 2016, pp. 766-780. Available OPEN ACCESS at: http://pubsonline.informs.org/doi/full/10.1287/ijoc.2016.0712