https://optimization.mccormick.northwestern.edu/api.php?action=feedcontributions&user=Xudansha&feedformat=atom optimization - User contributions [en] 2022-06-27T04:47:55Z User contributions MediaWiki 1.21.3 https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T23:37:53Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> ===Algorithm Flow Chart ===<br /> The flow chart for outer-approximation is as below<br /> <br /> [[File:A.png|450px]]<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> &lt;math&gt;min f= y_1 +y_2 + {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = 1&lt;/math&gt;.<br /> <br /> <br /> Solving the following NLP,<br /> <br /> &lt;math&gt;min f= 2+ {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2 \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 10&lt;/math&gt;.<br /> <br /> <br /> Solving master program as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge y_1 +y_2 + 8 + 4(x_1-2) + 4(x_2-2)&lt;/math&gt;<br /> <br /> &lt;math&gt; - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 1&lt;/math&gt;.<br /> <br /> <br /> Choose &lt;math&gt;y = [0, 1] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> &lt;math&gt;min f= 1+ {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2 -3\le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3&lt;/math&gt;.<br /> <br /> <br /> Solving master program as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge y_1 +y_2 + 2 + 2(x_1-1) + 2(x_2-1)&lt;/math&gt;<br /> <br /> &lt;math&gt; - 2x_1 - x_2 +3 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T23:30:46Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> ===Algorithm Flow Chart ===<br /> The flow chart for outer-approximation is as below<br /> <br /> [[File:A.png|450px]]<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> &lt;math&gt;min f= y_1 +y_2 + {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = 1&lt;/math&gt;.<br /> <br /> <br /> Solving the following NLP,<br /> <br /> &lt;math&gt;min f= 2+ {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2 \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 10&lt;/math&gt;.<br /> <br /> <br /> Solving master program as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge y_1 +y_2 + 8 + 4(x_1-2) + 4(x_2-2)&lt;/math&gt;<br /> <br /> &lt;math&gt; - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 1&lt;/math&gt;.<br /> <br /> <br /> Choose &lt;math&gt;y = [0, 1] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> &lt;math&gt;min f= 1+ {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2 -3\le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T23:18:57Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> ===Algorithm Flow Chart ===<br /> The flow chart for outer-approximation is as below<br /> <br /> [[File:A.png|450px]]<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> &lt;math&gt;min f= y_1 +y_2 + {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = 1&lt;/math&gt;.<br /> <br /> <br /> Solving the following NLP,<br /> <br /> &lt;math&gt;min f= 2+ {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2 \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 10&lt;/math&gt;.<br /> <br /> <br /> Solving master program as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge y_1 +y_2 + 8 + 4(x_1-2) + 4(x_2-2)&lt;/math&gt;<br /> <br /> &lt;math&gt; - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T23:06:56Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> ===Algorithm Flow Chart ===<br /> The flow chart for outer-approximation is as below<br /> <br /> [[File:A.png|450px]]<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> &lt;math&gt;min f= y_1 +y_2 + {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3y_1&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> &lt;math&gt;min f= 2+ {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2 \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - 1\ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1+x_2 \ge 3&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 10&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T23:04:06Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> ===Algorithm Flow Chart ===<br /> The flow chart for outer-approximation is as below<br /> <br /> [[File:A.png|450px]]<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> &lt;math&gt;min f= y_1 +y_2 + {x_1}^2 + {x_2}^2&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. (x_1-2)^2 - x_2 \le 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1-2y_1 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 -x_2-3(1-y_1) \le 0 &lt;/math&gt;<br /> <br /> &lt;math&gt;x_1 - (1-y_1) \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;x_2 - y_2 \ge 0&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1 + y_2 \ge 1&lt;/math&gt;<br /> <br /> &lt;math&gt;0 \le x_1 \le 4, 0 \le x_2 \le 4&lt;/math&gt;<br /> <br /> &lt;math&gt;y_1, y_2 \in (0,1)&lt;/math&gt;<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T22:25:15Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> ===Algorithm Flow Chart ===<br /> The flow chart for outer-approximation is as below<br /> <br /> [[File:A.png|450px]]<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:A.png File:A.png 2014-06-08T22:18:58Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T22:17:31Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> A classic MINLP problem could be expressed as follows,<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T22:15:15Z <p>Xudansha: /* Master Problem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> &lt;math&gt;min \alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> &lt;math&gt;min Z=\alpha&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. \alpha \ge C^T y + f(x^k) + \triangledown {f(x^k)}^T(x-x^k)&lt;/math&gt;<br /> <br /> &lt;math&gt;g(x^k) + \triangledown {g(x^k)}^T(x-x^k) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in ({0,1})^m&lt;/math&gt;<br /> <br /> &lt;math&gt;\alpha \in \mathbb{R}&lt;/math&gt;<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T22:00:39Z <p>Xudansha: /* Upper Bounding Subproblem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> &lt;math&gt;min Z(y^k) = C^Ty^k + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.g(x) + By^k \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X&lt;/math&gt;<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> &lt;math&gt;min u&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t. g(x) +By^k \leqslant u&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, u \in \mathbb{R}&lt;/math&gt;<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T21:57:24Z <p>Xudansha: /* Problem Statement */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> <br /> &lt;math&gt; Ay \leqslant a&lt;/math&gt;<br /> <br /> &lt;math&gt; x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T21:55:59Z <p>Xudansha: /* Problem Statement */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> &lt;math&gt;x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-06-08T21:55:30Z <p>Xudansha: /* Problem Statement */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;min Z=C^T y + f(x)&lt;/math&gt;<br /> <br /> &lt;math&gt;s.t.&lt;/math&gt; &lt;math&gt;g(x) + By \leqslant 0&lt;/math&gt;<br /> &lt;math&gt;Ay \leqslant a&lt;/math&gt;<br /> &lt;math&gt;x \in X, y \in {0,1}^m&lt;/math&gt;<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T22:22:51Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|180px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|330px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T22:21:36Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;.<br /> <br /> Choose &lt;math&gt;y = [0, 1, 0] &lt;/math&gt;. Insert into upper bound problem as follows:<br /> <br /> [[File:function9.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1]&lt;/math&gt;. &lt;math&gt;f^U = 3.5&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function10.png|400px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 3.5&lt;/math&gt;. <br /> Upper bound is the same with lower bound. Optimal solution is found.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function10.png File:Function10.png 2014-05-25T22:20:06Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function9.png File:Function9.png 2014-05-25T22:13:42Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function8.png File:Function8.png 2014-05-25T22:08:06Z <p>Xudansha: Xudansha uploaded a new version of &amp;quot;File:Function8.png&amp;quot;</p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T22:06:04Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> Start from &lt;math&gt; y_1 = y_2 = y_3 = 1&lt;/math&gt;.<br /> <br /> Solving the following NLP,<br /> <br /> [[File:function7.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [2, 2]&lt;/math&gt;. And the optimal value is &lt;math&gt;f^U = 11&lt;/math&gt;.<br /> <br /> Solving master program as follows:<br /> <br /> [[File:function8.png|200px]]<br /> <br /> The solution is &lt;math&gt;x = [1, 1] y = [0, 1, 0] &lt;/math&gt;. And the optimal value is &lt;math&gt;f^L = 1.5&lt;/math&gt;.<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function8.png File:Function8.png 2014-05-25T22:03:54Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function7.png File:Function7.png 2014-05-25T21:42:59Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:29:46Z <p>Xudansha: /* A Numerical Example */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> The original mixed integer nonlinear problem is as follows:<br /> <br /> [[File:function6.png|250px]]<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function6.png File:Function6.png 2014-05-25T21:27:14Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:24:01Z <p>Xudansha: </p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:23:34Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> Compare the upper and lower bound. One of the following cases must occur:<br /> a) If the upper and lower bound are the same, then stop and final optimal solution is found. <br /> <br /> b) If the upper and lower bound are not the same, then update the &lt;math&gt;y^k&lt;/math&gt; as new fixed value of &lt;math&gt;y&lt;/math&gt;. Then start from upper bounding subproblem again to find the final optimal solution.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:12:24Z <p>Xudansha: /* Convergence and Optimality */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> == Optimality ==<br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:10:00Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bounding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bound. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bounding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> == Convergence and Optimality ==<br /> <br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:09:21Z <p>Xudansha: /* Master Problem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bonding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> Master problem is the relaxation of original MINLP. So we can use this solution as lower bound.<br /> <br /> == Convergence and Optimality ==<br /> <br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:05:01Z <p>Xudansha: /* Convergence and Optimality */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bonding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> == Convergence and Optimality ==<br /> <br /> <br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> <br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:04:16Z <p>Xudansha: /* Master Problem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bonding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|275px]]<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:03:27Z <p>Xudansha: /* Master Problem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bonding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|250px]]<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T21:03:14Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> [[File:function4.png|150px]]<br /> <br /> Based on the solution of upper bonding problem, form a new relaxed MILP as follows:<br /> <br /> [[File:function5.png|200px]]<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function5.png File:Function5.png 2014-05-25T21:02:49Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function4.png File:Function4.png 2014-05-25T20:58:08Z <p>Xudansha: Xudansha uploaded a new version of &amp;quot;File:Function4.png&amp;quot;</p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:53:26Z <p>Xudansha: /* Master Problem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> The main idea of using outer approximation is to develop equivalent linear representation of MINLP and apply relaxation. All the functions in constraints and objective should be convex and differentiable.<br /> <br /> First reformulate the origin MINLP as follows:<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function4.png File:Function4.png 2014-05-25T20:53:11Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:41:16Z <p>Xudansha: /* Upper Bonding Subproblem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> We can use the following NLP to check whether the former NLP is infeasible. <br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:21:16Z <p>Xudansha: /* Reference */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> One of the following cases must occur:<br /> a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> b) This NLP is infeasible. If the fixed &lt;math&gt;y^k&lt;/math&gt; is not feasible, use the following NLP problem to obtain &lt;math&gt;x^k&lt;/math&gt;<br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:20:57Z <p>Xudansha: /* Reference */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> One of the following cases must occur:<br /> a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> b) This NLP is infeasible. If the fixed &lt;math&gt;y^k&lt;/math&gt; is not feasible, use the following NLP problem to obtain &lt;math&gt;x^k&lt;/math&gt;<br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br /> <br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.<br /> <br />  Varvarezos D K, Grossmann I E, Biegler L T. An outer-approximation method for multiperiod design optimization[J]. Industrial &amp; engineering chemistry research, 1992, 31(6): 1466-1477.<br /> <br />  Bisschop J, Roelofs M. Aimms-Language Reference[M]. Lulu. com, 2006. p377 -387<br /> <br /> </div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:16:58Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> One of the following cases must occur:<br /> a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> b) This NLP is infeasible. If the fixed &lt;math&gt;y^k&lt;/math&gt; is not feasible, use the following NLP problem to obtain &lt;math&gt;x^k&lt;/math&gt;<br /> <br /> [[File:function3.png|165px]]<br /> <br /> If &lt;math&gt;u \le 0&lt;/math&gt;, then former NLP is feasible. If &lt;math&gt;u &gt; 0&lt;/math&gt;, then infeasible.<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function3.png File:Function3.png 2014-05-25T20:13:27Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:10:16Z <p>Xudansha: /* Upper Bonding Subproblem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|175px]]<br /> <br /> One of the following cases must occur:<br /> a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> b) This NLP is infeasible. If the fixed &lt;math&gt;y^k&lt;/math&gt; is not feasible, use the following NLP problem to obtain &lt;math&gt;x^k&lt;/math&gt;<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T20:09:45Z <p>Xudansha: /* Algorithm */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> [[File:function2.png|180px]]<br /> <br /> One of the following cases must occur:<br /> a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution &lt;math&gt;x^k&lt;/math&gt;is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.<br /> b) This NLP is infeasible. If the fixed &lt;math&gt;y^k&lt;/math&gt; is not feasible, use the following NLP problem to obtain &lt;math&gt;x^k&lt;/math&gt;<br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function2.png File:Function2.png 2014-05-25T19:01:37Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function1.png File:Function1.png 2014-05-25T19:00:52Z <p>Xudansha: Xudansha uploaded a new version of &amp;quot;File:Function1.png&amp;quot;</p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function1.png File:Function1.png 2014-05-25T19:00:15Z <p>Xudansha: Xudansha uploaded a new version of &amp;quot;File:Function1.png&amp;quot;</p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T18:54:55Z <p>Xudansha: /* Upper Bonding Subproblem */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> First, give initial values for binary variables. In the given problem, the binary variable is &lt;math&gt;y&lt;/math&gt;. Fix all the &lt;math&gt;y&lt;/math&gt; variables at &lt;math&gt;y^k&lt;/math&gt; and solve the new non-linear problem.<br /> <br /> === Feasibility Subproblem ===<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T18:50:41Z <p>Xudansha: /* Problem Statement */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> &lt;math&gt;f(x)&lt;/math&gt; and &lt;math&gt;g(x)&lt;/math&gt; should be convex.<br /> <br /> === Upper Bonding Subproblem ===<br /> <br /> === Feasibility Subproblem ===<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T18:49:39Z <p>Xudansha: /* Problem Statement */</p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> [[File:function1.png|150px]]<br /> <br /> === Upper Bonding Subproblem ===<br /> <br /> === Feasibility Subproblem ===<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/File:Function1.png File:Function1.png 2014-05-25T18:47:05Z <p>Xudansha: </p> <hr /> <div></div> Xudansha https://optimization.mccormick.northwestern.edu/index.php/Outer-approximation_(OA) Outer-approximation (OA) 2014-05-25T18:40:53Z <p>Xudansha: </p> <hr /> <div>--[[User:Xudansha|Xudansha]] ([[User talk:Xudansha|talk]]) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014)<br /> Steward: Dajun Yue, Fengqi You<br /> <br /> <br /> <br /> == General ==<br /> <br /> Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) &lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.<br /> <br /> == Algorithm ==<br /> === Problem Statement ===<br /> &lt;math&gt;<br /> min Z=C^T y + f(x)&lt;/math&gt;<br /> &lt;math&gt;s.t. g(x) + By \le 0 &lt;/math&gt;<br /> <br /> <br /> <br /> === Upper Bonding Subproblem ===<br /> <br /> === Feasibility Subproblem ===<br /> <br /> === Master Problem ===<br /> <br /> == Convergence and Optimality ==<br /> To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.&lt;span style=&quot;font-size: 8pt; position:relative; bottom: 0.3em;&quot;&gt;&lt;/span&gt;<br /> == A Numerical Example ==<br /> <br /> == Conclusion ==<br /> <br /> == Reference ==<br />  Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339.<br />  Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.</div> Xudansha