Tuesday, July 31, 2012

MIP Gap increasing

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:

image

Many solvers (e.g. Cplex) use:

image

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):

image

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

image

is really small.