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

Akartunali, Kerem and Fragkos, Ioannis and Miller, Andrew J. and Wu, Tao (2016) Local cuts and two-period convex hull closures for big-bucket lot-sizing problems. INFORMS Journal on Computing, 28 (4). pp. 766-780. ISSN 1526-5528 (https://doi.org/10.1287/ijoc.2016.0712)

[thumbnail of Akartunah-etal-INFORMS-JOC-2016-Local-cuts-and-two-period-convex-hull-closures-for-big-bucket]
Preview
 Text. Filename: Akartunah_etal_INFORMS_JOC_2016_Local_cuts_and_two_period_convex_hull_closures_for_big_bucket.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (315kB)| Preview

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

CORE (COnnecting REpositories)