Branch-and-Bound integer/float
Answered
Hi.
Gurobi is using the branch-and-bound/cut-method for optimization. According to literature the aim of this method is to find an optimal integer solution by going through the search tree. But the solution of my optimisation is of the data type float. So does Gurobi return the optimal solution solved with e.g. simplex unless the user tells the optimizer that some specified variables should be integers or am I wrong about that?
-
Hi Tessa,
Working with floating numbers instead of true integers is common practice in numerical algorithms. This is due to the fact that machine precision is not infinite. Thus, optimization solvers work with integrality tolerances (IntFeasTol in Gurobi). As a result, it is possible that the optimal solution value of an integer or a binary variable is reported as, e.g., 0.999999 instead of 1. Recently, Gurobi introduced the IntegralityFocus parameter to tackle this issue and spend more effort to determine true integer values for binary and integer variables. However, this comes with a price hurting the overall performance.
So does Gurobi return the optimal solution solved with e.g. simplex unless the user tells the optimizer that some specified variables should be integers or am I wrong about that?
If your problem does not contain any discrete variables, then Gurobi will provide the solution found by one of the Simplex algorithms or the Barrier algorithm (depending on which one is fastest for a given instance). If your problem has discrete variables, then feasible points are determined via various heuristics which try to make the solution values of discrete variables as integer as possible and accept non-integer values up to the tolerance given by the IntFeasTol parameter.
If you are interested in the topic of numerical accuracy, I recommend having a glance at the book by Nicholas Higham on Accuracy and Stability of Numerical algorithms for more insight.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment