Outer-approximation (OA)

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Introduction

Mixed-integer nonlinear programming (MINLP) deals with optimization problems by combining the modeling capabilities of mixed-integer linear programming (MILP) and nonlinear programming (NLP) into a powerful modeling framework. The integer variables make it possible to incorporate discrete decisions and logical relations in the optimization problems, and the combination of linear and nonlinear functions make it possible to accurately describe a variety of different phenomena. The ability to accurately model real-world problems has made MINLP an active research area and there exists a vast number of applications in fields such as engineering, computational chemistry, and finance. MINLP problems are usually the hardest to solve unless a special structure can be exploited. Consider the following MINLP formulation :

Theory

The Outer-Approximation (OA) algorithm was first proposed by Duran and and Grossmann in 1986 to solve MINLP problems. The basic idea of the OA method is to solve a sequence of nonlinear programming sub-problems and relaxed mixed-integer linear master problem successfully. In a minimization problem, for example, the NLP subproblems appear for a fixed number of binary variables, and involve the optimization of continuous variables with an upper bound to the original MINLP is obtained. The MILP master problem provides a global linear approximation to the MINLP in which the objective function is underestimated and the nonlinear feasible region is overestimated. In addition, the linear approximations to the nonlinear equations are relaxed as inequalities. This MILP master problem accumulates the different linear approximations of previous iterations so as to produce an increasingly better approximation of the original MINLP problem. At each iteration the master problem predicts new values of the binary variables and a lower bound to the objective function. Finally, the search is terminated when no lower bound can be found below the current best upper bound which then leads to an infeasible MILP.

Example

Numerical Example

The following is a step-by-step solution for an MINLP optimization problem using Outer-Approximation method:
Minimize

$$f(x)=y_{1}+y_{2}+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2y_{1}\geq 0$$

$$x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0$$

$$x_{1}+y_{1}-1\geq 0$$

$$x_{2}-y_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3y_{1}$$

$$y_{1}+y_{2}\geq 1$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

$$y_{1},y_{2}\in {\big \{}0,1{\big \}}$$

Solution
Step 1a: Start from ${\textstyle y_{1}=y_{2}=1}$ and solve the NLP below:
Minimize

$$f=2+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2\geq 0$$

$$x_{1}-x_{2}\geq 0$$

$$x_{1}\geq 0$$

$$x_{2}-1\geq 0$$

$$x_{1}+x_{2}\geq 3$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

Solution: ${\textstyle x_{1}=2,x_{2}=1}$, Upper Bound = 7

Step 1b: Solve the MILP master problem with OA for ${\textstyle x^{*}=[2,1]}$ :

$$f{\big (}x{\big )}={\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2},~~\bigtriangledown f{\big (}x{\big )}=[2x_{1}~~~~2x_{1}]^{T}~~for~~x^{*}=[2~~~~1]^{T}$$

$$f{\big (}x^{*}{\big )}+\bigtriangledown f{\big (}x^{*}{\big )}^{T}{\big (}x-x^{*}{\big )}=5+[4~~~~2]{\begin{bmatrix}x_{1}-2\\x_{2}-1\end{bmatrix}}=5+4{\big (}x_{1}-2{\big )}+2{\big (}x_{2}-1{\big )}$$

$$g{\big (}x{\big )}={\big (}x_{1}-2{\big )}^{2}-x_{2},~~\bigtriangledown g{\big (}x{\big )}=[2x_{1}-4~~~~-1]^{T}~~for~~x^{*}=[2~~~~1]^{T}$$

$$g{\big (}x^{*}{\big )}+\bigtriangledown g{\big (}x^{*}{\big )}^{T}{\big (}x-x^{*}{\big )}=-1+[0~~~~-1]{\begin{bmatrix}x_{1}-2\\x_{2}-1\end{bmatrix}}=-x_{2}$$

Minimize

$$\alpha$$

Subject to

$$\alpha \geq y_{1}+y_{2}+5+4{\big (}x_{1}-2{\big )}+2{\big (}x_{2}-1{\big )}$$

$$-x_{2}\leq 0$$

$$x_{1}-2y_{1}\geq 0$$

$$x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0$$

$$x_{1}+y_{1}-1\geq 0$$

$$x_{2}-y_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3y_{1}$$

$$y_{1}+y_{2}\geq 1$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

$$y_{1},y_{2}\in {\big \{}0,1{\big \}}$$

MILP Solution: ${\textstyle x_{1}=2,x_{2}=1,y_{1}=1,y_{2}=0}$, Lower Bound = 6
Lower Bound < Upper Bound, Integer cut: ${\textstyle y_{1}-y_{2}\leq 0}$

Step 2a: Start from ${\textstyle y=[1,0]}$ and solve the NLP below:
Minimize

$$f=1+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2\geq 0$$

$$x_{1}-x_{2}\geq 0$$

$$x_{1}\geq 0$$

$$x_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

Solution: ${\textstyle x_{1}=2,x_{2}=1}$, Upper Bound = 6
Upper Bound = 6 = Lower Bound, Optimum!
Optimal Solution for the MINLP: ${\textstyle x_{1}=2,x_{2}=1,y_{1}=1,y_{2}=0}$

GAMS Model

The above MINLP example can be expressed in the General Algebraic Modeling System (GAMS) as follows:

Variable z;
Positive Variables x1, x2;
Binary Variables y1, y2;
Equations obj, c1, c2, c3, c4, c5, c6, c7;
obj.. z =e= y1 + y2 + sqr(x1) + sqr(x2);
c1.. sqr(x1 - 2) - x2 =l= 0;
c2.. x1 - 2*y1 =g= 0;
c3.. x1 - x2 - 3*sqr(1 - y1) =g= 0;
c4.. x1 + y1 - 1 =g= 0;
c5.. x2 - y2 =g= 0;
c6.. x1 + x2 =g= 3*y1;
c7.. y1 + y2 =g= 1;
x1.lo = 0; x1.up = 4;
x2.lo = 0; x2.up = 4;
model Example /all/;
option minlp = bonmin;
option optcr = 0;
solve Example minimizing z using minlp;
display z.l, x1.l, x2.l, y1.l, y2.l;

Conclusion

References