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

17 Citations (Scopus)
26 Downloads (Pure)

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

Keywords

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

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.

  • Projects

  • Research Output

    • 17 Citations
    • 1 Paper

    A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems

    Fragkos, I. & Akartunali, K., Aug 2014, p. 41-45. 5 p.

    Research output: Contribution to conferencePaper

    Open Access
    File
  • Activities

    • 1 Key-note speaker and plenary lectures at conferences
    • 1 Invited talk

    Production Planning: From Decompositions to Robust Reformulations

    Kerem Akartunali (Speaker)

    9 Jan 2018

    Activity: Talk or presentation typesInvited talk

    18th ONPCE (National Workshop on Problems of Cutting and Packing, Planning and Production Scheduling)

    Kerem Akartunali (Participant)

    7 Nov 2017

    Activity: Participating in or organising an event typesKey-note speaker and plenary lectures at conferences

    Cite this