The MIPGap parameter controls the minimal quality of the returned solution. It is an upper bound on the actual MIP gap of the final solution. It can happen that Gurobi runs until finding a solution that is significantly better than the MIP gap because it is not always possible to terminate with the given MIP gap requirement. One reason is that the gap improvement is happening in jumps rather than a continuous progression:
Recall that the gap in Gurobi is computed using the following formula:
\[\frac{\left| \text{ObjBound} - \text{ObjVal} \right|}{\left| \text{ObjVal} \right|}\]
Some decision-makers worry that they could leave money on the table by setting a positive MIP Gap tolerance ε. To alleviate that concern, please note there could be different scenarios in the optimization process:
- Sometimes, Gurobi finds the global optimal solution early on while the current MIP gap is bigger than the allowed tolerance (e.g. current MIP gap of 40% vs an ε of 0.01%), so the rest of the optimization time is spent trying to get the certificate of optimality by pushing the dual bound towards the objective value of the incumbent solution.
- Sometimes, however, Gurobi terminates the optimization run because the current MIP Gap is already within the specified tolerance, defined by ε. In such cases, the reported solution may not be the exact optimum. We then say that the incumbent solution is ε-optimal, meaning that its objective value is within ε (e.g., 0.01%) relative difference from the best possible objective value—had we continued to explore the branch-and-bound tree. Note that while better solutions could exist deeper in the tree, their existence is not guaranteed (as explained in the bullet point above).
In any case, for a given MIP Gap tolerance ε, once Gurobi is finished, you are guaranteed that the optimal solution is in the ε-neighborhood of the solution found by the solver. Moreover, for real-world applications, it is always sensible to set a positive MIP Gap tolerance since:
- Numerical Precision: Solvers use finite precision arithmetic. A zero gap can cause problems due to numerical limits.
-
Computational Time:
Achieving an exact zero gap is often time-consuming and resource-intensive.
That's why Gurobi by default uses a small, non-zero value for
MIPGapto balance solution quality and solve time, providing near-optimal results without excessive computation. - Diminishing Returns: Smaller gaps lead to marginal solution improvements but require exponentially more effort.
- Solver Limitations: Forcing a zero gap can interfere with solver heuristics, thus reducing performance.