ERGO-Code
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;
If there's an error in presolve - and there are bugs to fix - then run with presolve=off
Thanks for the quick reply @jajhall.
I wasn't thinking there was an error. I was thinking I needed to tweak an option but I'm too ignorant of the api to figure out which options would help here.
Do you think there might be an error? Is there something I could provide that might help in tracking it down?
Edit: I can provide 7 samples similar to the one described above if that will help identify the bug.
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.
subset_select_highs_in.mps.txt isn't the right file, as I get the same optimal objective value (of 39) with/without presolve, and with Gurobi. However, the log file make the (real) model look useful for debugging
Sorry about that. In the samples below dataset A is the same dataset as in the previous example, I just copied the wrong values for the constraints, the one that matches the solution text given in the first post is the A_on_45_off_44 mps.
These are from MIP models with integer cols and bool bounds, the letter represents the dataset used, the on and off values represent the primal bound with preset=on, preset=off respectively. The preset=off values match expected values as given by exact calculation.
subset_select_A_on_42_off_40.mps.txt subset_select_A_on_43_off_41.mps.txt subset_select_A_on_45_off_44.mps.txt subset_select_A_on_50_off_49.mps.txt subset_select_A_on_58_off_55.mps.txt subset_select_A_on_60_off_57.mps.txt subset_select_B_on_139_off_138.mps.txt subset_select_C_on_153_off_152.mps.txt
I've made some progress: if the presolved MIP is saved and then solved with --presolve=off, the the correct objective is found for all your instances.
It's not a fix, but it does indicate that I was looking in the wrong place for a bug!
@jajhall your comment got me to thinking that if saving->loading->solving the presolved MIP worked then the earlier assumption about a bug could be wrong too we could just go back to my ignorance of the api/options. So, I started setting each option in turn to its extremes and found that mip_feasibility_tolerance solved all of them and I started backing off from that...
@ 1e-04 it got all but two of them.
So should this just be chalked up to user ~~error~~ ignorance or would you expect the solver to adjust/find these cases?
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 😁
I've been working a lot on this for the past few days, and have learned more about presolve, particularly ours!
If the presolved problem is saved, and then solves to give the right objective, it doesn't even mean that the reductions are all correct. It's possible that the MIP may have been reduced to one with the same optimal objective. However, an incorrect reduction can mean that there are errors in transforming a feasible point for the reduced problem to a point for the original problem - and that's what was happening. In trying to track down where the error in transforming the point ocurred, I found an error in some data used for checking whether two potential parallel columns had the same number of nonzeros. As soon as I corrected the check - just now - the MIP solver (with presolve on) gets the right answer to subset_select_A_on_42_off_40.mps.txt.
Why was there no code to check that the checking data were correct? Well the MIP presolve and solve were developed by someone who, almost always, writes correct code without the need for such checking. Which is barely credible given the complexity, sophistication and performance of the MIP code.
I still have to correct the update of the checking data tomorrow, but that's easy.
The dog's happy, too!
So, here's how your problems stack up now
- a-42-40.mps Solves correctly with parallel columns fix
- a-43-41.mps
- a-45-44.mps
- a-50-49.mps Solves correctly with parallel columns fix
- a-58-55.mps
- a-60-57.mps
- b-139-138.mps Solves correctly with parallel columns fix
- c-153-152.mps Solves correctly with parallel columns fix
The others still give the same errors, but the incorrect data may well affect other places in presolve
😅 That sounds like some serious digging! Thanks for taking a keen interest in it.
I'm pleased that the test datasets are coming in useful and even more please that the dog is happy too (it always helps) :)
I look forward to hearing more about the details as I continue to scratch the surface of understanding in this arena.
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.
Should this issue be closed?
Running HiGHS 1.5.3 [date: 2023-05-23, git hash: 3105f7735]
These two still exhibit the same differing results with presolve on and off...
subset_select_B_on_139_off_138.mps.txt subset_select_C_on_153_off_152.mps.txt
yet, your https://github.com/ERGO-Code/HiGHS/issues/1273#issuecomment-1532269604 indicates that you had this resolved. Perhaps something didn't make it into the merge?
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
Hi all,
It seems like I have the same issue. I was not sure whether I should create a new issue or use this one. I somehow chose to group the theme.
The file is fail_highs.lp and contains a purely binary problem arising from a Dantzig-Wolfe reformulation of a GAP instance.
Using command line, I get the following output:
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
MIP master has 44 rows; 494 cols; 6072 nonzeros; 492 integer variables
Presolving model
44 rows, 492 cols, 6072 nonzeros
44 rows, 176 cols, 1700 nonzeros
28 rows, 5 cols, 68 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
WARNING: Solution with objective 798 has untransformed violations: bound = 0; integrality = 0; row = 1 (row 22[con23])
Solving report
Status Optimal
Primal bound 798
Dual bound 798
Gap 0% (tolerance: 0.01%)
Solution status infeasible
798 (objective)
0 (bound viol.)
0 (int. viol.)
1 (row viol.)
Timing 0.05 (total)
0.05 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 0 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
ERROR: MIP solver claims optimality, but with num/sum/max primal(2/2/1) infeasibilities
Hope that helps :-)
Thks.
ps: if there is a way to detect when this happens through the C++ API, I'm happy to learn it as well.
hello,
For subset_select_B_on_139_off_138.mps.txt and subset_select_C_on_153_off_152.mps.txt.
I doubt these bugs due to the shrinkproblem in the HPresolve.cpp, so, I tried to execute more shrinkproblem, when presolve back to the main while loop. Interesting, these bugs are solved, but I am confused about what has changed with more shrinkproblem, and why more shrinkproblem can solve these bugs. With deep-dive to the detail, I found this implication information has changed. But I am not sure this is the core of these bugs.
Thanks
A couple more bugs have been fixed in presolve in recent months, but I'd not gone back through issues to see whether the fixes had resolved them.
Thanks for letting me know about these two
I've gone through all these instances again, and all problems solve correctly with presolve, except
- subset_select_B_on_139_off_138.mps
- subset_select_C_on_153_off_152.mps
I don't quite understand what you mean by "execute more shrinkproblem when presolve back to the main while loop"
Are you saying that you've changed the numbers in
if (shrinkProblemEnabled && (numDeletedCols >= 0.5 * model->num_col_ || numDeletedRows >= 0.5 * model->num_row_)) shrinkProblem(postsolve_stack);
so that shrinkProblem is called more frequently?
This may make a difference because, if I set the HiGHS option random_seed to be a value other than 0, sometimes HiGHS with presolve solves these instances OK. Calling shrinkProblem with a different frequency may yield a random reordering of the rows/columns that has the same effect