A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times

Zeger Degraeve () and Raf Jans ()
Additional contact information
Zeger Degraeve: London Business School, Regent's Park, London NW1 4SA, United Kingdom
Raf Jans: RSM Erasmus University, 3000 DR Rotterdam, The Netherlands

Operations Research, 2007, vol. 55, issue 5, 909-920

Abstract: Although the textbook Dantzig-Wolfe decomposition reformulation for the capacitated lot-sizing problem, as already proposed by Manne [Manne, A. S. 1958. Programming of economic lot sizes. Management Sci. 4 (2) 115--135], provides a strong lower bound, it also has an important structural deficiency. Imposing integrality constraints on the columns in the master program will not necessarily give the optimal integer programming solution. Manne's model contains only production plans that satisfy the Wagner-Whitin property, and it is well known that the optimal solution to a capacitated lot-sizing problem will not necessarily satisfy this property. The first contribution of this paper answers the following question, unsolved for almost 50 years: If Manne's formulation is not equivalent to the original problem, what is then a correct reformulation? We develop an equivalent mixed-integer programming (MIP) formulation to the original problem and show how this results from applying the Dantzig-Wolfe decomposition to the original MIP formulation. The set of extreme points of the lot-size polytope that are needed for this MIP Dantzig-Wolfe reformulation is much larger than the set of dominant plans used by Manne. We further show how the integrality restrictions on the original setup variables translate into integrality restrictions on the new master variables by separating the setup and production decisions. Our new formulation gives the same lower bound as Manne's reformulation. Second, we develop a branch-and-price algorithm for the problem. Computational experiments are presented on data sets available from the literature. Column generation is accelerated by a combination of simplex and subgradient optimization for finding the dual prices. The results show that branch-and-price is computationally tractable and competitive with other state-of-the-art approaches found in the literature.

Keywords: integer programming; algorithms; decomposition; column generation; branch-and-price; inventory/production: lot sizing; setup times (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0404 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:55:y:2007:i:5:p:909-920

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().