On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm

By F. Vanderbeck. Operational Research, 2000

330 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Selected Topics in Column Generation (2002, background): “When integer solutions are sought for the MP, general branching schemes are given by Vanderbeck (2000) and Vanderbeck and Wolsey (1996).”
Integer and Combinatorial Optimization (2013, methodology): “" The bound resulting from a particular decomposition can be computed using two different computational techniques—Dantzig-Wolfe decomposition (Dantzig and Wolfe, 1960; Vanderbeck, 2000) (column generation) and Lagrangian relaxation (Fisher, 1981; Geoffrion, 1974; Held and Karp, 1970).”
A Primer in Column Generation (2005, methodology): “Let us also remark that instead of a convexification of the subproblem’s domain X (when bounded), one can explicitly represent all integer points in X via a discretization approach formulated by Vanderbeck, 2000 .”
50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art (2010, methodology): “In the third paper entitled Reformulation and Decomposition of Integer Programs, François Vanderbeck and Laurence Wolsey survey ways to reformulate integer and mixed integer programs to obtain stronger linear programming relaxations.”
Bin packing and cutting stock problems: Mathematical models and exact algorithms (2016, methodology): “Vanderbeck [150] introduced a branch-and-price algorithm whose rule is to branch on a set of columns.”