[Scip] Question about changing branching rule

Mon Mar 10 16:22:50 CET 2014

Dear Abde Ali,

> Unfortunately my problem does not have set partitioning structure, so
> I am unable to use Ryan Foster branching.
> 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
> 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
> branch-and-price. Currently my implementation (using cloud or strong
> branching) is indeed very slow. In particular, the lower bound seems to
> 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
> sure how much it can help.
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.

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.

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.

> 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 ?
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).

Best,
Gerald

>
>
> Thanks,
>
> Abde Ali
>
>
> On Mon, Mar 3, 2014 at 4:00 AM, Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>> wrote:
>
>     Dear Abde Ali,
>
>     now that the release is done, here are some more detailed answers.
>
>     SCIP is a plugin-based system, there are currently 9 different
>     branching
>     rules shipped with the release 3.1. All of them are included into SCIP
>     by SCIPincludeBranchruleXyz() methods, that is why calling
>     SCIPincludeBranchruleAllfullstrong() produced an error - the branching
>     rule is already included into SCIP by default.
>
>     You can display a list of all branching rules in the interactive shell
>     via "display branching". They are always called in decreasing order of
>     priority, so the relpscost (hybrid reliability pseudo cost) branching
>     rule is used by default. As Thomas mentioned already, you need to set
>     the priority of allfullstrong branching to something larger than
>     10000,
>     if you want to activate it.
>
>     However, if you are doing branch-and-price, I would recommend you
>     to not
>     use one of the default branching rules. They are all branching on
>     variables (which is standard for branch-and-cut), but branching on
>     variables is typically very ineffective for branch-and-price and might
>     also make your pricing problem harder. Does you master problem have a
>     set partitioning structure? This is very common and allows to use the
>     Ryan-Foster branching rule. You can find examples for this
>     branching in
>     the Coloring and Binpacking example, which you would need to adapt to
>     your application.
>
>     You might also want to have a look at the GCG project, which is also
>     part of the SCIP optimization suite. It is a generic
>     branch-cut-and-price solver, i.e., you put in a problem in an original
>     form, it performs a Dantzig-Wolfe decomposition and solves the
>     reformulated problem with a branch-and-price approach. You can specify
>     the structure for the decomposition yourself or let GCG try to
>     detect a
>     good structure. The branch-and-price process is done without any need
>     for you to implement anything: There is already a pricer solving the
>     pricing problems as MIPs and different branching rules, e.g.,
>     branching
>     on original variables or Ryan-Foster-style branching.
>
>     Best,
>     Gerald
>
>
>     On 27.02.2014 20 <tel:27.02.2014%2020>:37, Thomas Schlechte wrote:
>     > Hi Abde Ali,
>     >
>     > I think the SCIP developers are hard working for the
>     >
>     > next release :), so please take a look at
>     >
>     > http://scip.zib.de/doc/html/PARAMETERS.php
>     >
>     > and try so set
>     >
>     > branching/allfullstrong/priority
>     >
>     > higher than all other priorities of included branching rules.
>     >
>     > Have fun
>     > Thomas
>     >
>     >
>     >
>     > higher than all
>     >> Hi SCIP Developers,
>     >>
>     >> I have a couple of small questions about branching rules:
>     >>
>     >> - If I do not specify a particular branching rule, which
>     branching rule is
>     >> used by default ?
>     >>
>     >> - How can I change the branching rule to something other than
>     the default
>     >> option ?
>     >>   I don't plan on implementing my own branching rule, but I
>     wanted to just
>     >> pick one
>     >> of the options like full strong or pseudo cost based rules that
>     you have
>     >> provided.
>     >> In my C++ code, I tried asking the solver to use the all full
>     strong
>     >> branching rule by calling this function
>     >> :SCIPincludeBranchruleAllfullstrong
>     >> (
>     >>
>     SCIP<http://scip.zib.de/doc/html/type__scip_8h.php#a4792a242d315bf76f05b1f4e0712bc33>*
>     >> *scip*)
>     >> But I seem to get this error when I run the code:
>     >>
>     >> RROR: branching rule <allfullstrong> already included.
>     >> [src/scip/branch_allfullstrong.c:479] ERROR: Error <-9> in
>     function call
>     >> [src/scip/scipdefplugins.c:90] ERROR: Error <-9> in function call
>     >> [maskfracture.cpp:265] ERROR: Error <-9> in function call
>     >>
>     >> So how do I specify a particular branching rule for branch and
>     price ?
>     >>
>     >> Thank you very much.
>     >>
>     >> Abde Ali
>     >> _______________________________________________
>     >> Scip mailing list
>     >> Scip at zib.de <mailto:Scip at zib.de>
>     >> http://listserv.zib.de/mailman/listinfo/scip
>     >>
>     >
>     >
>     > _____________________________________________
>     >
>     > Dr. Thomas Schlechte
>     > Zuse Institute Berlin
>     > Takustrasse 7, D-14195 Berlin-Dahlem, Germany
>     > phone: +49-30 841 85 317 <tel:%2B49-30%20841%2085%20317>
>     > fax: +49-30 841 85 269 <tel:%2B49-30%20841%2085%20269>
>     > url: http://www.zib.de/schlechte
>     > e-mail: schlechte at zib.de <mailto:schlechte at zib.de>
>     > _____________________________________________
>     >
>     > _______________________________________________
>     > Scip mailing list
>     > Scip at zib.de <mailto:Scip at zib.de>
>     > http://listserv.zib.de/mailman/listinfo/scip
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140310/e985b6a0/attachment.html>