As the discussion in http://lists.gnu.org/archive/html/help-glpk/2012-07/msg00104.html indicates a MIP relative gap can increase. See also http://yetanothermathprogrammingconsultant.blogspot.com/2011/06/mip-gap-not-increasing.html. There are a few definitions around. GAMS likes to use:
Many solvers (e.g. Cplex) use:
This looks like a big problem, but when we say “stop at 5% gap” both definitions are quite close. Gurobi seems to use (https://groups.google.com/forum/?fromgroups#!topic/gurobi/RKbC1qiFZ-A):
which is almost the same.
Do we really need an alternative definition as suggested in http://lists.gnu.org/archive/html/help-glpk/2012-07/msg00104.html. I would not think so. The reason is that for almost all models the current definitions work just fine: the gap will only decrease. Only in the case where one bound is at the other side of 0 than the other bound we are somewhat in trouble. However the number of models where
is really small.