Local cuts and two-period convex hull closures for big-bucket lot-sizing problems

Kerem Akartunali, Ioannis Fragkos, Andrew J. Miller, Tao Wu

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)
28 Downloads (Pure)


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. 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 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.
Original languageEnglish
Pages (from-to)766-780
Number of pages15
JournalINFORMS Journal on Computing
Issue number4
Early online date12 Oct 2016
Publication statusPublished - 31 Oct 2016


  • lot sizing
  • integer programming
  • local cuts
  • convex hull closure
  • column generation


Dive into the research topics of 'Local cuts and two-period convex hull closures for big-bucket lot-sizing problems'. Together they form a unique fingerprint.

Cite this