A Horizon Decomposition approach for the Capacitated Lot Sizing Problem with Setup Times

Ioannis Fragkos, Zeger Degraeve, B De Reyck

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)

Abstract

We introduce horizon decomposition in the context of Dantzig-Wolfe decomposition, and apply it to the capacitated lot-sizing problem with setup times. We partition the problem horizon in contiguous overlapping intervals and create subproblems identical to the original problem, but of smaller size. The user has the flexibility to regulate the size of the master problem and the subproblem via two scalar parameters. We investigate empirically which parameter configurations are efficient, and assess their robustness at different problem classes. Our branch-and-price algorithm outperforms state-of-the-art branch-and-cut solvers when tested to a new data set of challenging instances that we generated. Our methodology can be generalized to mathematical programs with a generic constraint structure.
Original languageEnglish
Pages (from-to)465-482
Number of pages18
JournalINFORMS Journal on Computing
Volume28
Issue number3
DOIs
Publication statusPublished - 2016

Fingerprint

Dive into the research topics of 'A Horizon Decomposition approach for the Capacitated Lot Sizing Problem with Setup Times'. Together they form a unique fingerprint.

Cite this