Suboptimal solution reported as optimal on a small MIP with presolve enabled #3561

Activity

1. jajhall commented on Nov 6, 2026

   

   jajhall

   on Nov 6, 2026

   SponsorMember

   More actions

   Reproduced with latest (9ba15c4)
2. jajhall

   added

   MIP

   Bug

   on Nov 6, 2026
3. DoumarCharles commented on Nov 6, 2026

   

   DoumarCharles

   on Nov 6, 2026

   More actions

   I have been looking at this presolve code, and I found what causes this. Here is a proposed fix.

   The wrong fixing comes from dual-fixing probing (rule 20; presolve_rule_off = 1048576 avoids it). updateLhsRedundant and updateRhsRedundant in HighsDomain.cpp count a row side as redundant when its activity bound is within feastol of the side. On rand_numer_060_mr8, probing x1 = 0 leaves r0 1e-6 short of redundant, but it is marked redundant anyway, so x3 and x8 are dual-fixed down. That violates r0, the probe is declared infeasible, and x1 is fixed to 1.

   Without the tolerance, both models solve correctly (144.680846 and 171.336411):

   --- a/highs/mip/HighsDomain.cpp
   +++ b/highs/mip/HighsDomain.cpp
   @@ -733,8 +733,7 @@
          mipsolver->model_->row_upper_[row] == kHighsInf)
        return;
    
   -  if (domain->getMaxActivity(row) <=
   -      mipsolver->model_->row_upper_[row] + mipsolver->mipdata_->feastol) {
   +  if (domain->getMaxActivity(row) <= mipsolver->model_->row_upper_[row]) {
        redundantRowInds_.push_back(idx);
        redundantRowFlags_[idx] = 1;
        if (!isEnabled()) ++numGlobalRedundantRows_;
   @@ -747,8 +746,7 @@
          mipsolver->model_->row_lower_[row] == -kHighsInf)
        return;
    
   -  if (domain->getMinActivity(row) >=
   -      mipsolver->model_->row_lower_[row] - mipsolver->mipdata_->feastol) {
   +  if (domain->getMinActivity(row) >= mipsolver->model_->row_lower_[row]) {
        redundantRowInds_.push_back(idx);
        redundantRowFlags_[idx] = 1;
        if (!isEnabled()) ++numGlobalRedundantRows_;

   I used an AI assistant to help trace this.
4. Opt-Mucca commented on Nov 6, 2026

   

   Opt-Mucca

   on Nov 6, 2026

   Collaborator

   More actions

   @DoumarCharles thanks for tracking down the issue! I've proposed a fix in #3575 that works for the problematic instance. In general I'd prefer to keep tolerances here as they're used constantly in this context throughout the code. It was some avoidable unlucky floating precision stuff that was causing this instance to produce incorrect results.

   @hodangkhoinguyen thanks for raising the issue!
5. Opt-Mucca

   closed this as completedon Nov 6, 2026