From Cornell University Computational Optimization Open Textbook - Optimization Wiki
|
|
Line 30: |
Line 30: |
| <math display=block>0 \leq x_{2}\leq 4</math> | | <math display=block>0 \leq x_{2}\leq 4</math> |
| ''Solution: ''<math display=inline>x_{1}=2, x_{2}=1</math>, Upper Bound = 7 <br> | | ''Solution: ''<math display=inline>x_{1}=2, x_{2}=1</math>, Upper Bound = 7 <br> |
| | |
| | '''Step 1a:''' Solve the MILP master problem with OA for <math display=inline> x^{*} =[2,1] </math> : <br> |
| | <math display=block>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} </math> |
|
| |
|
| ==Conclusion== | | ==Conclusion== |
|
| |
|
| ==References== | | ==References== |
Revision as of 05:52, 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/53a4da719bf07dc10c836a41caa820990b28459d)
Conclusion
References