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

Most upvoted comments

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.