[Coin-discuss] Coin-discuss Digest, Vol 44, Issue 6
Gabrielle A. Grün
grun at cs.sfu.ca
Fri Jun 13 18:15:52 EDT 2008
Hi Sebastian,
How are you? Not only do you have to set numberStrong_ to 0, you have to
set numberBeforeTrust_ to 0, and do it also in CbcStrategy.
SYMPHONY has branch and price. Thanks.
Gabrielle A. Grün, Ph.D. Student
School of Computing Science
Simon Fraser University
8888 University Drive
Burnaby, BC
V5A 1S6
<http://www.cs.sfu.ca/~grun>
----- Original Message -----
From: <coin-discuss-request at list.coin-or.org>
To: <coin-discuss at list.coin-or.org>
Sent: Friday, June 13, 2008 9:00 AM
Subject: Coin-discuss Digest, Vol 44, Issue 6
> Send Coin-discuss mailing list submissions to
> coin-discuss at list.coin-or.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
> http://list.coin-or.org/mailman/listinfo/coin-discuss
> or, via email, send a message with subject or body 'help' to
> coin-discuss-request at list.coin-or.org
>
> You can reach the person managing the list at
> coin-discuss-owner at list.coin-or.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of Coin-discuss digest..."
>
>
> Today's Topics:
>
> 1. Cbc, branch-and-price? (Sebastian Nowozin)
> 2. OsiCbc, CbcModel, how to disable strong branching?
> (Sebastian Nowozin)
> 3. Re: Cbc, branch-and-price? (John J Forrest)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Fri, 13 Jun 2008 09:49:51 +0200
> From: Sebastian Nowozin <nowozin at gmail.com>
> Subject: [Coin-discuss] Cbc, branch-and-price?
> To: Discussions about open source software for Operations Research
> <coin-discuss at list.coin-or.org>
> Message-ID: <4852269F.5090003 at gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>
> 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
>
>
> ------------------------------
>
> Message: 2
> Date: Fri, 13 Jun 2008 14:50:40 +0200
> From: Sebastian Nowozin <nowozin at gmail.com>
> Subject: [Coin-discuss] OsiCbc, CbcModel, how to disable strong
> branching?
> To: Discussions about open source software for Operations Research
> <coin-discuss at list.coin-or.org>
> Message-ID: <48526D20.1050100 at gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
>
>
> Hello,
>
> I use Cbc 2.1.0 using COIN-OR Osi trunk with OsiCbcSolverInterface.
> The MILP problem I create solves quickly and outputs finally:
>
> Cbc0001I Search completed - best objective 1757.3, took 3356139
> iterations and 26844 nodes (1463.37 seconds)
> Cbc0032I Strong branching done 135138 times (6347787 iterations),
> fathomed 0 nodes and fixed 0 variables
> Cbc0035I Maximum depth 60, 1.56856e+06 variables fixed on reduced cost
>
> Because strong branching did not seem to be effective at all, I want to
> disable it by adding this to my code:
>
> OsiCbcSolverInterface si;
> // ... (setup model)
>
> // Switch of strong branching
> CbcModel* mod = si.getModelPtr();
> mod->setNumberStrong(0);
>
> (I have seen this in sample5.cpp in the Cbc/examples/ directory).
>
> However, the above output remains and strong branching still seems
> enabled.
>
> Am I doing something wrong?
>
> Sebastian
>
>
> ------------------------------
>
> Message: 3
> Date: Fri, 13 Jun 2008 05:59:53 -0400
> From: John J Forrest <jjforre at us.ibm.com>
> Subject: Re: [Coin-discuss] Cbc, branch-and-price?
> To: Sebastian Nowozin <nowozin at gmail.com>
> Cc: Discussions about open source software for Operations Research
> <coin-discuss at list.coin-or.org>, coin-discuss-bounces at list.coin-or.org
> Message-ID:
> <OFE0E68822.61E59D4F-ON85257467.0036BA19-85257467.0036EBD9 at us.ibm.com>
> Content-Type: text/plain; charset=US-ASCII
>
> 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
>
>
>
>
> ------------------------------
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>
>
> End of Coin-discuss Digest, Vol 44, Issue 6
> *******************************************
More information about the Coin-discuss
mailing list