Incorrect Improvement in Solution After Adding a Cut in Iterative Process

sertalpbilal commented 1 month ago

Hi,

I'm encountering an unexpected behavior when using the HiGHS solver. In a two-step iterative process, I solve a problem and then add a cut in the second iteration. Theoretically, this should result in the same or a worse solution compared to the first iteration, as all the original constraints remain unchanged and the cut adds an additional restriction. However, the solver returns a better solution after adding the cut, which clearly seems incorrect.

I attached both MPS files in a zip file. mps_files.zip

HiGHS Version

1.7.2 (Windows)

Steps to Reproduce:

Solve both MPS files using HiGHS.
Observe that the first file (with _0.mps) gives an objective value of -288.521, while the second one (_1.mps) gives -288.654

Relevant Details

I use an options file with only mip_rel_gap = 0 in it. But, the issue happens regardless of this file.
CBC solver gives an objective value of -289.269406 for both files.

Logs

Solve 1:

Status            Optimal
Primal bound      -288.5210454
Dual bound        -288.5210454
Gap               0%
Solution status   feasible
-288.5210454 (objective)
0 (bound viol.)
3.5527136788e-15 (int. viol.)
0 (row viol.)
Timing            302.57 (total)
0.40 (presolve)
0.00 (postsolve)
Nodes             1104
LP iterations     452760 (total)
206095 (strong br.)
13946 (separation)
28275 (heuristics)

Solve 2:

Status            Optimal
Primal bound      -288.6548272
Dual bound        -288.6548272
Gap               0%
Solution status   feasible
-288.6548272 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing            82.14 (total)
0.98 (presolve)
0.00 (postsolve)
Nodes             101
LP iterations     223069 (total)
132909 (strong br.)
7133 (separation)
23063 (heuristics)

odow commented 1 month ago

CBC solver gives an objective value of -289.26906 for both files.

Gurobi concurs with -289.269406

jajhall commented 1 month ago

Sorry about this. Probably due to an error in presolve. I'll investigate further in due course

sertalpbilal commented 1 month ago

Looks like it works with HiGHS 1.2.0. I am able to get the same objective (-289.269406).

Solving report
  Status            Optimal
  Primal bound      -289.269406
  Dual bound        -289.269406
  Gap               0%
  Solution status   feasible
                    -289.269406 (objective)
                    0 (bound viol.)
                    1.16018306073e-13 (int. viol.)
                    0 (row viol.)
  Timing            72.25 (total)
                    0.42 (presolve)
                    0.00 (postsolve)
  Nodes             208
  LP iterations     221430 (total)
                    133567 (strong br.)
                    5321 (separation)
                    20564 (heuristics)

jajhall commented 1 month ago

This is probably because bug fixes to the MIP presolve since 1.2.0 have caused the 1.7.2 MIP presolve to take a different path and exposed a bug. In other words, it's very unlikely to be a regression.

What happens with random_seed=1?

sertalpbilal commented 1 month ago

With random_seed=1 I still get the incorrect objective (-288.5210454)

jajhall commented 1 month ago

And if you switch off presolve?

sertalpbilal commented 1 month ago

When presolve is off (version 1.7.2), I get the correct result, so you are right, it looks like a presolve issue. It takes much longer (2181 seconds) to solve as expected, but finds the same solution as CBC and Gurobi.

Solving report
  Status            Optimal
  Primal bound      -289.269406
  Dual bound        -289.269406
  Gap               0%
  Solution status   feasible
                    -289.269406 (objective)
                    0 (bound viol.)
                    6.76125821997e-14 (int. viol.)
                    0 (row viol.)
  Timing            2181.20 (total)
                    0.03 (presolve)
                    0.00 (postsolve)
  Nodes             4552
  LP iterations     2350958 (total)
                    798769 (strong br.)
                    97653 (separation)
                    135297 (heuristics)

fwesselm commented 2 weeks ago

@sertalpbilal I am trying to investigate this, but the reproduction examples are rather large. By any chance do you have a smaller instance to reproduce this? The answer is most probably no, but I wanted to ask anyway...

sertalpbilal commented 2 weeks ago

@fwesselm I have attached 5 iterations from a smaller solve (~1.8 MB each) and pasting the objectives (score column) we get below. Iter_0 should be without a cut, Iter_1 is after cutting the best solution, and so on.

iterations.zip

fwesselm commented 2 weeks ago

@fwesselm I have attached 5 iterations from a smaller solve (~1.8 MB each) and pasting the objectives (score column) we get below. Iter_0 should be without a cut, Iter_1 is after cutting the best solution, and so on.

iterations.zip

Thank you. For iter_0 the problematic presolve reduction is number 2454. I will continue investigating.

ERGO-Code / HiGHS