Does the Gurobi MIP Solver use safe bounds?

Answered

Renan Fernando Franco da Silva

March 30, 2023 13:22 Edited

• 
• 
• 

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

 

Related to

• Numerics

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 16, 2025 23:41

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jaromił Najman

  • Gurobi Staff

  March 21, 2022 08:33 Edited

  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

Post is closed for comments.