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

[Laszlo Ladanyi]

Hello,

I think you are right, there is numerical instability in the code in reduced
cost fixing. However, the problem, I think, is a bit deeper. (I'll describe
everything in terms of the first dj test, the second block is analogous.)

1) A certain numerical problem is that dj[i] is not bounded away from 0. The
tests should be 'if (dj[i] > 1e-6)' (or some other epsilon, but definitely not
0).

2) Because of roundoff problems it should be tested that new_ub is not below
the current lb. I wonder if this was your problem? You did say that you got
infeasibility, but it's not clear whether the new_ub only went below the
current value making the current solution infeasible, or below the current lb
making the LP relaxation infeasible.

3) Was the -1.9e-13 reduced cost the rc of a basic variable or not? If it was
a basic var then the rc should, of course, be 0, so the interface to the LP
needs to be checked and the rc zeroed out for basic vars (to make sure that
there's no roundoff errors and no junk left there -- not likely, but it's
possible that some LP solvers don't bother to update the rc for basic vars).
If it was not a basic var then it was at its lower or upper bound. In the
first case we go back to 2), since if the new_ub is below the current value
then it is below the current lb. In the second case your var must have been at
1e24 and you really don't want that :-) (so I don't think this applies).

4) If 1) and 2) are tested (and we assume that basic vars -- even if their rc
is not 0, but at least near 0 with some roundoff error) then I don't think it
is necessary to test new_ub against the current solution value. The reason is
that if dj[i]>0 then it must be non-basic at its lower bound, so if we lower
the upper bound (but make sure not to go below the current lower bound) then
the solution must remain feasible.

What do you think?

I'm going to implement and commit 1) and 2), but if you could look into 3)
before updating your copy of the code that would be great.

Thanks,
--Laci


On Mon, 28 Nov 2005 acw at ascent.com wrote:

> 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.