I am using Knitro to solve an MINLP using branch-and-bound and I want to know about the reference or technique they are adopting to code their algorithm. I know that there are many applications of branch-and-bound to tackle MINLP but I couldn't find which technique they are adopting.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ artelys.com/docs/knitro/2_userGuide/bibliography.html $\endgroup$– KuifjeJan 17, 2020 at 7:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Knitro offers two variations of branch-and-bound for mixed-integer nonlinear programs. The first (and default method) is a standard branch-and-bound method that solves a continuous nonlinear optimization problem at each node by relaxing the integer variables. The second (the Quesada-Grossmann approach) solves linear programming subproblems at most nodes and only solves continuous nonlinear subproblems at select nodes. This method has easier/faster node solves, but typically requires many more nodes to prove optimality. A reference to this approach can be found in the bibliography section of the Knitro User's Manual.
Both approaches are designed for convex MINLP models and are only heuristics in the non-convex case. The choice of method is controlled through the "mip_method" user option. The Knitro branch-and-bound approach also includes heuristics for finding integer feasible points and a variety of cuts, branching strategies, etc. that can be controlled through user options.
More information can be found in the User's Manual https://www.artelys.com/docs/knitro/2_userGuide/minlp.html.
$\begingroup$
$\endgroup$
As KNITRO's manual says, it's vanilla branch-and-bound: the integer variables are relaxed to continuous, and solving that relaxed problem provides the bound for branch and bound.
Since in this case the relaxation of the problem is the problem itself made continuous, this bound is only valid if the problem is convex:
It is primarily designed for convex models, and in this case the integrality gap measure can be trusted.
