[Coin-bcpdiscuss] Possible problem in BCP_lp_user::reduced_cost_fixing

[acw at ascent.com]

In our BCP application we kept getting errors which we eventually tracked 
down to reduced_cost_fixing screwing up the bounds on some variables.  Our 
suspicion is that when dj[i] (the reactivity of the objective to the given 
variable) ought to be zero, it can sometimes be given a very small value 
due to roundoff error.  In this case, the bounds can get slammed to one 
end or the other, leaving the relaxed value of the variable outside the 
bounds.

We propose adding a check that doesn't adjust the bound if doing so would 
exclude the current value of the variable.  The relevant code is:

      if (dj[i] > 0) {
        const double lb = var->lb();
        const double new_ub = lb + floor(gap / dj[i]);
        if (new_ub < var->ub() && (atAny || CoinAbs(x[i])<petol)
            && (new_ub >= x[i])) { //  If x[i] is no longer in range, 
you've goofed due to roundoff error.
                                   // (this problem came up with an upper 
bound of 1e+24 and a dj of -1.9e-13)
          vars[i]->set_ub(new_ub);
          changed_indices.unchecked_push_back(i);
          changed_bounds.unchecked_push_back(lb);
          changed_bounds.unchecked_push_back(new_ub);
        }
      } else if (dj[i] < 0) {
        const double ub = var->ub();
        const double new_lb = ub - floor(gap / (-dj[i]));
        if (new_lb > var->lb() && (atAny || CoinAbs(x[i])<petol)
            && (new_lb <= x[i])) { //  If x[i] is no longer in range, 
you've goofed due to roundoff error.
                                   // (this problem came up with an upper 
bound of 1e+24 and a dj of -1.9e-13)
          vars[i]->set_lb(new_lb);
          changed_indices.unchecked_push_back(i);
          changed_bounds.unchecked_push_back(new_lb);
          changed_bounds.unchecked_push_back(ub);
        }
      }

The changes are marked with comments.

So far our tests show the problem that used to cause the errors, no longer 
doing so.  But our confidence-level is not high: the error was elusive, 
appearing and disappearing with changes that ought to have made no 
difference.  We are wondering if we are on the right track, and if this is 
a worthwhile change to migrate back into the source.  We'd appreciate any 
insights from other members of the COIN/Bcp community.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/bcp/attachments/20051128/a21f48cf/attachment.html