[Coin-bcpdiscuss] test_ful() question

[Laszlo Ladanyi]

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?

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