Inconsistent optimal results by enable/disable presolve

[zxt5]

Not sure if this is a duplicate of #2171.

HiGHS produces different results for seed.mps.txt with --presolve on and off.

Solver: highs --presolve on
Status: Optimal
Objective: -26760.686634486985
x0 = 16.9701093661577, x1 = 80.6041223372959, x10 = -69.3245709660754, x11 = 28.5413466358537, x12 = 148.0, x13 = -195.0, x14 = -164.0, x2 = -81.943907445893, x3 = -8.0, x4 = -114.9309127668198, x5 = -146.0, x6 = -49.0801884097884, x7 = 75.0, x8 = 187.7495937926897, x9 = 200.0,

Solver: highs --presolve off
Status: Optimal
Objective: -26770.807548851153
x0 = 15.8303099899044, x1 = 80.7145047599353, x10 = -69.6001380898785, x11 = 28.7929515268995, x12 = 148.0, x13 = -195.0, x14 = -166.0, x2 = -81.0734607384476, x3 = -8.0, x4 = -114.5400541325929, x5 = -147.0, x6 = -47.9633713958449, x7 = 75.0, x8 = 187.4473933184731, x9 = 200.0,

For reference, the results produced by CBC, scip, and gurobi are -26770.80..

[jajhall]

Probably the same issue. What do you think, @fwesselm?

[fwesselm]

Probably the same issue. What do you think, @fwesselm?

I agree. I am in process of debugging #2171.

[zxt5]

Just got a similar case seed.mps.txt seems because of the same issue, but not 100% sure. So attach it here for reference.

root@b9f8d0525121:/tmp/fuzz-mip# highs --model_file seed.mps --presolve on
      . . .
Solving report
  Model             seed
  Status            Optimal
  Primal bound      -35644.2863263
  Dual bound        -35644.2863263
  Gap               0% (tolerance: 0.01%)
  P-D integral      4.49616247444e-05
  Solution status   feasible
                    -35644.2863263 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.07 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     33 (total)
                    0 (strong br.)
                    8 (separation)
                    0 (heuristics)
root@b9f8d0525121:/tmp/fuzz-mip# highs --model_file seed.mps --presolve off
     . . .
Solving report
  Model             seed
  Status            Optimal
  Primal bound      -35653.394378
  Dual bound        -35656.3979176
  Gap               0.00842% (tolerance: 0.01%)
  P-D integral      9.84603038411e-05
  Solution status   feasible
                    -35653.394378 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.26 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 1
  Nodes             6
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     134 (total)
                    28 (strong br.)
                    25 (separation)
                    37 (heuristics)

[zxt5]

Just test this case on latest branch which has merged the fix of #2171.
The issue still exists. So I am not sure it's a duplicate of 2171.

[fwesselm]

It looks like an invalid fixing is performed in HighsMipSolverData::finishAnalyticCenterComputation(). I am attaching a solution file for debugging and will continue investigating.

issue-2173.sol.txt

[fwesselm]

The optimal solution for the analytic center LP after the restart has at least one integer variable at its bounds, which seems to cause the incorrect fixing. I am attaching the MPS file.

issue-2173_ac_restart.mps.txt

[jajhall]

Interesting: perhaps it's not properly centred. @filikat added proper centring to IPX a while ago, so maybe we should try that for this instance. The proper centring code should always be used, but I'd not wanted to perturb the MIP solver. Clearly we're doing that frequently now, and have proper regression testing

[fwesselm]

Thanks for the suggestion @jajhall. Two other IPM codes I tried on this model returned "more centred" solutions (which would not yield the invalid fixing).

[fwesselm]

Setting run_centring to true in HighsMipSolverData::startAnalyticCenterComputation() resolves the issue.

[Opt-Mucca]

@fwesselm Support enabling run_centering for this (if it does what it sounds like)! @jajhall could this have any potential ramifications like enabling presolve does for the analytic center solve?