Dantzig-Wolfe decomposition
From DDL Wiki
m |
|||
| Line 1: | Line 1: | ||
| - | Dantzig-Wolfe decomposition is a type of [[decomposition]] technique used to solve | + | Dantzig-Wolfe decomposition is a type of [[decomposition]] technique used to solve linear programming (LP) problems. The technique takes exploits the structure of the LP to generate subproblems that can be solved efficiently. In particular, it divides the constraints into a set of general constraints and a set of constraints that have special structure. The technique iterates between solving an LP (the master problem) with the general constraints and solving the subproblem with the special constraints. It is a type of column generation technique. |
| + | |||
| + | Dantzig-Wolfe decomposition is a special case of applying the more general Benders' decomposition and Lagrangian relaxation techniques to linear programs. | ||
== References == | == References == | ||
| - | + | Bazaraa, Mokhtar, John J. Jarvis, and Hanif D. Sherali, ''Linear Programming and Network Flows,'' Second Edition, John Wiley & Sons, New York, 1990. | |
[[Category:optimization]] | [[Category:optimization]] | ||
[[Category:decomposition]] | [[Category:decomposition]] | ||
Revision as of 17:23, 12 November 2008
Dantzig-Wolfe decomposition is a type of decomposition technique used to solve linear programming (LP) problems. The technique takes exploits the structure of the LP to generate subproblems that can be solved efficiently. In particular, it divides the constraints into a set of general constraints and a set of constraints that have special structure. The technique iterates between solving an LP (the master problem) with the general constraints and solving the subproblem with the special constraints. It is a type of column generation technique.
Dantzig-Wolfe decomposition is a special case of applying the more general Benders' decomposition and Lagrangian relaxation techniques to linear programs.
References
Bazaraa, Mokhtar, John J. Jarvis, and Hanif D. Sherali, Linear Programming and Network Flows, Second Edition, John Wiley & Sons, New York, 1990.
