Does anybody know why in the outer approximation approach for MINLP it is not necessarily/needed to solve MILP to optimality? What is the rationale or explanation behind it?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
I think this link has a reasonable description of Outer Approximation approach for MINLP
The outer approximation MILP is a relaxation of the MINLP. Any lower bound on the MILP outer approximation is also a lower bound on the MINLP. Therefore a lower bound on the outer approximation MILP can be used as a lower bound for the MINLP, without requiring it be solved to optimality.
answered Dec 9, 2022 at 12:35
-
$\begingroup$ I might be mistaken, but how can we obtain the lower bound for MINLP if we do not solve MILP to optimality? $\endgroup$ Dec 9, 2022 at 20:05
-
$\begingroup$ Presuming minimization is being performed: As the MILP solution progresses, it produces a lower bound based on continuous relaxation, and as soon as it finds an (integer) feasible solution to the MILP,, an upper bound based on the objective value of the best feasible point (the incumbent) found thus far. The gap is the difference between the lower bound and the upper bound. Even if the gap is not zero or small, the lower bound is still valid as a lower bound of the MILP, and hence of the MINLP, because it is the objective value of the continuous relaxation of a MILP relaxation of the MINLP. $\endgroup$ Dec 9, 2022 at 20:17
-
$\begingroup$ I am still not getting it. "Therefore a lower bound on the outer approximation MILP can be used as a lower bound for the MINLP, without requiring it be solved to optimality." If you do not solve to optimality, you do not get a lower bound; you get an upper bound. It does not explain how you can get any bound from the MILP if you do not solve to optimality. The MILP is a relaxation; therefore any solution (that is not optimal) is neither a lower bound, nor an upper bound. $\endgroup$ Dec 9, 2022 at 23:22
-
$\begingroup$ Assume minimization. Optimal objective value of outer approximation is a lower bound on optimal objective value of MINLP. Lower bound on optimal objective value of MILP, obtained by continuous relaxation of the MILP, is therefore a lower bound of optimal objective value of MINLP. This concept is very simple. $ x \le y \le z$, therefore $x \le z$., where z is optimal objective value of MINLP, y is optimal objective value of MILP relaxation of MINLP, and z is lower bound of MILP based on continuous relaxation. If z is far below optimal objective value of MILP, it's not a tight bound on z. $\endgroup$ Dec 9, 2022 at 23:56
-
$\begingroup$ Is x represent the lower bound of MILP based on continuous relaxation in the inequality? If yes, what do you mean by that? x is the optimal solution of the continuous relaxation of the MILP? Or something else? $\endgroup$ Dec 10, 2022 at 0:19