From Cornell University Computational Optimization Open Textbook - Optimization Wiki
|
|
Line 51: |
Line 51: |
| <math display=block>0 \leq x_{2}\leq 4</math> | | <math display=block>0 \leq x_{2}\leq 4</math> |
| <math display=block>y_{1},y_{2} \in \big\{0,1\big\} </math> | | <math display=block>y_{1},y_{2} \in \big\{0,1\big\} </math> |
| | |
| | ''MILP Solution: ''<math display=inline>x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0</math>, Lower Bound = 6 <br> |
| | Lower Bound<Upper Bound, Integer Cut:<math display=inline>y_{1}- y_{2}\leq 0</math> |
|
| |
|
| ==Conclusion== | | ==Conclusion== |
|
| |
|
| ==References== | | ==References== |
Revision as of 06:32, 26 November 2021
Author: Yousef Aloufi (CHEME 6800 Fall 2021)
Introduction
Theory
Example
Minimize
![{\displaystyle f(x)=y_{1}+y_{2}+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ab8e1bc126cd849f5060c9ca69bcd4ac447b33c)
Subject to ![{\displaystyle {\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6bcfcc560c0186731c410cef4630175e4465790)
![{\displaystyle x_{1}-2y_{1}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdeb45cdc9c09055bad00731bb702e5f3f4b05eb)
![{\displaystyle x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6ad6d8e0c1c6473936775029d2419ea266e55c2)
![{\displaystyle x_{1}+y_{1}-1\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66264acb5380e9823af9358b1d97714f08b0fa23)
![{\displaystyle x_{2}-y_{2}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdbc6f7e5d1c9094a20d5f6c73758e5735179dcb)
![{\displaystyle x_{1}+x_{2}\geq 3y_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88a0e12b50bfb973b9e9c27458eb703ca965d7b4)
![{\displaystyle y_{1}+y_{2}\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7201c9465abeab7744902821bd4a3d25876331b)
![{\displaystyle 0\leq x_{1}\leq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a48467cb5ee7a8e445f5a1a61975fd9e79dd012b)
![{\displaystyle 0\leq x_{2}\leq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d05a2ca84eb35b390327ab7240b78cc971c9dc7)
![{\displaystyle y_{1},y_{2}\in {\big \{}0,1{\big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5fa1b50e362c07e6324569f4951f77af3107fb1)
Solution
Step 1a: Start from
![{\textstyle y_{1}=y_{2}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e10ae5b4d30fa85051c423a238d46c2a14527f69)
and solve the NLP below:
Minimize ![{\displaystyle f=2+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec3b1d0eec2d84d99d5eeaf17972e42894f3e815)
Subject to ![{\displaystyle {\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6bcfcc560c0186731c410cef4630175e4465790)
![{\displaystyle x_{1}-2\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14983c6c0276939dd02cfac381a1e04e8437f6ab)
![{\displaystyle x_{1}-x_{2}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1767b4f30f6fa67fe29baa978cffc7ff4b5592f5)
![{\displaystyle x_{1}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1158db629080d417050d60fed774e0f12084231)
![{\displaystyle x_{2}-1\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2068f6e9b72606cd635e83ce21d85d00ed7d1c87)
![{\displaystyle x_{1}+x_{2}\geq 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f105325bbaf9ae2cb549be8b876004cc659333af)
![{\displaystyle 0\leq x_{1}\leq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a48467cb5ee7a8e445f5a1a61975fd9e79dd012b)
![{\displaystyle 0\leq x_{2}\leq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d05a2ca84eb35b390327ab7240b78cc971c9dc7)
Solution: ![{\textstyle x_{1}=2,x_{2}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa6a85b0be2f68d750cd3f53a811deb3178cc8cd)
, Upper Bound = 7
Step 1a: Solve the MILP master problem with OA for
:
![{\displaystyle 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3aa00d3f49988a196d93388e7ac41da58fc00066)
![{\displaystyle 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 )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29222aefe55bdb63f346ae1a3c21c27fe7efa013)
![{\displaystyle 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f025d4d61d63efd6a87b01d8e7848abc520f2bfa)
![{\displaystyle 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52bbf7d8d87d53306f2542ef0f6ff2b8a75ce4a9)
Minimize
![{\displaystyle \alpha }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b79333175c8b3f0840bfb4ec41b8072c83ea88d3)
Subject to ![{\displaystyle \alpha \geq y_{1}+y_{2}+5+4{\big (}x_{1}-2{\big )}+2{\big (}x_{2}-1{\big )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9590b067f75649c3a890306d81014f92ffc93995)
![{\displaystyle -x_{2}\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9815cf2113aceecb21a18380eef526bb7a9a1aef)
![{\displaystyle x_{1}-2y_{1}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdeb45cdc9c09055bad00731bb702e5f3f4b05eb)
![{\displaystyle x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6ad6d8e0c1c6473936775029d2419ea266e55c2)
![{\displaystyle x_{1}+y_{1}-1\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66264acb5380e9823af9358b1d97714f08b0fa23)
![{\displaystyle x_{2}-y_{2}\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdbc6f7e5d1c9094a20d5f6c73758e5735179dcb)
![{\displaystyle x_{1}+x_{2}\geq 3y_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88a0e12b50bfb973b9e9c27458eb703ca965d7b4)
![{\displaystyle y_{1}+y_{2}\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7201c9465abeab7744902821bd4a3d25876331b)
![{\displaystyle 0\leq x_{1}\leq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a48467cb5ee7a8e445f5a1a61975fd9e79dd012b)
![{\displaystyle 0\leq x_{2}\leq 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d05a2ca84eb35b390327ab7240b78cc971c9dc7)
![{\displaystyle y_{1},y_{2}\in {\big \{}0,1{\big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5fa1b50e362c07e6324569f4951f77af3107fb1)
MILP Solution:
, Lower Bound = 6
Lower Bound<Upper Bound, Integer Cut:
Conclusion
References