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 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.