Why are there large or increasing MIP gap values?

Sometimes in the Gurobi log, you might see an increase in the gap. In the example below, the gap increases from 113% up to 4171%, before it decreases again.

   Nodes     |    Current Node   | Objective       Bounds     |    Work
 Expl Unexpl |  Obj Depth IntInf | Incumbent   BestBd     Gap | It/Node Time

  1503  1467 -283.00000  284  285 2160.99979 -285.00000   113%   609  127s
H 1968  1870                    1858.0000000 -285.00000   115%   662  145s
[...]
  4854  3038 -257.55772  357  368   13.00000 -285.00000  2292%  1044  919s
H 4924  2950                       8.0000000 -285.00000  3662%  1050  919s
  5130  3120 -246.16119  393  407    8.00000 -285.00000  3662%  1044  942s
H 5317  3172                       7.0000000 -285.00000  4171%  1059  942s
  5630  3377 infeasible  468         7.00000 -285.00000  4171%  1042  969s
  5716  3420 -285.00000   21  472    7.00000 -285.00000  4171%  1058  993s
  5937  3615 -284.00000   77  403    7.00000 -285.00000  4171%  1057 1024s
H 5938  3615                       2.0000000 -285.00000      -  1057 1024s
[...]
  8623  6061 -213.60040  141  748    2.00000 -285.00000      -  1219 1487s
H 8848  6207                    -103.0000000 -285.00000   177%  1210 1487s
  9149  6446 infeasible  191      -103.00000 -285.00000   177%  1199 1561s
  9675  6904 -280.00000  114  725 -103.00000 -285.00000   177%  1182 1626s
[...]
H18133 14145                    -118.0000000 -285.00000   142%  1015 3309s
 18258 14238 -264.98878  195  590 -118.00000 -285.00000   142%  1020 3408s
 18590 14461 -198.90509  211  630 -118.00000 -285.00000   142%  1027 3622s
H18749   815                    -284.0000000 -285.00000  0.35%  1025 3622s

This is expected behavior in certain cases. The relative MIP gap is computed as

\[\frac{\left| \text{ObjBound} - \text{ObjVal} \right|}{\left| \text{ObjVal} \right|}\]

where ObjBound and ObjVal are the MIP objective bound (column BestBd) and incumbent solution objective, respectively.

If primal and dual bound have different signs, the interpretation of the MIP gap value may not make sense.

When the gap is larger than 9999%, Gurobi will not print it in the log in order to avoid formatting issues. In these cases a - is shown; note that- is also displayed for models without an incumbent solution.

It would be possible to add a constant to the objective function that is large enough to make sure that the objective is always positive. Doing this would, however, change the meaning of the gap.

Further information

• How do I pass an objective bound to Gurobi?