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

Ioannis Fragkos, Kerem Akartunali

Research output: Contribution to conferencePaper

113 Downloads (Pure)

Abstract

We study the big-bucket capacitated lot sizing problem with setup times. We use the novel methodology of Akartunali et al. (2014) that exploits two-period relaxations of the formulation in order to generate inequalities that cut-off the optimal solution of the linear programming relaxation. Our approach applies column generation in an unconventional way, with the master problem being a distance minimizing formulation and the subproblems being combina-torial two-period relaxations of the original problem. We identify a lower bound of the dimensionality of the generated cuts and provide extensive computational experiments that show how the generated bounds compare with other state-of-
the-art approaches. Our results show that, for certain classes of problems, the bound improvement is considerable.
Original languageEnglish
Pages41-45
Number of pages5
Publication statusPublished - Aug 2014
EventInternational Workshop on Lot-Sizing (IWLS) 2014 - Porto, Portugal
Duration: 27 Aug 201429 Aug 2014

Workshop

WorkshopInternational Workshop on Lot-Sizing (IWLS) 2014
Country/TerritoryPortugal
CityPorto
Period27/08/1429/08/14

Keywords

  • convex hull closures
  • lot-sizing problems
  • two-period relaxations

Fingerprint

Dive into the research topics of 'A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems'. Together they form a unique fingerprint.

Cite this