Outer-approximation algorithm

Compared to nonlinear branch and bound, the outer approximation algorithm usually requires very few solutions of the MILP and NLP subproblems. This is especially advantageous on problems where the NLPs are large and expensive to solve. Moreover, there are two variations of outer approximation that may be suitable for particular problem types ... 

Duran, M. A. and I. E. Grossmann. An Outer Approximation Algorithm for a Class of Mixed—Integer Nonlinear Programs. Math Prog 36 307-339, (1986). 

In the subsequent sections, we will concentrate on the algorithms that are based on decomposition and outer approximation, that is on 1., 3., 5., 6., 7., and 8.. This focus of our study results from the existing evidence of excellent performance of the aforementioned decomposition-based and outer approximation algorithms compared to the branch and bound methods and the feasibility approach. 

Remark 3 Note that if in addition to the separability of x and y, we assume that y participates linearly (i.e., conditions for Outer Approximation algorithm), then we have... 

Fletcher and Ley ffer (1994) studied the worst-case performance of GOA in an attempt to present the potential limitations that the outer approximation algorithm of Duran and Grossmann (1986a) may exhibit despite the encouraging experience obtained from application to engineering problems. 

M. A. Duran and I. E. Grossmann. An outer approximation algorithm for a class of mixed-integer nonlinear programs. Math. Prog., 36 307,1986a. 

Figure 9.15. Worst-case Design using Outer Approximation Algorithm.

Turkay, M., and Grossmann, I.E. A Logic Based Outer-Approximation Algorithm for MINLP Optimization of Process Flowsheets, AIChE Annual Meeting, San Francisco (1994). 

The general structure of an outer-approximation algorithm for worst-case design is as follows... 

The new worst-case design algorithm is discussed further below following the general outer-approximation algorithm structure constraint maximization, initialization, and multi-mode design. 

The outer-approximation algorithm (Section II.A) took six iterations to identify this solution, with a projection factor, e, of. 05 on the disturbance amplitude. Both vertex and nonvertex constraint maximizers were identified, confirming the need to consider nonvertex maximizers. The variables that contributed nonvertex maximizers were the step switching times (several times) and the measurement lags (once). Robustness was verified with respect to all vertex combinations of uncertain values and a random selection of interior points (ivert = 1, nrand y = 1000). 

Mayne, D. Q., Michalska, H., and Polak, E. An Efficient Outer Approximations Algorithm for Solving Infinite Sets of Inequalities, in Proceedings of the 29th Conference of Decision and Control, 1990, p. 960-955 (1990). 

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

Duran, M.A. and Grossmann, I.E., 1986, An Outer-Approximation Algorithm for a class of Mixed-Integer Nonlinear Programs. Math. Prog., 36, 307. 

Once an initial solution is incorporated into the MINLP model, the model is solved via the DICOPT solver employing the Outer approximation algorithm for equality relaxation and augmented penalty (OA/ER/AP). 

---