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

[John J Forrest]

Sebastian,

Cbc does not support branch and price.  I estimate it would take a week or
two to allow it to do so - it would need classes inheriting from
OsiClpSolverInterface and CoinWarmStartBasis.

I will leave it to others to say which would be the best Coin code to use.

John Forrest


                                                                                                                           
  From:       Sebastian Nowozin <nowozin at gmail.com>                                                                        
                                                                                                                           
  To:         Discussions about open source software for Operations Research <coin-discuss at list.coin-or.org>               
                                                                                                                           
  Date:       06/13/2008 04:01 AM                                                                                          
                                                                                                                           
  Subject:    [Coin-discuss] Cbc, branch-and-price?                                                                        
                                                                                                                           






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