Dantzig–Wolfe decomposition is an algorithm for solving
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
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
Column generation or delayed column generation is an efficient algorithm for solving large linear programs.
The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by so ...
for improving the
tractability of large-scale linear programs. For most linear programs solved via the revised
simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are ...
, 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 ''F
i'' 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 every point of a non-empty, bounded
convex polyhedron
In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
can be represented as a
convex combination
In convex geometry and Vector space, vector algebra, a convex combination is a linear combination of point (geometry), points (which can be vector (geometric), vectors, scalar (mathematics), scalars, or more generally points in an affine sp ...
of its
extreme points.
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
closed source
Proprietary software is software that grants its creator, publisher, or other rightsholder or rightsholder partner a legal monopoly by modern copyright and intellectual property law to exclude the recipient from freely sharing the software or modi ...
AMPL
AMPL (A Mathematical Programming Language) is an algebraic modeling language to describe and solve high-complexity problems for large-scale mathematical computing (e.g. large-scale optimization and scheduling-type problems).
It was developed ...
and
GAMS mathematical modeling software. There are general, parallel, and fast implementations available as
open-source software
Open-source software (OSS) is Software, computer software that is released under a Open-source license, license in which the copyright holder grants users the rights to use, study, change, and Software distribution, distribute the software an ...
, including some provided by
JuMP and the
GNU Linear Programming Kit
The GNU Linear Programming Kit (GLPK) is a software package intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the fo ...
.
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 (2001) computational evaluation of Dantzig-Wolfe in general and Dantzig-Wolfe and parallel computation is the PhD thesis by J. R. Tebboth
[
]
See also
*
Delayed column generation
Column generation or delayed column generation is an efficient algorithm for solving large linear programs.
The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by so ...
*
Benders' decomposition
References
{{DEFAULTSORT:Dantzig-Wolfe decomposition
Linear programming
Decomposition methods