Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems
Kerem Akartunali (kerem.akartunalistrath.ac.uk)
Abstract: 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.
Keywords: Lot-Sizing; Integer Programming; Local Cuts; Convex Hull Closure; Quadratic Programming; Column Generation.
Category 1: Applications -- OR and Management Sciences
Category 2: Integer Programming
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
Entry Submitted: 07/03/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|