Publication Type

Journal Article

Version

publishedVersion

Publication Date

5-2016

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.

Keywords

algorithms, lot sizing, branch and price

Discipline

Business Administration, Management, and Operations | Theory and Algorithms

Research Areas

Operations Management

Publication

INFORMS Journal on Computing

Volume

28

Issue

3

First Page

465

Last Page

482

ISSN

1091-9856

Identifier

10.1287/ijoc.2016.0691

Publisher

INFORMS (Institute for Operations Research and Management Sciences)

Embargo Period

8-29-2021

External URL

https://doi.org/10.1287/ijoc.2016.0691

Download

Share

COinS