[BCP] Branch-and-price, computing lower bound, ...

[Xavier Schepler]

Le 12/02/2013 18:46, Changhyeok Lee a écrit :
> Hello,

Hi,

> I'm also using Coin-BCP to implement a branch-and-price algorithm. As far as I know, one should override "generate_vars_in_lp" and "vars_to_cols" functions (and "compute_lower_bound") to implement the branch-and-price.
Sure.
> In "generate_vars_in_lp", the user is supposed to return newly added variables to Bcp and in "vars_to_cols", the user is supposed to return the column information of the newly added variable to Bcp. This is achieved by receiving the address of BCP_vec< …. > as a parameter and add relevant objects to the vector.
Yes.
> Then, the internal functions in the Bcp package will do the rest - adding generated variables to the restricted master problem ( i.e. whatever OsiSolverInterface instance the user is using) and re-optimze. So, basically you don't need to worry about them. If there are new variables, the LP iteration will continue, otherwise, it will proceed to, say, branching decision.
Yes.
> One caveat is that in the original implementation of "compute_lower_bound", if the column generation option is turned on (btw, you have to turn this option on by specifying "colgen = BCP_GenerateColumns" in "init_new_phase" function in tree manager class), it simply does not update the lower bound. However, if there's no column to be generated, we should update the lower bound to the new LP objective value.
This is the problem. When BCP prune nodes, it uses the lower bound given 
by the LP relaxation,
even if /colgen /is set to /BCP_GenerateColumns/ in /init_new_phase 
function/.
> In order to fix this, we have to do the following: Implement the code that is supposed to be in "generate_vars_in_lp" in the "compute_lower_bound" function. and tell "compute_lower_bound" function to update the lower bound, if there's no column to be added, otherwise do not update. Save the generated variable information (e.g. as a member variable of "…_lp" class). In "generate_vars_in_lp", simply return the saved information to Bcp.
Yes, I think this is a way to do it.

What I did is different. I finally managed to have it working.

In the /compute_lower_bound/ method, I modify the /true_lower_bound/ 
value of the node object,
and I return a value such as BCP never prune the node.
Then, in the branching phase, I'm sure that all variables to be 
generated have been generated,
and that the LP value is a true lower bound.
So, in the function where a branching object is created 
(/select_branching_object/ as far as I can remember),
/BCP_DoNotBranch_Fathomed/ may be returned  according to the LP bound.
Everything is working now but it looks like a hack ...

Thanks for you response.

Xavier Schepler
PhD student, Université du Havre, France

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/bcp/attachments/20130212/744087c5/attachment.html>