<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Dear Abde Ali,<br>
<br>
</div>
<blockquote
cite="mid:CAKis+KL_f4VjGkoaYmHCPMFntcKQ=9EMB4xGDeL2KEEbj8iqLw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<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>
</div>
</div>
</blockquote>
what type of problem is your pricing problem and how do you solve
it? Branching on a variable like the standard SCIP branching rules
do is however not the way to go or branch-and-price. This gives you
a very unbalanced tree and the dual bound typically moves very
slowly. Moreover, how do you make sure that you don't generate the
same column again after branching fixed a variable to 0? This
typically makes your pricing problem much harder.<br>
<br>
Also, strong branching is quite expensive and does not generate new
variables when investigating potential child nodes, so its
predictions might not be very good. My experience is that you should
really use a branching rule which is specific to branch-and-price
and/or your problem.<br>
<br>
Can you send me a log-file of one of your runs, including statistics
in the end? Then I can have a look and perhaps give you some hints
what might be improved.<br>
<br>
<br>
<blockquote
cite="mid:CAKis+KL_f4VjGkoaYmHCPMFntcKQ=9EMB4xGDeL2KEEbj8iqLw@mail.gmail.com"
type="cite">
<div dir="ltr">
<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>
</div>
</div>
</blockquote>
Yes, it is possible to add your own algorithm to GCG for solving the
pricing problem, this is called pricing solver in GCG. It gets the
updated SCIP representing the pricing problem, but you can also just
take the updated objective coefficients from it to update its data
and then run your own algorithm. Have a look at src/type_solver.c
and src/solver_knapsack.c. We did not use GCG via the API, yet, but
it should be possible, since it is just an extension of SCIP. You
can just build your problem via the default SCIP methods and then
define the structure yourself. Please have a look at
src/reader_dec.c for that, in particular fillDecompStruct().
Essentially, you need a hashmap defining for each constraint which
block it belongs to (or if it is a master constraint).<br>
<br>
Best,<br>
Gerald<br>
<br>
<blockquote
cite="mid:CAKis+KL_f4VjGkoaYmHCPMFntcKQ=9EMB4xGDeL2KEEbj8iqLw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<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 moz-do-not-send="true"
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 moz-do-not-send="true" 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 moz-do-not-send="true"
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 moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:Scip@zib.de">Scip@zib.de</a><br>
>> <a moz-do-not-send="true"
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 moz-do-not-send="true"
href="tel:%2B49-30%20841%2085%20317"
value="+493084185317">+49-30 841 85 317</a><br>
> fax: <a moz-do-not-send="true"
href="tel:%2B49-30%20841%2085%20269"
value="+493084185269">+49-30 841 85 269</a><br>
> url: <a moz-do-not-send="true"
href="http://www.zib.de/schlechte" target="_blank">http://www.zib.de/schlechte</a><br>
> e-mail: <a moz-do-not-send="true"
href="mailto:schlechte@zib.de">schlechte@zib.de</a><br>
> _____________________________________________<br>
><br>
> _______________________________________________<br>
> Scip mailing list<br>
> <a moz-do-not-send="true"
href="mailto:Scip@zib.de">Scip@zib.de</a><br>
> <a moz-do-not-send="true"
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>
</blockquote>
<br>
</body>
</html>