Incorrect Optimal Solution by calling Cbc from pulp

[zxt5]

I am using pulp calling Cbc to solve (maximize) this MIP problem seed.txt and getting the result:

Solver: PULP_CBC_CMD
Status: Optimal
Objective: -3083.860014227
x0 = 7.9199113, x1 = 20.0, x10 = -3.323801, x11 = 23.0, x12 = -22.313379, x2 = 25.517974, x3 = -5.8030527, x4 = 18.000674, x5 = 20.055656, x6 = 5.0, x7 = 20.0, x8 = 5.0, x9 = 14.161162

All other solvers I have tried (HiGHS, SCIP, GLPK, GUROBI) returned the following results with only floating-point difference:

Status: Optimal
Objective: -3063.738381768596
x0 = 7.446534162454931, x1 = 19.0, x10 = -4.189205715504795, x11 = 22.0, x12 = -21.724589725764098, x2 = 25.19341851184199, x3 = -6.039803641320515, x4 = 17.563227149705163, x5 = 19.232812684092806, x6 = 5.0, x7 = 20.0, x8 = 5.0, x9 = 13.937354378089148,

I'm not sure if this inconsistency is expected, I would appreciate any suggestions or instructions.

[jjhforrest]

master gets correct result but I can reproduce error using stable. Will look into it.

[zxt5]

Thanks for your quick reply.

[jjhforrest]

It is a tolerance issue - which can happen if you are unlucky enough - on master as well as stable.
If a variable e.g. x1 is at 20.2 and the code sees that forcing it down to 20.0 costs 100 then it knows that forcing it down to 19.0 would cost at least 600. If that would make the objective worse than the best so far, then it can put a lower bound of 20 on x1.

There are tolerances to avoid errors but in this unlucky case x1 had a value of 20.000003. 3.0e-6 is just more than the integer tolerance and as this variable had not been branched on, the code wanted to get an idea about how expensive changing the variable might be. Forcing it to 20 cost 0.001 and extrapolating the code saw that forcing it to 19 would cost too much. In reality forcing it to 19 would cost 15 (which would give an objective of -3063.7). Dealing with tolerances is tricky and this case was unlucky as about three computations went the wrong way.

I am changing the code so that those computations will not be used unless the variable is much more away from an integer.

•            if (distance < 5.0) {
  

•            if (distance < 5.0 && down > 1.0e-3) {
               double newLower = ceil(value - distance);
  

[zxt5]

Thanks for your explanation and the quick fix!