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 journalArticleAcademicpeer-review

25 Citations (Scopus)
14 Downloads (Pure)

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

Original languageEnglish
Pages (from-to)766-780
Number of pages15
JournalINFORMS Journal on Computing
Volume28
Issue number4
DOIs
Publication statusPublished - 1 Sept 2016

Bibliographical note

Funding Information:
The authors thank Laurence Wolsey and Stephen Robinson for earlier discussions that led to significant improvements of the paper. The research of the first author was supported in part by the EPSRC [Grant EP/L000911/1] entitled "Multi-Item Production Planning: Theory, Computation and Practice," and the research of the third author was supported in part by the NSF [Grants CMMI-0323299 and CMMI-0521953].

Publisher Copyright:
© 2016 INFORMS.

Research programs

  • RSM LIS

Fingerprint

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