[Coin-discuss] BCP: selecting variables for strong branching

[Miroslav Karamanov]

I perform strong branching on the 10 most fractional 
variables: BCP_StrongBranch_CloseToHalfNum=10.
I noticed a strange behavior: a variable that should be 
selected based on its fractionality is not among the 10 
candidates. Furthermore, all 10 selected variables have zero 
objective coefficients while the discarded variable has a 
large positive coefficient. This behavior was systematic for 
the instance I solved.
As a result, the LP bound (almost) does not change for a 
long time.

The culprit is BCP_lp_user::branch_close_to_half(). Variable 
selection is done in two steps: first, select a larger 
number of variables based on fractionality; then, order the 
candidates by objective coefficients and select the first 10 
(in my case).

Well, this ordering is done in nondecreasing cost. I do not 
see the reason and I may be missing something. But I think 
nonincreasing ordering is more appropriate. Please correct me.

I replaced
di = std::upper_bound(new_cost.begin(), new_cost.end(), val);
by
di = std::upper_bound(new_cost.begin(), new_cost.end(), val, 
std::greater<double>());
in lines 1016 and 1023 of file BCP_lp_user.cpp (CVS:1.25).

Other criteria for variable selection can be considered here 
too. E.g. the product of cost and fractional part instead of 
cost only.

Miroslav