Generalized Benders decomposition

In Generalized Benders Decomposition (GBD) [see Sahinidis and Grossmann, Computers and Chem. Eng. 15 481 (1991)], the lower... 

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... 

Geoffrion, A. M. Generalized Benders Decomposition. J Optim Theory Appl 10(4) 237-260 (1972). 

Generalized Benders Decomposition, GBD (Geoffrion, 1972 Paules and Floudas,... 

In the pioneering work of Geoffrion (1972) on the Generalized Benders Decomposition GBD two sequences of updated upper (nonincreasing) and lower (nondecreasing) bounds are created... 

The Generalized Cross Decomposition GCD simultaneously utilizes primal and dual information by exploiting the advantages of Dantzig-Wolfe and Generalized Benders decomposition. 

The basic idea in Generalized Benders Decomposition GBD is the generation, at each iteration, of an upper bound and a lower bound on the sought solution of the MINLP model. The upper bound results from the primal problem, while the lower bound results from the master problem. The primal problem corresponds to problem (6.2) with fixed y-variables (i.e., it is in the jr-space only), and its solution provides information about the upper bound and the Lagrange... 

This section presents the theoretical development of the Generalized Benders Decomposition GBD. The primal problem is analyzed first for the feasible and infeasible cases. Subsequently, the theoretical analysis for the derivation of the master problem is presented. 

We mentioned in remark 1 of the formulation section (i.e., 6.3.1), that problem (6.2) represents a subclass of the problems for which the Generalized Benders Decomposition GBD can be applied. This is because in problem (6.2) we considered the y G T set to consist of 0-1 variables, while Geoffrion (1972) proposed an analysis for Y being a continuous, discrete or continuous-discrete set. 

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. 

The derivation of the primal master problem follows the same steps as the derivation of the master problem in Generalized Benders Decomposition GBD. The final form of the primal master problem is ... 

Remark 3 The upper bounding sequence Pk, and the lower bounding sequence pfe will converge to the optimal value of (6.52). This corresponds to the Generalized Benders Decomposition GBD part of the Generalized Cross Decomposition. 

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. 

J.A. Bloom. Solving an electricity generating capacity expansion planning problem by generalized benders decomposition. Oper. Res., 31(5) 84, 1983. 

A. M. Geoffrion. Generalized benders decomposition. J. Optim. Theory and Appl., 10(4) 237, 1972. 

H. H. Hoang. Topological optimization of networks A nonlinear mixed integer model employing generalized Benders decomposition. IEEE Trans. Automatic Control, AC-27 164, 1982. 

R. Rouhani, W. Lasdon, L. Lebow, and A. D. Warren. A generalized benders decomposition approach to reactive source planning in power systems. Math. Progr. Study, 25 62, 1985. 

N. V. Sahinidis and I. E. Grossmann. Convergence properties of generalized Benders decomposition. Comp. Chem. Eng., 15(7) 481, 1991. 

Sahinidis. N. V and Grossmann. 1. E. Convergence Properties of Generalized Benders Decomposition. Comput. Chem. Eng. 15,481 (1991b). 

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... 

---