<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi Christina,<br>
<br>
all branching rules in SCIP do branching on variables, i.e., split
the domain of a single variable when branching. This is the
standard way to do it for branch-and-cut, but for
branch-and-price, this does not work well, because the pricing
would need to know that a variable was for example fixed to 0 and
must not be regenerated. This can often not be accomplished
without destroying the structure of the pricing problem needed for
the fast algorithms to solve them.<br>
<br>
In branch-and-price, you typically implement your own branching
rule which does not branch on variables, but on constraints or
decisions in the pricing problem. For example, the Ryan and Foster
branching rule applied to binpacking decides whether two items
will be packed into the same bin or two different bins. This leads
to a modification of the pricing problem as well as forbidding
some of the master variables which do not comply with the current
branching decisions. Alternatively, you could branch on variables
of the underlying structure represented by the compact
formulation. This means, if your variables correspond to paths in
a graph, you could branch on the decision whether an arc is used
or not.<br>
<br>
Please check out the binpacking and coloring example for examples
of Ryan and Foster branching rules.<br>
<br>
Best,<br>
Gerald<br>
<br>
On 03.06.2014 10:45, Cristina Núñez del Toro wrote:<br>
</div>
<blockquote
cite="mid:CAKuRvOEkp0o-t-M1-xjrEC7f4LwxmDwMsU=PSY44UJzAKeidmg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div style="font-family:arial,sans-serif;font-size:13px">Hello
Martin,<br>
<br>
</div>
<span style="font-family:arial,sans-serif;font-size:13px">I
think I understand the problem. I just have a couple of
questions:</span><br
style="font-family:arial,sans-serif;font-size:13px">
<br style="font-family:arial,sans-serif;font-size:13px">
<ol style="font-family:arial,sans-serif;font-size:13px">
<li style="margin-left:15px">I can not see clearly how this
situation can be fixed by implementing my own branching rule</li>
<li style="margin-left:15px">I have checked that there some
branching rules that are currently available on <span
class="">SCIP</span>. How can I know which branching rule
does <span class="">SCIP</span> uses by default? Because
these branching rules seem to be quite general, I would like
to try first on swapping among them. Is there a way to make
a callback to force the use of one of them instead of the
default one? If not, is the only way to implement my
personalized branching rule by adding explicitly a
constraint handler?</li>
</ol>
<p style="font-family:arial,sans-serif;font-size:13px">Thanks in
advance.</p>
<p style="font-family:arial,sans-serif;font-size:13px"><br>
</p>
<div class="gmail_extra"
style="font-family:arial,sans-serif;font-size:13px">
<br>
---<br>
Cristina Nuñez</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">2014-05-28 20:46 GMT+02:00 Martin
Bergner <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:bergner@or.rwth-aachen.de" target="_blank">bergner@or.rwth-aachen.de</a>></span>:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">Hi
Cristina,<br>
<div class=""><br>
somewhere in your detailed explanation, you write:<br>
> Even<br>
> that your comment about branching was focus on
variables with upper<br>
> bound = 0, now I am thinking that maybe the branching
rule is somehow<br>
> forbidding some of the variables. How can I check
this behaviour? I do<br>
> not use any special rule for the branching. All the
branching procedure<br>
> is set as default.<br>
</div>
This is probably the issue:<br>
When you don't specify a branching rule, SCIP branches on
the priced<br>
variables. If they are binary, they are fixed to one in one
branch and<br>
zero in the other. If the variable is fixed to zero, then
nothing in the<br>
pricing problem forbids it from being generated again.<br>
<br>
Suppose now you have a non-degenerate variable in the basis
that is<br>
removed by fixing it to zero. Since nothing in the pricing
forbids it<br>
from doing so, it regenerates that variable that has been
fixed. After<br>
all, this variable is highly attractive (negative reduced
cost) and<br>
should be put into the basis, it was there before it was
forcibly<br>
removed by branching.<br>
<br>
Do you see the problem? Whenever SCIP fixes a variable to
zero, your<br>
pricing problem generates it again (and you thus have the
problem you see).<br>
<br>
The remedy is: You have to (and in fact everyone when using<br>
branch-and-price with SCIP with integral priced variables
should)<br>
implement your own branching rule (maybe Ryan-Foster or
something more<br>
general, depending on your problem at hand).<br>
<br>
I hope I could clarify the issue.<br>
<br>
Regards,<br>
Martin<br>
<br>
<br>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
---<br>
Cristina Nuñez<br>
</div>
</blockquote>
<br>
</body>
</html>