UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

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

Fragkos, I; Degraeve, Z; De Reyck, B; (2016) A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times. INFORMS Journal on Computing , 28 (3) pp. 465-482. 10.1287/ijoc.2016.0691. Green open access

[thumbnail of De Reyck_Horizon_Decomposition_Final.pdf]
Preview
Text
De Reyck_Horizon_Decomposition_Final.pdf - Accepted Version

Download (652kB) | Preview

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.

Type: Article
Title: A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times
Open access status: An open access version is available from UCL Discovery
DOI: 10.1287/ijoc.2016.0691
Publisher version: http://doi.org/10.1287/ijoc.2016.0691
Language: English
Keywords: Science & Technology, Technology, Computer Science, Interdisciplinary Applications, Operations Research & Management Science, Computer Science, algorithms, lot sizing, branch and price, BRANCH-AND-PRICE, STABILIZED COLUMN GENERATION, INTEGER PROGRAMS, LOWER BOUNDS, FORMULATIONS, HEURISTICS, MODEL
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > UCL School of Management
URI: https://discovery.ucl.ac.uk/id/eprint/1514841
Downloads since deposit
205Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item