[Coin-bcpdiscuss] Bug in strong branching?

[Laszlo Ladanyi]

Hi Lasse,

You may have hit on a bug. Your understanding of what should happen is
correct. However, there's an assumption in BCP, that is, 0 is always a
feasible value for any column that's not in the core. This assumption is there
simply because otherwise the rhs should be adjusted based on a column bcp has
no knowledge yet. Therefore no column is deleted if both of its bounds are
nonzero and the value of the var is nonzero. I think that's what you ran
into. 

It's debatable whather this assumption should be kept for the artificially
introduced branching variables, too. Even if I wanted to remove the assumption
there I don't see off the top of my head how to do so. I'll give it some
thought in the next couple of days. If you email me the exact formulation of
the cuts you are branching on and what is the result you want to achieve (how
you want to split the feasible region), I might be able to suggest a slightly
different way of getting there without violating BCP's assumption.

Cheers,
--Laci

On Wed, 2 May 2007, Lasse Nisted wrote:

> Hello
> 
> I might have encountered a bug, or maybe I'm doing something wrong in my
> column generation algorithm.
> 
> My problem happens when creating new variables in
> BCP_lp_user::select_branching_candidates while having strong branching enabled.
> 
> First some details about the branching.
> 
> I create a couple of branching candidates. Each candidate has an up and down
> branch. In the down-branch one row's coefficients are chosen to be 0, so all
> columns having this row's coefficient = 1 are forced to 0 with a column
> bound of 0.
> In the up-branch the same row's coefficient are forced to be 1. This is done
> by bounding all columns with the coefficient at 0 to 0 and adding new
> equivalent columns where the coefficient is 1 (with costs adjusted
> accordingly), this avoids regenerating those columns in the up-branch.
> 
> Now, when strong branching is enabled all candidates are presolved. As far
> as I can tell from the BCP code, all the new columns for ALL candidates are
> added to the LP problem and then disabled (bounds = 0), then columns are
> enabled for each candidate successively while presolving. Everything is fine
> so far.
> 
> The best candidate is found, and should now be send to the TM. This is where
> the problem occurs. The extra columns added for strong branching are
> "scheduled for deletion" in BCP_mark_result_of_strong_branching. Then in
> BCP_delete_unwanted_candidates they should be deleted. The columns for the
> selected candidate should be kept.
> For this some searching is done for the first and last column for which the
> candidate sets bounds. From my understanding, this search is wrong since it
> keeps too many columns.
> For instance when e.g. 3 candidates exist and e.g. 100 (old) columns exist
> and each candidate adds 10 new columns then candidate 3 will set bounds for
> some variables with indices [1,2,3,...,100] and [121,...,130].  The upper
> and lower bound (in BCP_delete_unwanted_candidates) will thus be LB<=100 and
> UB=130. Then according to the logic in BCP_delete_unwanted_candidates all
> extra columns are kept, also those for the other two candidates.
> 
> Those are then sent to the TM and my algorithm fails since the extra columns
> shouldn't exist in this branch.
> 
> A workaround is to pack the "BCP_var->is_to_be_removed()" attribute with the
> variable and then in BCP_lp_user::vars_to_cols create an empty column for
> these variables. For some reason the "is_to_be_removed()" is only set for
> the other candidates, so I think it can be trusted?
> But I think the correct solution would be to let
> BCP_delete_unwanted_candidates delete them correctly, somehow.
> 
> Is it a bug, or am I misunderstanding some of the functions (e.g. how to
> make new columns in select_branching_candidates).
> 
> 
> Kind regards,
> Lasse Nisted
> _______________________________________________
> Coin-bcpdiscuss mailing list
> Coin-bcpdiscuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-bcpdiscuss
>