[Coin-discuss] BCP: selecting variables for strong branching
ladanyi at us.ibm.com
Wed Jan 4 22:47:50 EST 2006
You are absolutely right. I have committed the suggested change.
As far as having other criteria... I'm not against adding more. It's just that
I wanted to have a few default, and for any specific problem class most people
have to devise their own branching anyway... I'm perfectly willing to include
more defaults if someone writes the code.
On Mon, 2 Jan 2006, Miroslav Karamanov wrote:
> 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);
> 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
> cost only.
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
More information about the Coin-discuss