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. 

O. E. Flippo and A. H. G. Rinnoy Kan. A note on benders decomposition in mixed integer quadratic programming. Oper. Res. Lett., 9 81, 1990. 

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. 

T. L. Magnanti and R. T. Wong. Accelerating benders decomposition algorithmic enhancement and model selection criterion. Oper. Res., 29(3) 464,1981. 

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. 

Magnanti, T. L., and Wong, R. T. Acclerated Benders Decomposition Algorithm Enhancement and Model Selection Criteria, Open Res. 29, 464-484 (1981). 

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

---