Does the Gurobi MIP Solver use safe bounds?
Answered
Hi,
I am working with the Bin Packing Problem, using a branch-and-price algorithm. There are instances that feasible tolerances of the Gurobi do not allow me solves completely the linear relaxation. That is, exists columns with reduced cost of absolute value less than 10^-9, and simplex does not pivot these columns.
Because of this, the root "optimal" solution can have the value X + c*10^-8, where X is the real optimal value and c is a constant greater than 1. This is expected since the dual solution is infeasible. There are ways to calculate a valid lower bound, such as the dual lagrangian lower bound or the dual safe bounds.
My doubt is, does the Gurobi MIP Solver uses safe bounds? If I pass the complete formulation to Gurobi, is guaranteed that it will not prune incorrectly a node in branch-and-bound tree because the simplex is unable to solve to optimality the relaxation?
Or does the Gurobi not guarantee correctness in instances with numerical issues?
Regards,
Renan
-
Hi Renan,
Gurobi will always try to be numerically as accurate as possible even for numerically questionable models. However, for numerically difficult models, Gurobi cannot guarantee 100% correctness due to computational tolerances and machine accuracy. For your particular example, it is very likely that Gurobi will perform the correct computations but it is not guaranteed due to numerical instability of the model. You could try experimenting with the parameters: FeasibilityTol, IntFeasTol, OptimalityTol, NumericFocus, and IntegralityFocus to increase Gurobi's computational accuracy.
In cases like this, it is always best to improve the numerical properties of your model to fight the source of the issue instead of only fighting the symptoms via parameter settings. You can find more information about tackling numerical issues in our Guidelines for Numerical Issues.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment