Benders' decomposition
Encyclopedia
Benders' decomposition is a technique in mathematical programming
that allows the solution of very large linear programming
problems that have a special block structure
. This structure often occurs in applications such as stochastic programming
.
As it progress towards a solution, Benders' decomposition adds new constraints , so the approach is called "row generation". In contrast, Dantzig–Wolfe decomposition
uses "column generation".
Mathematical Programming
Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...
that allows the solution of very large linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problems that have a special block structure
Block structure
* In mathematics, block structure is a possible property of matrices - see block matrix.* In computer science, a programming language has block structure if it features blocks which can be nested to any depth....
. This structure often occurs in applications such as stochastic programming
Stochastic programming
Stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within...
.
As it progress towards a solution, Benders' decomposition adds new constraints , so the approach is called "row generation". In contrast, Dantzig–Wolfe decomposition
Dantzig–Wolfe decomposition
Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Phil Wolfe and initially published in 1960...
uses "column generation".
See also
- FortSPFortSPFortSP is a software package for solving stochastic programming problems. It solves scenario-based SP problems with recourse as well as problems with chance constraints and integrated chance constraints...
solver uses Benders' decomposition for solving stochastic programming problems