Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Operations Researcharrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Operations Research
Article . 2007 . Peer-reviewed
Data sources: Crossref
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

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

Authors: Degraeve, Z.; Jans, R.F.;

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

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.

Related Organizations
Keywords

Dantzig-Wolfe decomposition, Lagrange relaxation, branch-and-price, lot sizing, mixed-integer programming, jel: jel:M, jel: jel:M11, jel: jel:C61, jel: jel:R4

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    81
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
81
Top 10%
Top 10%
Top 10%
bronze