[Coin-bcpdiscuss] test_ful() question

[fmargot at andrew.cmu.edu]

On Thu, 18 Jan 2007, Laszlo Ladanyi wrote:

> You are right, two different etols should be used, one for bound testing
> (which can be extracted from the LP solver) and one for integrality. This is
> an easy change and I can make it. Please file a ticket so that I'll remember
> it :-). Thanks!
>
> The problem is what happens if a bound is violated. It means that the LP
> solver has returned a solution that is not feasible b ythe LP solver's own
> tolerance (this can happen if the solver preprocesses, solves getting a sol
> within tolerance, unwinds the preprocess and ends up with a sol out of
> tolerance. Do LP sovers have this problem? If they do, what can BCP do?
>

I would simply trust the LP solver, i.e. not check bounds for non integer
variables. For most solvers, the precision for checking bounds and feasibility
in general applies to the preprocessed and scaled problem. That value
might be unrelated to the precision of the solution for the original LP.
BCP should accept what the solver returns, and the user can check if the
solution is precise enough in the end. If it is not precise enough, he knows 
that he should (try) to request more precsion from the LP solver.

The problem with checking bounds on continuous variables is that it
might lead to a BCP failure, although neither BCP nor the LP solver
is really at fault: BCP wants a certain precision on the solution, but there
is no way to request that from the solver. Moreover, no check for the
feasibilty of the solution with respect to the constraints (other than
bounds) is made. Why being stricter on the bounds than on the other
constraints?

Note that maybe a new parameter BCP_BoundTolerance might be useful, if
it is possible to pass that value to the solvers (even if it applies
only to the scaled problem).

Francois



> --Laci
>
> On Thu, 18 Jan 2007 fmargot at andrew.cmu.edu wrote:
>
>> I find the tests in BCP_lp_user::test_full() (similar tests in
>> test_binary() and test_integer())
>>
>>  	if (val < vari->lb() - etol || val > vari->ub() + etol)
>>  	  return(NULL);
>>
>> hard to understand. etol is the precision specified to check if a value
>> is integer, yet the above test is also applied to continuous variables.
>> Moreover, when the condition is true, it means that the lp solver returns
>> a solution that is slightly infeasible (more than etol-infeasible), but
>> claims that it is optimal (otherwise test_full() is not reached, I believe).
>> What should happen in this case? The above test is dangerous, since
>> test_full might return "infeasible" for a solution where all integer
>> variables are indeed integer (with precision etol), but a continuous
>> variable is slightly below its lower bound. Then BCP will fail, as
>> no branching variable can be found.
>>
>> This means that etol should be set larger than
>> the precision on the feasibility of the solution returned by the lp solver.
>> But this precision is hard to determine. For example, Cplex gives
>> a feasibility tolerance parameter, but it is applied to the scaled
>> problem, not the original problem. I have no idea what kind of
>> feasibility precision Clp has. The default value for etol is 1e-5, which
>> is not that much larger than the default feasibility tolerance of Cplex,
>> 1e-6. Taking possible scaling into account, it is not unlikely to  run
>> into problems.
>>
>> It seems to me that it is more natural to trust blindly the lp solver.
>> If it tells you that it has an optimal solution, it is not the role
>> of BCP to catch it lying. In other words, the above test should only
>> be applied to integer variables.
>>
>> Francois
>>
>> _______________________________________________
>> Coin-bcpdiscuss mailing list
>> Coin-bcpdiscuss at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/coin-bcpdiscuss
>>
>
>
>