Dantzig–Wolfe decomposition
Encyclopedia
Dantzig–Wolfe decomposition is an algorithm for solving linear programming
problems with special structure. It was originally developed by George Dantzig
and Phil 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.
The D matrix represents the coupling constraints and each Fi represents the independent submatrices. Note that it is possible to run the algorithm when there is only one F submatrix.
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).
Each column in the new master program represents a solution to one of the subproblems. The master program enforces that the coupling constraints are satisfied given the set of subproblem solutions that are currently available. The master program then requests additional solutions from the subproblem such that the overall objective to the original linear program is improved.
and GAMS
mathematical modeling languages. There is a general, parallel implementation available that leverages the open source GNU Linear Programming Kit
.
The algorithm can be implemented such that the subproblems are solved in parallel, since their solutions are completely independent. When this is the case, there are options for the master program as to how the columns should be integrated into the master. The master may wait until each subproblem has completed and then incorporate all columns that improve the objective or it may choose a smaller subset of those columns. Another option is that the master may take only the first available column and then stop and restart all of the subproblems with new objectives based upon the incorporation of the newest column.
Another design choice for implementation involves columns that exit the basis at each iteration of the algorithm. Those columns may be retained, immediately discarded, or discarded via some policy after future iterations (for example, remove all non-basic columns every 10 iterations).
A recent (2001) computational evaluation of Dantzig-Wolfe in general and Dantzig-Wolfe and parallel computation is the PhD thesis by J. R. Tebboth
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problems with special structure. It was originally developed by George Dantzig
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
and Phil Wolfe and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm
Decomposition method
In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set...
.
Dantzig–Wolfe decomposition relies on delayed column generation
Delayed column generation
Delayed column generation is an efficient algorithm for solving larger linear programs.The overarching idea is that many linear programs are too large to consider all the variables explicitly. Since most of the variables will be non-basic and assume a value of zero in the optimal solution, only a...
for improving the tractability of large-scale linear programs. For most linear programs solved via the revised simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
, 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.
Required form
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 Fi represents the independent submatrices. Note that it is possible to run the algorithm when there is only one F submatrix.
Problem reformulation
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 combinationConvex combination
In convex geometry, a convex combination is a linear combination of points where all coefficients are non-negative and sum up to 1....
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).
Each column in the new master program represents a solution to one of the subproblems. The master program enforces that the coupling constraints are satisfied given the set of subproblem solutions that are currently available. The master program then requests additional solutions from the subproblem such that the overall objective to the original linear program is improved.
The algorithm
While there are several variations regarding implementation, the Dantzig–Wolfe decomposition algorithm can be briefly described as follows:- Starting with a feasible solution to the reduced master program, formulate new objective functions for each subproblem such that the subproblems will offer solutions that improve the current objective of the master program.
- Subproblems are re-solved given their new objective functions. An optimal value for each subproblem is offered to the master program.
- The master program incorporates one or all of the new columns generated by the solutions to the subproblems based on those columns' respective ability to improve the original problem's objective.
- Master program performs x iterations of the simplex algorithm, where x is the number of columns incorporated.
- If objective is improved, goto step 1. Else, continue.
- The master program cannot be further improved by any new columns from the subproblems, thus return.
Implementation
There are examples of the implementation of Dantzig–Wolfe decomposition available in the AMPLAMPL
AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving high-complexity problems for large-scale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...
and GAMS
General Algebraic Modeling System
The General Algebraic Modeling System is a high-level modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixed-integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to...
mathematical modeling languages. There is a general, parallel implementation available that leverages the open source GNU Linear Programming Kit
GNU Linear Programming Kit
The GNU Linear Programming Kit is a software package intended for solving large-scale linear programming , mixed integer programming , and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library...
.
The algorithm can be implemented such that the subproblems are solved in parallel, since their solutions are completely independent. When this is the case, there are options for the master program as to how the columns should be integrated into the master. The master may wait until each subproblem has completed and then incorporate all columns that improve the objective or it may choose a smaller subset of those columns. Another option is that the master may take only the first available column and then stop and restart all of the subproblems with new objectives based upon the incorporation of the newest column.
Another design choice for implementation involves columns that exit the basis at each iteration of the algorithm. Those columns may be retained, immediately discarded, or discarded via some policy after future iterations (for example, remove all non-basic columns every 10 iterations).
A recent (2001) computational evaluation of Dantzig-Wolfe in general and Dantzig-Wolfe and parallel computation is the PhD thesis by J. R. Tebboth