[Coin-bcpdiscuss] test_ful() question
fmargot at andrew.cmu.edu
fmargot at andrew.cmu.edu
Thu Jan 18 09:30:42 EST 2007
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
More information about the Coin-bcpdiscuss
mailing list