Outer-approximation (OA)

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Introduction

Theory

Example

Numerical Example

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

Subject to
Solution
Step 1a: Start from and solve the NLP below:
Minimize
Subject to
Solution: , Upper Bound = 7

Step 1b: Solve the MILP master problem with OA for  :


Minimize

Subject to

MILP Solution: , Lower Bound = 6
Lower Bound < Upper Bound, Integer cut:

Step 2a: Start from and solve the NLP below:
Minimize

Subject to
Solution: , Upper Bound = 6
Upper Bound = 6 = Lower Bound, Optimum!
Optimal Solution for the MINLP:

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

Template:Reflist

  1. Content of the reference