Benders decomposition
Benders decomposition (or 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 block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders.
The strategy behind Benders decomposition can be summarized as divide-and-conquer. That is, in Benders decomposition, the variables of the original problem are divided into two subsets so that a first-stage master problem is solved over the first set of variables, and the values for the second set of variables are determined in a second-stage subproblem for a given first-stage solution. If the subproblem determines that the fixed first-stage decisions are in fact infeasible, then so-called Benders cuts are generated and added to the master problem, which is then re-solved until no cuts can be generated. Since Benders decomposition adds new constraints as it progresses towards a solution, the approach is called "row generation". In contrast, Dantzig–Wolfe decomposition uses "column generation".
Applications
Among the most successful applications of the Benders decomposition is the facility location problem. Castro et al.[1] show the Benders subproblems associated to the mathematical programming formulation of the facility location problem can be separated into block-angular structured linear programming problems. This allows efficiently solving large instances of those problems have been recently proposed by separating the variables of the original problem into binary decisions (corresponding to the placement of facilities) and transportation decisions (corresponding to the commodity flow).
See also
- FortSP solver uses Benders decomposition for solving stochastic programming problems
References
- Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
- Lasdon, Leon S. (2002), Optimization Theory for Large Systems (reprint of the 1970 Macmillan ed.), Mineola, New York: Dover Publications, pp. xiii+523, MR 1888251.
- ↑ Castro, J.; Nasini, S.; Saldanha-da-Gama, F. (2017). "A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method". Mathematical Programming. 163 (1): 411–444. doi:10.1007/s10107-016-1067-6.