Outer-approximation (OA)

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Example

Numerical Example

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}$

Code

The following code is used to solve the above example in the General Algebraic Modeling System (GAMS):
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;