MIP Gap not decreasing

Here is a small fragment of a Cplex log:

Nodes                                         Cuts/    Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap    3186  2520     -666.6217  4096      956.6330     -667.2010  1313338  169.74%    3226  2560     -666.6205  4097      956.6330     -667.2010  1323797  169.74%    3266  2600     -666.6201  4095      956.6330     -667.2010  1335602  169.74% Elapsed real time = 2801.61 sec. (tree size = 77.54 MB, solutions = 2) *  3324+ 2656                         -125.5775     -667.2010  1363079  431.31%    3334  2668     -666.5811  4052     -125.5775     -667.2010  1370748  431.31%    3380  2714     -666.5799  4017     -125.5775     -667.2010  1388391  431.31%    3422  2756     -666.5791  4011     -125.5775     -667.2010  1403440  431.31%

Usually we expect the gap to decrease while the MIP solver is working its way. Here we see a different behavior. Because we go through zero the gap% is actually increasing here.

I believe the gap calculation used by Cplex is:

Obviously this is sensitive w.r.t. to the sign of BestInteger. Of course in practice we don’t see this behavior very often (in many models BestInteger and BestNode have the same sign).