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

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

0.00 Avg rating0 Votes
Article ID: iaor20164568
Volume: 28
Issue: 4
Start Page Number: 766
End Page Number: 780
Publication Date: Nov 2016
Journal: INFORMS Journal on Computing
Authors: , , ,
Keywords: programming: convex
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.

Reviews

Required fields are marked *. Your email address will not be published.