Generalized Benders decomposition algorithm

Generalized Benders decomposition (GBD), derived in Geoffrion (1972), is an algorithm that operates in a similar way to outer approximation and can be applied to MINLP problems. Like OA, when GBD is applied to models of the form (9.2)-(9.5), each major iteration is composed of the solution of two subproblems. At major iteration K one of these subproblems is NLP(y ), given in Equations (9.6)-(9.7). This is an NLP in the continuous variables x, with y fixed at y The other GBD subproblem is an integer linear program, as in OA, but it only involves the... 

In sections 63-6.1 we discussed the generalized benders decomposition GBD and the outer approximation based algorithms (i.e., OA, OA/ER, OA/ER/AP, GOA), and we identified a number of similarities as well as key differences between the two classes of MINLP algorithms. 

MINOPT (Mixed Integer Nonlinear OPTimizer) is written entirely in C and solves MINLP problems by a variety of algorithms that include (i) the Generalized Benders Decomposition GBD, (ii) the Outer Approximation with Equality Relaxation OA/ER, (iii) the Outer Approximation with Equality Relaxation and Augmented Penalty OA/ER/AP, and (iv) the Generalized Cross Decomposition GCD. 

The branch and bound method can be used for MINLP problems, but it requires solving a large number of NLP problems and is, therefore, computationally intensive. Instead, methods such as the Generalized Benders Decomposition and Outer Approximation algorithms are usually preferred. These methods solve a master MILP problem to initialize the discrete variables at each stage and then solve an NLP subproblem to optimize the continuous variables. Details of these methods are given in Biegler et al. (1997) and Diwekar (2003). 

MINLP problems can be solved using several algorithms including branch-and-bound, generalized Benders decomposition (GBD), and the Outer Approximation/Equality-Relaxation (OA/ER). These... 

---