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 journalArticle

13 Citations (Scopus)

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.
LanguageEnglish
Pages766-780
Number of pages15
JournalINFORMS Journal on Computing
Volume28
Issue number4
Early online date12 Oct 2016
DOIs
Publication statusPublished - 31 Oct 2016

Fingerprint

Convex hull
Lot sizing
Closure
Column generation
Valid inequalities
Branch-and-bound
Problem solving
Methodology
Approximation
Single machine

Keywords

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

Cite this

Akartunali, Kerem ; Fragkos, Ioannis ; Miller, Andrew J. ; Wu, Tao. / Local cuts and two-period convex hull closures for big-bucket lot-sizing problems. In: INFORMS Journal on Computing. 2016 ; Vol. 28, No. 4. pp. 766-780.
@article{2bfc31474f7d473b827832ecd366e55e,
title = "Local cuts and two-period convex hull closures for big-bucket lot-sizing problems",
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.",
keywords = "lot sizing, integer programming, local cuts, convex hull closure, column generation",
author = "Kerem Akartunali and Ioannis Fragkos and Miller, {Andrew J.} and Tao Wu",
year = "2016",
month = "10",
day = "31",
doi = "10.1287/ijoc.2016.0712",
language = "English",
volume = "28",
pages = "766--780",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
number = "4",

}

Local cuts and two-period convex hull closures for big-bucket lot-sizing problems. / Akartunali, Kerem; Fragkos, Ioannis; Miller, Andrew J.; Wu, Tao.

In: INFORMS Journal on Computing, Vol. 28, No. 4, 31.10.2016, p. 766-780.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Akartunali, Kerem

AU - Fragkos, Ioannis

AU - Miller, Andrew J.

AU - Wu, Tao

PY - 2016/10/31

Y1 - 2016/10/31

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

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

KW - lot sizing

KW - integer programming

KW - local cuts

KW - convex hull closure

KW - column generation

UR - http://pubsonline.informs.org/journal/ijoc

U2 - 10.1287/ijoc.2016.0712

DO - 10.1287/ijoc.2016.0712

M3 - Article

VL - 28

SP - 766

EP - 780

JO - INFORMS Journal on Computing

T2 - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -