Dantzig-Wolfe decomposition
From Wikipedia, the free encyclopedia
Dantzig-Wolfe decomposition is a decomposition algorithm for rendering problems tractable for solution under Linear Programming which may otherwise be too big. It was developed by George Dantzig and Phil Wolfe[1]. It is similar to Benders Decomposition in terms of the bounds it uses [2].
In an interview given by Wolfe, he explains that the main idea behind the algorithm was creating a column in the linear programming problem only when needed in order to sidestep the issue of having to deal with too many columns[3].
[edit] References
- ^ Slides from a class on Linear Optimization, Brady Hunsaker, University of Pittsburgh, 2004, accessed 2008-6-11.
- ^ Slides from a class on Dantzig-Wolfe Decomposition, Infanger, Standford University, Winter 2007/2008, accessed 2008-6-11.
- ^ Optimization Trailblazers, The Dantzig-Wolfe Decomposition Algorithm, accessed 2008-6-11.
