[Scip] Question about changing branching rule

Thu Mar 6 03:04:41 CET 2014

Hi Gerald,

Thank you very much for the detailed response and suggestions.

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.

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 ?

Thanks,

Abde Ali

On Mon, Mar 3, 2014 at 4:00 AM, Gerald Gamrath <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: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
> >> 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
> > fax: +49-30 841 85 269
> > url: http://www.zib.de/schlechte
> > e-mail: schlechte at zib.de
> > _____________________________________________
> >
> > _______________________________________________
> > Scip mailing list
> > 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/20140305/22226d73/attachment.html>