Dantzig-Wolfe decomposition

From DDL Wiki

Jump to: navigation, search

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.

Retrieved from "http://wiki.ece.cmu.edu/ddl/index.php/Dantzig-Wolfe_decomposition"
Personal tools