Originally posted by: mremn

Hi everyone,

I'm solving a Max problem and facing a strange behavior of Cplex: gap was increasing when cplex found a better solution. You can see the image in the attachment. Is this a bug of Cplex? Or maybe I did something wrong with my code. I'm using fixed version of Cplex Callable C 12.5.1. 

Thank you for your answers,

Ha

Originally posted by: Laci Ladanyi

You seem to have an instance where you maximize an objective, your current best dual bound is positive but your best primal solution value is negative. In such cases all sort of strange things can happen. Looking up the definition of the gap, for example, at the documentation of the relative MIP gap tolerance parameter (http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html?lang=en) you can find that it is defined as

          |bestbound-bestinteger|/(1e-10+|bestinteger|)

so if bestbound is positive, bestinteger is negative, and you find a better integer that is still negative then the gap will increase.

--Laci

Originally posted by: mremn

Thank you Laci,

So in such case, is it possible that Cplex never stops? 

Ha

Originally posted by: Laci Ladanyi

If the optimum is nonzero then eventually the sign of the best integer solution and the best dual bound will be the same, and from then on the gap will be sensible again. Also, if the optimum is 0 then as soon as a solution of value 0 is found (i.e., you "just" need to prove optimality) the relative gap will make sense again because of the 1e-10 shift in the divisor. So yes, eventually the relative gap can be used for termination. And, of course, there is the absolute gap as well that is checked for termination criteria. And if neither kicks in then sooner or later cplex will enumerate the whole tree, though it may take a while :-).

--Laci