<div dir="ltr"><div><div><div><div>Hi Gerald,<br><br></div>Thank you very much for the detailed response and suggestions.<br> <br></div>Unfortunately my problem does not have set partitioning structure, so I am unable to use Ryan Foster branching. <br>
</div>The problem I am solving is very large with around 10^8 binary variables and 10^6 constraints. But the interesting aspect of the problem is that in the <br>optimal solution, most of the binary variables are zero and typically less than 100 variables are one. That is why I was interested in applying <br>
branch-and-price. Currently my implementation (using cloud or strong branching) is indeed very slow. In particular, the lower bound seems to <br>improve very slowly. Any suggestions on how I can improve the convergence ? I am considering trying out some dual stabilization method, but I am not <br>
sure how much it can help.<br><br></div><div>I did not try using GCG yet because I wanted to have my own heuristics for pricing. Is there a way to do it ? Also, it seems like GCG is a standalone executable, unlike SCIP which I can use as an API. Is that correct ?    <br>
<br><br></div><div>Thanks,<br><br>Abde Ali<br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Mar 3, 2014 at 4:00 AM, Gerald Gamrath <span dir="ltr"><<a href="mailto:gamrath@zib.de" target="_blank">gamrath@zib.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear Abde Ali,<br>
<br>
now that the release is done, here are some more detailed answers.<br>
<br>
SCIP is a plugin-based system, there are currently 9 different branching<br>
rules shipped with the release 3.1. All of them are included into SCIP<br>
by SCIPincludeBranchruleXyz() methods, that is why calling<br>
SCIPincludeBranchruleAllfullstrong() produced an error - the branching<br>
rule is already included into SCIP by default.<br>
<br>
You can display a list of all branching rules in the interactive shell<br>
via "display branching". They are always called in decreasing order of<br>
priority, so the relpscost (hybrid reliability pseudo cost) branching<br>
rule is used by default. As Thomas mentioned already, you need to set<br>
the priority of allfullstrong branching to something larger than 10000,<br>
if you want to activate it.<br>
<br>
However, if you are doing branch-and-price, I would recommend you to not<br>
use one of the default branching rules. They are all branching on<br>
variables (which is standard for branch-and-cut), but branching on<br>
variables is typically very ineffective for branch-and-price and might<br>
also make your pricing problem harder. Does you master problem have a<br>
set partitioning structure? This is very common and allows to use the<br>
Ryan-Foster branching rule. You can find examples for this branching in<br>
the Coloring and Binpacking example, which you would need to adapt to<br>
your application.<br>
<br>
You might also want to have a look at the GCG project, which is also<br>
part of the SCIP optimization suite. It is a generic<br>
branch-cut-and-price solver, i.e., you put in a problem in an original<br>
form, it performs a Dantzig-Wolfe decomposition and solves the<br>
reformulated problem with a branch-and-price approach. You can specify<br>
the structure for the decomposition yourself or let GCG try to detect a<br>
good structure. The branch-and-price process is done without any need<br>
for you to implement anything: There is already a pricer solving the<br>
pricing problems as MIPs and different branching rules, e.g., branching<br>
on original variables or Ryan-Foster-style branching.<br>
<br>
Best,<br>
Gerald<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
On <a href="tel:27.02.2014%2020" value="+12702201420">27.02.2014 20</a>:37, Thomas Schlechte wrote:<br>
> Hi Abde Ali,<br>
><br>
> I think the SCIP developers are hard working for the<br>
><br>
> next release :), so please take a look at<br>
><br>
> <a href="http://scip.zib.de/doc/html/PARAMETERS.php" target="_blank">http://scip.zib.de/doc/html/PARAMETERS.php</a><br>
><br>
> and try so set<br>
><br>
> branching/allfullstrong/priority<br>
><br>
> higher than all other priorities of included branching rules.<br>
><br>
> Have fun<br>
> Thomas<br>
><br>
><br>
><br>
> higher than all<br>
>> Hi SCIP Developers,<br>
>><br>
>> I have a couple of small questions about branching rules:<br>
>><br>
>> - If I do not specify a particular branching rule, which branching rule is<br>
>> used by default ?<br>
>><br>
>> - How can I change the branching rule to something other than the default<br>
>> option ?<br>
>>   I don't plan on implementing my own branching rule, but I wanted to just<br>
>> pick one<br>
>> of the options like full strong or pseudo cost based rules that you have<br>
>> provided.<br>
>> In my C++ code, I tried asking the solver to use the all full strong<br>
>> branching rule by calling this function<br>
>> :SCIPincludeBranchruleAllfullstrong<br>
>> (<br>
>> SCIP<<a href="http://scip.zib.de/doc/html/type__scip_8h.php#a4792a242d315bf76f05b1f4e0712bc33" target="_blank">http://scip.zib.de/doc/html/type__scip_8h.php#a4792a242d315bf76f05b1f4e0712bc33</a>>*<br>
>> *scip*)<br>
>> But I seem to get this error when I run the code:<br>
>><br>
>> RROR: branching rule <allfullstrong> already included.<br>
>> [src/scip/branch_allfullstrong.c:479] ERROR: Error <-9> in function call<br>
>> [src/scip/scipdefplugins.c:90] ERROR: Error <-9> in function call<br>
>> [maskfracture.cpp:265] ERROR: Error <-9> in function call<br>
>><br>
>> So how do I specify a particular branching rule for branch and price ?<br>
>><br>
>> Thank you very much.<br>
>><br>
>> Abde Ali<br>
>> _______________________________________________<br>
>> Scip mailing list<br>
>> <a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
>> <a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a><br>
>><br>
><br>
><br>
> _____________________________________________<br>
><br>
> Dr. Thomas Schlechte<br>
> Zuse Institute Berlin<br>
> Takustrasse 7, D-14195 Berlin-Dahlem, Germany<br>
> phone: <a href="tel:%2B49-30%20841%2085%20317" value="+493084185317">+49-30 841 85 317</a><br>
> fax: <a href="tel:%2B49-30%20841%2085%20269" value="+493084185269">+49-30 841 85 269</a><br>
> url: <a href="http://www.zib.de/schlechte" target="_blank">http://www.zib.de/schlechte</a><br>
> e-mail: <a href="mailto:schlechte@zib.de">schlechte@zib.de</a><br>
> _____________________________________________<br>
><br>
> _______________________________________________<br>
> Scip mailing list<br>
> <a href="mailto:Scip@zib.de">Scip@zib.de</a><br>
> <a href="http://listserv.zib.de/mailman/listinfo/scip" target="_blank">http://listserv.zib.de/mailman/listinfo/scip</a><br>
<br>
</div></div></blockquote></div><br></div>