Optimization Online


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

Kerem Akartunali (kerem.akartunali***at***strath.ac.uk)
Ioannis Fragkos (i.fragkos***at***ucl.ac.uk)
Andrew J. Miller (foresomenteneikona***at***gmail.com)
Tao Wu (twu1***at***dow.com)

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
Entry Accepted: 07/03/2014
Entry Last Modified: 10/13/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society