Potential issues with presolve: incorrect 'optimal' solution and incorrect infeasibiliy detection
Opened this issue · 10 comments
Greetings,
I have two problems where HiGHS returns incorrect results. In the first problem the solution returned is suboptimal and in the second it is incorrectly reported as infeasible. Turning presolve off avoids the potential issue(s).
TwoProblems.zip
With latest:
- First (
1725a.mps) is incorrectly identified as infeasible in presolve, and solved correctly with--presolve=off. Error is in reduction 851/861 - First (
1725b.mps) gets wrong optimal objective value of-4987010.44031rather than-4987029.63936, with the latter obtained when--presolve=off. Error is in reduction 850/971
Sure, I've got marking to do for a few more days
I'm not sure if it would have been better to create a new issue but I suspect mine is another manifestation of this issue (please let me know if you prefer a separate issue).
Optimizing model.mps.txt gives the following values with different solvers under different presolve settings.
We noticed the difference while upgrading from 1.5.3 to 1.7.0 so included that one in the table as well.
Everyone agrees on the optimal objective function values if the presolve is off but HiGHS deviates from the optimal significantly if the presolve is active.
| Solver | Presolve-on | Presolve-off | ||
|---|---|---|---|---|
| BestBound | BestSol | BestBound | BestSol | |
| HiGHS-1.5.3 | 112.85649849700943 | 112.85649849700943 | 132.63375308481827 | 132.63375308481827 |
| HiGHS-1.7.0 | 115.3379075077637 | 115.3379075077637 | 132.6337530848185 | 132.6337530848185 |
| Gurobi-11.0.2 (from lp) | 132.6337531104 | 132.6337530848 | 132.6337530848 | 132.6337530848 |
| Gurobi-11.0.2 (from mps) | -132.6337531349 | -132.6337531016 | -132.6337530848 | -132.6337530848 |
I couldn't try on 1.7.1 as the model is created in julia and the latest version of highs.jl points to 1.7.0.
Here are at the solver logs:
gurobi-lp-presolve-off.log
gurobi-lp.log
gurobi-mps-presolve-off.log
gurobi-mps.log
highs-1.5.3-presolve-off.log
highs-1.5.3.log
highs-1.7.0-presolve-off.log
highs-1.7.0.log
Thanks. There are bugs in the MIP presolve that we are steadily fixing. This can be added to the instances @fwesselm
Thanks. There are bugs in the MIP presolve that we are steadily fixing. This can be added to the instances @fwesselm
I just tried the latest branch, and this seems to be fixed:
Solving report
Status Optimal
Primal bound -132.633753085
Dual bound -132.633753085
Gap 0% (tolerance: 0.01%)
Solution status feasible
-132.633753085 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 1.53 (total)
0.07 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 677 (total)
0 (strong br.)
237 (separation)
36 (heuristics)
This is great news @fwesselm
This might be due to differences in compute environment but one thing that I want to flag is that the total solver duration is very different between your output and mine (1.53s vs. 0.06s).
I wonder if reading from MPS versus creating the model directly from julia has any role here.
This is great news @fwesselm
This might be due to differences in compute environment but one thing that I want to flag is that the total solver duration is very different between your output and mine (1.53s vs. 0.06s).
I wonder if reading from MPS versus creating the model directly from julia has any role here.
Oh, yes, I did not pay attention to the running times. I built in debug mode, which will be much slower.
Yes, solving in debug takes 1.02s for me, and 0.16s in release
I just tried the
latestbranch, and this seems to be fixed:
Hopefully, although fixes to presolve may cause the sequence of reductions to change and avoid the error