[Coin-bcpdiscuss] comute_lower_bound and generate_vars_in_lp methods in BCP

[Laszlo Ladanyi]

Hi Ali,

Your understanding is perferct. Everything happens exactly as you describe and
exactly for the reasons you describe. And yes, the right thing to do is to
clear the list just before compute_lower_bound.

Exactly because this whole process is a rather awkward thing to do I have
introduced the process_lp_result() method. It combines all the post lp solving
methods (testing feasibility, computing true lower bound, generating
cuts/vars) in a single call. If the user overrides this method then none of
the others are called, instead BCP just picks up the lower bound / columns,
etc. from the values/vectors returned by the user's method. If the user does
not override process_lp_result() then all the others are invoked in the order
you have described. Especially for column generation I'd recommend trying out
using process_lp_result().

I hope this helps,
--Laci

On Mon, 6 Aug 2007 alikoc at mail.utexas.edu wrote:

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