Dantzig-Wolfe decomposition

Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm.

Dantzig–Wolfe decomposition relies on delayed column generation for improving the tractability of large-scale linear programs. For most linear programs solved via the revised simplex algorithm, at each step, most columns (variables) are not in the basis. In such a scheme, a master problem containing at least the currently active columns (the basis) uses a subproblem or subproblems to generate columns for entry into the basis such that their inclusion improves the objective function.

In order to use Dantzig–Wolfe decomposition, the constraint matrix of the linear program must have a specific form. A set of constraints must be identified as "connecting", "coupling", or "complicating" constraints wherein many of the variables contained in the constraints have non-zero coefficients. The remaining constraints need to be grouped into independent submatrices such that if a variable has a non-zero coefficient within one submatrix, it will not have a non-zero coefficient in another submatrix. This description is visualized below:

The D matrix represents the coupling constraints and each F_i represents the independent submatrices. Note that it is possible to run the algorithm when there is only one F submatrix.

After identifying the required form, the original problem is reformulated into a master program and n subprograms. This reformulation relies on the fact that a non-empty, bounded convex polyhedron can be represented as a convex combination of its extreme points (or, in the case of an unbounded polyhedron, a convex combination of its extreme points and a weighted combination of its extreme rays).

...
Wikipedia