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

[Xavier Schepler]

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

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