Outer-approximation (OA)

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Theory

The Outer-Approximation algorithm was first proposed by Duran and and Grossmann in 1986 to solve MINLP problems. The OA defines the master problem as equivalent In the OA method the optimal solution of he subproblems is used to define a MILP master problem

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;