ERGO-Code
Potential issues with presolve: incorrect 'optimal' solution and incorrect infeasibiliy detection
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
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.
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
I upgraded highs_jll package and tried with the latest version (1.7.2) and I am afraid the optimal solution of the problem above is still cut by the presolve. I get 102.677587727 with presolve and 133.377025318 without it.
We have only the following parameters set. I guess the tolerances might be taking part in this bug but I know nothing about the presolve routine.
"mip_rel_gap" => 1.0,
"mip_abs_gap" => 0.01,
"presolve" => "off"/"on" , # https://github.com/ERGO-Code/HiGHS/issues/1725#issuecomment-2179281914
"mip_heuristic_effort" => 0.4,
"mip_feasibility_tolerance" => 1e-5,
"primal_feasibility_tolerance" => 1e-7,
Can't see them playing part in this but for completeness, we also have the following:
"time_limit" => 20,
"output_flag" => true,
"log_to_console" => true,
Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [1e-02, 1e+02]
Cost [2e+00, 1e+06]
Bound [1e+00, 1e+02]
RHS [5e-01, 9e+02]
Presolving model
1104 rows, 1056 cols, 3541 nonzeros 0s
833 rows, 887 cols, 3083 nonzeros 0s
743 rows, 797 cols, 2669 nonzeros 0s
Solving MIP model with:
743 rows
797 cols (102 binary, 0 integer, 0 implied int., 695 continuous)
2669 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 18288.67871 -inf inf 0 0 0 0 0.0s
0 0 0 0.00% 133.3770253 -inf inf 0 0 2 405 0.0s
C 0 0 0 0.00% 133.3770253 41.44289993 221.83% 982 119 12 564 0.0s
L 0 0 0 0.00% 102.6775877 102.6775877 0.00% 1460 176 12 683 0.1s
Solving report
Status Optimal
Primal bound 102.677587727
Dual bound 102.677587727
Gap 0% (tolerance: 1%)
Solution status feasible
102.677587727 (objective)
0 (bound viol.)
7.44959649523e-14 (int. viol.)
0 (row viol.)
Timing 0.08 (total)
0.01 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 696 (total)
0 (strong br.)
278 (separation)
11 (heuristics)
vs.
Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [1e-02, 1e+02]
Cost [2e+00, 1e+06]
Bound [1e+00, 1e+02]
RHS [5e-01, 9e+02]
Presolve is switched off
Solving MIP model with:
1189 rows
1974 cols (270 binary, 0 integer, 0 implied int., 780 continuous)
4471 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 18288.67871 -inf inf 0 0 0 0 0.0s
0 0 0 0.00% 133.3770253 -inf inf 0 0 2 444 0.0s
R 0 0 0 0.00% 133.3770253 129.4747983 3.01% 2146 243 93 832 0.1s
T 0 0 0 0.00% 133.3770253 133.3770253 0.00% 2532 278 93 893 0.1s
Solving report
Status Optimal
Primal bound 133.377025318
Dual bound 133.377025318
Gap 0% (tolerance: 1%)
Solution status feasible
133.377025318 (objective)
0 (bound viol.)
5.46187775008e-08 (int. viol.)
0 (row viol.)
Timing 0.14 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 893 (total)
0 (strong br.)
441 (separation)
0 (heuristics)
Actually, I just checked and it looks like it is indeed related to tolerance. If I don't set "mip_feasibility_tolerance" => 1e-5,, HiGHS returns the same solution (or more precisely the same objective function value) with and without presolve.
So it looks like the issue was not that we were on 1.7.0 or 1.5.3 but that we have a non-standard mip_feasibility_tolerance.
I hope these observations will be useful for debugging assuming this is bug.