Benders’ decomposition is an iterative technique for mathematical programming in which a problem is decomposed into two parts: a master problem which solves for only a subset of the variables, and a subproblem which solves for the remaining variables while treating the master variables as fixed. The technique uses information from the solution of the subproblem to design a constraint that is unsatisfied by the current master solution but necessary for the optimal solution of the full problem. The master problem and subproblem are solved iteratively as new constraints are added to the master problem until no such constraint exists and the last master solution therefore optimizes the full problem. In traditional Benders’ decomposition , the subproblem is a linear program, and the Benders’ constraint is based on the dual solution to that subproblem. More recently, logic-based  or combinatorial Benders’  have been developed that generate Benders constraints based on infeasibility or suboptimality-based constraints. By not requiring a linear programming subproblem, Benders approaches provide an excellent approach to integrating disparate optimization approaches.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- A Benders’Approach to a Transportation Network Design Problem
Michael A. Trick
- Springer Berlin Heidelberg
Neuer Inhalt/© ITandMEDIA