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

[Laszlo Ladanyi]

Hi Miroslav,

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.

--Laci

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);
> 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
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>