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

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

The extended cuttingplane (ECP) algorithm [Westerlund and Pet-tersson, Computers and Chem. Engng. 19 S131 (1995)] is complementary to GBD. While the lower bounding problem in Pig. 3-62 remains essentially the same, the continuous variables xk are chosen from the MILP solution and the NLP (3-113) is replaced by a simple evaluation of the objective and constraint functions. As a result, only MILP problems [(3-116) plus integer cuts] need be solved. Consequently, the ECP approach has weaker upper bounds than outer approximation and requires more MILP solutions. It has advantages over outer approximation when the NLP (3-113) is expensive to solve. 

The MINLP-problems were implemented in GAMS [7, 8] and solved by the outer approximation/equality relaxation/augmented penalty-method [9] as implemented in DICOPT. The algorithm generates a series of NLP and MILP subproblems, which were solved by the generalized reduced gradient method [10] as implemented in CONOPT and the integrality relaxation based branch and cut method as... 

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

The big-M formulation is often difficult to solve, and its difficulty increases as M increases. This is because the NLP relaxation of this problem (the problem in which the condition yt = 0 or 1 is replaced by yt between 0 and 1) is often weak, that is, its optimal objective value is often much less than the optimal value of the MINLP. An alternative to the big-M formulation is described in Lee and Grossman (2000) using an NLP relaxation, which often has a much tighter bound on the optimal MINLP value. A branch-and-bound algorithm based on this formulation performed much better than a similar method applied to the big-M formulation. An outer approximation approach is also described by Lee and Grossmann (2000). 

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. 

In the sequel, we will discuss the vl-GBD for class 1 problems since this by itself defines an interesting mathematical structure for which other algorithms (e.g., Outer Approximation) has been developed. 

---