[Coin-discuss] BCP: selecting variables for strong branching
miroslav at andrew.cmu.edu
Mon Jan 2 18:42:47 EST 2006
I perform strong branching on the 10 most fractional
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
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.
di = std::upper_bound(new_cost.begin(), new_cost.end(), val);
di = std::upper_bound(new_cost.begin(), new_cost.end(), val,
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
More information about the Coin-discuss