[Coin-discuss] Cbc, branch-and-price?

[Sebastian Nowozin]

Hello,

does COIN-OR Cbc support branch-and-price?

I have a problem that can be well modeled by a set covering formulation, 
  where N binary decisions must be made and K output levels must be 
reached.  Each binary decision involves a constant setup cost (c_use) 
and overproduction (measured by slack_k) costs as well, but a minimum 
level b_k must be reached for each "product" k.  We have a_{k,n} >= 0 in 
this model:

min_{x,slack}  \sum_{k=1}^{K} c_slack slack_k + \sum_{n=1}^{N} c_use x_n
sb.t. \sum_{n=1}^{N} a_{k,n} x_n - slack_k = b_k,  for all k=1,..,K
       x_n \in {0, 1} binary,  for all n=1,..,N
       slack_k >= 0, for all k=1,..,K

K is fixed and small (< 100), but the number of variables N is virtually 
unbounded, and I can generate a large number of columns.  A simple test 
with a small fixed number of "good" columns worked well with Cbc and 
Dive/RINS heuristics and standard cut generators.  The model looks 
similar to set covering formulations to airline crew scheduling on which 
branch-and-price is often used, so I want to give branch-and-price a try.

   Of the COIN projects, if Cbc does not support branch-and-price which 
is the easiest other option (SYMPHONY or BCP), and can branch-and-price 
be performed using the Osi* interface?

Thanks,
Sebastian