Dantzig-Wolfe decomposition
From DDL Wiki
Current revision (17:26, 12 November 2008) (view source) m (revised text) |
|||
| (2 intermediate revisions not shown.) | |||
| Line 1: | Line 1: | ||
| - | Dantzig-Wolfe decomposition is a type of [[ | + | Dantzig-Wolfe decomposition is a type of [[decomposition]] technique used to solve linear programming (LP) problems. The technique can be used when the LP has special structure 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 block angular 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]] | ||
Current revision
Dantzig-Wolfe decomposition is a type of decomposition technique used to solve linear programming (LP) problems. The technique can be used when the LP has special structure 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 block angular 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.
