A new dantzig-wolfe reformulation and branch-and-price algorithm for the capacitated lot-sizing problem with setup times

摘要

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.