Originally posted by: vincentve

Dear All,

as far as i know the relative gap for a MIP solution should be non-negative by definition. However, i get the following results using Cplex 12.1.

• getStatus()==OPTIMAL
• getCplexStatus()==OPTIMAL
• getObjValue()<getBestObjValue() which should, again, not be i think
• getMIPRelativeGap()<0

In some sense these results are consistent.

Up to now i thought, that

• getObjValue() delivers the objective value of the best feasible solution found
• getBestObjValue() delivers the best lower bound (talking about minimization problems)
• getMIPRelativeGap()=(getObjValue()-getBestObjValue())/getBestObjValue()...(this actually holds in my case).

Am i mistaken at some point?
If not, is it a know problem?
Any solutions to that?

Thanks in advance,
Dirk
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> vincentve wrote:
> Dear All,
>
> as far as i know the relative gap for a MIP solution should be non-negative by definition. However, i get the following results using Cplex 12.1.
>
> - getStatus()==OPTIMAL
> - getCplexStatus()==OPTIMAL
> - getObjValue()<getBestObjValue() which should, again, not be i think
> - getMIPRelativeGap()<0
>
> In some sense these results are consistent.
>
> Up to now i thought, that
> - getObjValue() delivers the objective value of the best feasible solution found
> - getBestObjValue() delivers the best lower bound (talking about minimization problems)
> - getMIPRelativeGap()=(getObjValue()-getBestObjValue())/getBestObjValue()...(this actually holds in my case).
>
> Am i mistaken at some point?
> If not, is it a know problem?
> Any solutions to that?
>
> Thanks in advance,
> Dirk

Assuming you are minimizing, everything you said is true, under
perfect arithmetic. However, if your model is ill conditioned,
then a negative mipgap is possible in finite precision.

Can you reproduce this with interactive CPLEX and a SAV file of the model in question? In other words, add a call to IloCplex::exportModel after the solve() call that yielded the above results. Then, start up interactive CPLEX, read in the SAV file, and solve (using any non default parameter settings that you used in your program if they are essential to reproducing the behavior). Check the solution quality, and
also check the problem statistics to see if the model has mixtures of large and small numbers that might lead to ill conditioning.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: vincentve

Thanks a lot for your help. I updated to Cplex 12.2 meanwhile and the problem vanished. Also, following your suggestions would mean to reinstall 12.1....so, i think i leave it be.

Maybe you can tell me the following: does "a model being ill conditioned" mean that the matrix' condition number is large? Probably it does not rule out anything but coefficients in my model are not exceeding 40 and integer....so imho likelihood for rounding problems should be very low.

Anyway, thanks again, i appreciate your help.

Dirk
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Modest and evenly scaled coefficients do not preclude ill-conditioning. Fill a 2x2 matrix with the value 1 in every entry, then change one of the off-diagonal entries to 1-epsilon (epsilon small and positive) and check the condition number.

CPLEX 12 will let you collect statistics on the kappa values (condition numbers) of the basis matrices encountered, so you can put to the test the question of whether conditioning is an issue in your problem.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

I agree with Paul that you don't need very large (or even very small coefficients) to have an ill conditioned problem. But, the fact that your model has reasonable coefficients improves the odds that ill conditioning is not the issue. Since you have
upgraded to CPLEX 12.2, you can also make use of the new MIP Kappa feature which collects statistics on the various node LP
basis condition numbers. That should help you assess the
conditioning level.

I agree that you shouldn't bother going back to 12.1 just to try to track this down. But, if you are willing to upload the SAV file of the model, I will see if I can reproduce the negative MIP gap result. While the absence of this behavior in 12.2 is encouraging, it could have occurred due to a change in path rather than a bug fix. Or, if the model is ill conditioned, a change in path would be enough to change the results as well.
#CPLEXOptimizers
#DecisionOptimization