What is the MIPGap?

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:

Please note that the MIPGap parameter is not just a termination criterion but also influences the algorithm in other parts. It may happen that the solver takes a different path and behaves differently when using a different MIPGap.

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 finishes the optimization run (because the current MIP Gap is already within tolerances as defined by ε) and reports a solution that may not be the optimal solution. In this case, we say the incumbent solution is ε-suboptimal, as the objective value it attains is at most ε (e.g. 0.01%) worse from the value attained by other solutions that could be found if we continue to explore the branch-and-bound tree (although there's no guarantee that such solutions exist, as already 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 to manage the tradeoff between having a feasible solution that is good enough for the use-case and the computation time required to explore the branch-and-bound tree (many times it's prohibitive to exhaust that search).

Further information

• Is there a way to predict how long it will take Gurobi to solve a MIP?
• Why are there large or increasing MIP gap values?