[Coin-bcpdiscuss] Bug in strong branching?

[Lasse Nisted]

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