Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems
Kerem Akartunalı, Ioannis Fragkos, Andrew J. Miller, Tao Wu
INFORMS Journal on Computing · 2016 · Volume 28 · Issue 4
Abstract
Despite the significant attention they have drawn, big-bucket lot-sizing problems remain notoriously difficult to solve. Previous literature contained results (computational and theoretical) indicating that what makes these problems difficult are the embedded single-machine, single-level, multiperiod submodels. We therefore consider the simplest such submodel, a multi-item, two-period capacitated relaxation. We propose a methodology that can approximate the convex hulls of all such possible relaxations by generating violated valid inequalities. To generate such inequalities, we separate two-period projections of fractional linear programming 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 can therefore 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.
Keywords
lot-sizing, integer programming, local cuts, convex hull closure, quadratic programming, column generation
Enable JavaScript for citation tools and additional paper interactions.