[Coin-bcpdiscuss] comute_lower_bound and generate_vars_in_lp methods in BCP

[alikoc at mail.utexas.edu]

Hello,

I encountered a problem when I was using BCP for branch & price. I fixed it
after 3 days of debugginng; but I wonder whether it is may fault in using BCP, 
or it is a bug in BCP, or it is none of those but something that users should be
aware of.

Here is the problem: In column generation, in order to compute the lower bounds
we need to solve subproblems to optimality. We are doing this in
BCP_lp_user::compute_lower_bound_method(). But, this process (solving
subproblems) also gives us the favorable columns. Hence, in order not to do tha
same task twice, we store these columns in a local variable of the BCP_lp_user
class (or in a user defined class that extends it). In
BCP_lp_user::generate_vars_in_lp() method we are adding those columns that we
already stored, and clearing the local variable.

The above algorithm is what I was using in my code (I copied it from the AAP
implementation of Matthew Galati
-http://coral.ie.lehigh.edu/~coin/COIN_EXAMPLES/AAP_BP/Doc/aap/index.html). The
thing that does not work is this: The code in 'BCP_lp_main_loop' works as
follows (the relevant part): It calls first the test_feasiblity() method (or
the 'process_lp_result()' method) and than the 'compute_lower_bound()' method.
And after that, it tries to fathom the node by comparing the lower and upper
bounds. If it succeeds in pruning the node, it does not call the
'generate_vars_in_lp()' method (which is reasonable). But, we were clearing the
local variable that keeps the faovorable columns in 'generate_vars_in_lp()'
method. Since, it does not call this method, our local variable is not cleared.
And since the BCP_lp_user class is not specific to the nodes of the tree, we
have some columns in a local variable of the BCP_lp_user class that is going to
be used for the next-to-be-processed node of the B&B tree. And if these columns
does not obey the branching restrictions of the new node, the same variable
shows up again and again as fractional, although we already branched on it.

I fixed the problem simply clearing the local variable in the
compute_lower_bound() method before starting the subproblem solver.


So my questions is this: Is my understanding of the error in my code is true, or
it is not as what I think, and there is some other source of the error :(


Thanks,

Ali