Benders' decomposition

Benders' decomposition (alternatively, Benders's decomposition; named after Jacques F. Benders) 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 progresses towards a solution, Benders' decomposition adds new constraints , so the approach is called "row generation". In contrast, Dantzig–Wolfe decomposition uses "column generation".

See also

• FortSP solver uses Benders' decomposition for solving stochastic programming problems

References

• J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems," Numer. Math. 4, 3 (Sept. 1962), pp. 238–252.
• Lasdon, Leon S. (2002). Optimization theory for large systems (reprint of the 1970 Macmillan ed.). Mineola, New York: Dover Publications, Inc. pp. xiii+523. MR 1888251.