HiGHS: MIP yields incorrect result with presolve on.
This is one of just a few solutions that are incorrect. Perhaps there is an option I can change?
subset_select_highs_in.mps.txt
Exact solution: Optimal = 44
With presolve on:
Solving report
Status Optimal
Primal bound 45
Dual bound 45
Gap 0% (tolerance: 0.01%)
Solution status feasible
45 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.01 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 21 (total)
0 (strong br.)
3 (separation)
0 (heuristics)
With presolve off:
Solving report
Status Optimal
Primal bound 44
Dual bound 44
Gap 0% (tolerance: 0.01%)
Solution status feasible
44 (objective)
0 (bound viol.)
2.23376872555e-13 (int. viol.)
0 (row viol.)
Timing 0.01 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 51 (total)
0 (strong br.)
23 (separation)
0 (heuristics)
subset_select_job3_highs-presolve-off.log subset_select_job3_highs-presolve-on.log
I only saw one LP option and these MIP options. Would one of them be appropriate?
// Options for MIP solver
bool mip_detect_symmetry;
HighsInt mip_max_nodes;
HighsInt mip_max_stall_nodes;
HighsInt mip_max_leaves;
HighsInt mip_max_improving_sols;
HighsInt mip_lp_age_limit;
HighsInt mip_pool_age_limit;
HighsInt mip_pool_soft_limit;
HighsInt mip_pscost_minreliable;
HighsInt mip_min_cliquetable_entries_for_parallelism;
HighsInt mip_report_level;
double mip_feasibility_tolerance;
double mip_rel_gap;
double mip_abs_gap;
double mip_heuristic_effort;
About this issue
- Original URL
- State: open
- Created a year ago
- Comments: 20 (13 by maintainers)
Commits related to this issue
- optimize: disable presolve for some known problems See https://github.com/ERGO-Code/HiGHS/issues/1273 — committed to Thell/bdo-housecraft by Thell a year ago
- update lastest: use presolve fixes for 1273 See https://github.com/ERGO-Code/HiGHS/issues/1273 — committed to Thell/highs-sys by Thell a year ago
Sorry, yes, the bug in these two has not yet been fixed. All your models are carefully filed in my “to be debugged” folders, so I won’t forget
So, quite a saga, but I was wrong about the “incorrect data” being the reason for the errors. However, I found out that some of the presolve reductions for your failing models were mathematically “illegal”. I’ve implemented a check to prevent such reductions, and all your failing problems solve correctly.
Since the error has implications beyond your models, I’m studying it further, but I’ll let you know when the corrected solver is available.
It’s not a matter of tolerances. I think I found a logical bug this evening.
Thanks for your efforts though. I’ll reply in more detail later. In walking the dog at the moment 😁
We’ve got a few instances where one or more bugs in presolve lead to the incorrect optimal objective. Small examples like yours are helpful. Just this one from you should be enough, as all 7 may relate to the same bug. We can find this out once the bug is fixed. However, fixing bugs in the presolve and MIP solver is tricky, as the developer is no longer working for us: she’s still cooperating with us, but has little time due to her now position.