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

[Changhyeok Lee]

Hello,  

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.

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.

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.  

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.

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.   

--
Changhyeok Lee
PhD Student

Dept. of Industrial Engineering & Management Sciences


McCormick School of Engineering & Applied Science


Northwestern University


Email: changhyeoklee2014 at u.northwestern.edu





On Sunday, February 10, 2013 at 4:20 AM, Xavier Schepler wrote:

> Hello,
>  
> I've been struggling with Coin-BCP for several hours.
> There is almost no informations on the topic of computing a lower bound
> with Coin-BCP in a branch-and-price.
> The given examples with Coin-BCP look weird, because,
> the column generation processes seem to stop too early.
> They occur in the function compute_lower_bound,
> but, they do not add any column to the restricted master problem,
> and they do not re-optimize the restricted master problem to get updated reduced cost.
> There are comments like "TO DO" .... Ok ? So ?
>  
> I've implemented the generate_vars_in_lp method.
> Everything is working fine. Expected that the branch-and-price gives me false value.
> I've checked the value given by the column generation at root nodes and it is correct.
> Sometimes, the branch-and-price halts too early, indicating an optimal solution value,
> which is not optimal.
>  
> I thought it is because I have to implement the compute_lower_bound method,
> as said in the documentation.
> So, that's what I tryed to do.
> But, how can I add the generated variables to the restricted master problem,
> and reoptimize it, to get updated reduced costs, in a proper way ?
>  
> I've tryed something like that (the column generation loop is missing, as I tryed
> to add just one column first, and to reoptimize the restricted master problem) :
>  
> double LinearProgram::compute_lower_bound(const double oldLowerBound,
> const BCP_lp_result& LPResult, const BCP_vec<BCP_var*>& variables,
> const BCP_vec<BCP_cut*>& cuts)
> {
>  
> BCP_vec<BCP_var*> generatedVariables ;
> BCP_vec<BCP_col*> generatedColumns ;
> BCP_vec<BCP_col*> columns ;
> double lowerBound = oldLowerBound ;
> generate_vars_in_lp(LPResult, variables, cuts, false,
> generatedVariables, generatedColumns) ;
> vars_to_cols(cuts, generatedVariables, columns,
> LPResult, BCP_Object_FromGenerator, false) ;
> this->getLpProblemPointer()->lp_solver
>  
> Then, I tryed to add columns through the OsiSolverInterface methods,
> but it looks messy, and it didn't work.
>  
> Otherwise, the variables are correctly added to the the restricted master problem,
> using the generate_vars_in_lp and vars_to_cols methods.
> The pricing is going fine.
> But it seems to fail for computing lower bounds,
> and it looks like nodes are pruned too early.
>  
> HELP please.
>  
> Thanks in advance,
>  
> Xavier Schepler
>  
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org (mailto:BCP at list.coin-or.org)
> http://list.coin-or.org/mailman/listinfo/bcp