<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<tt>Dear Myroslav,<br>
<br>
maybe I need to clarify my previous answer: In the z_P = 0 branch,
you want to find a path with the most negative reduced cost that
is not P and has most negative reduced costs. After solving the
corresponding pricing problem, you either add a new variable z_P'
or you proved that the continuous relaxation in the current
(local) node has been solved to optimality. In both cases, you
don't add a variable that has been generated already.<br>
<br>
To summarize it, you need to respect the branching decisions in
order to ensure that you generate all variables that are needed
for solving the LP relaxation of a local node to optimality.
Branching on the master variables usually changes the pricing
problems drastically (e.g., shortest path -> k-shortest path).<br>
<br>
Best,<br>
Benny<br>
<br>
<br>
</tt>
<div class="moz-cite-prefix">On 08/30/2018 12:15 PM, myroslav wrote:<br>
</div>
<blockquote type="cite"
cite="mid:dd896a58-8c8b-2653-9c68-5fc12788a479@uni-wuerzburg.de">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<p>Dear Benny,</p>
<p><br>
</p>
<p>thanks a lot for the example! I see that the pricing problem is
changed when we add a branching constraint for a variable that
is already in the model but the point that I miss is why we
would want to generate the same variable again. If z_P has
already been generated, then SCIP knows about it. So we can
simply algorithmically prevent generating it again, by putting
an if-statement in the pricing algorithm. Why would we even want
to compute its reduced cost, since the variable is already
generated?</p>
<p>I can only think of one scenario when an already generated
variable is added again: the variable z_P has been generated at
some node of the branching tree, since SCIP always adds
variables globally, it also adds this variable to all the other
nodes(even those which are not in the sub-tree of the node where
z_P was generated) by using the SCIP default variable pricer
which uses its own pricing algorithm(that's what the SCIP
default variable pricer does, right?). If this scenario is
wrong, please let me know, because then I don't quite understand
how SCIP works.</p>
<p><br>
</p>
<p>Sincerely,</p>
<p>Myroslav<br>
</p>
<p><br>
</p>
<br>
<div class="moz-cite-prefix">On 30/08/2018 11:10, Benjamin Müller
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:b9a1ffe9-4f0b-6bba-6c85-35938e205fd5@zib.de">
<meta http-equiv="Content-Type" content="text/html;
charset=utf-8">
<tt>Dear Myroslav,<br>
<br>
branching on a generated variable introduces a constraint
whose dual multiplier needs to be considered in the objective
function of the following pricing problems (when the added
constraint is active). This might change the nature of the
pricing problems completely. Imagine a branch-and-price
example where the pricing problem is a classical shortest path
problem. Let z_P the variable corresponding to a path P that
has been generated. In the branch z_P = 0 you need to ensure
that your pricing problem doesn't generate P again. This
changes your pricing problem to a k-shortest path problem.<br>
<br>
I left out most of the details, but there is plenty of
literature about branching rules in branch-and-price. An
example of how a branching rule interacts nicely with the
pricing problem is shown in the Binpacking example of SCIP,
see <a moz-do-not-send="true"
href="http://scip.zib.de/doc-6.0.0/html/BINPACKING_MAIN.php">here</a>
for more details.<br>
<br>
Best,<br>
Benny<br>
</tt><br>
<div class="moz-cite-prefix">On 08/29/2018 12:17 PM, myroslav
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:40939517-8370-c916-06f5-0495257e6782@uni-wuerzburg.de">Dear
SCIP community, <br>
<br>
<br>
I wanted to ask about how branching affects pricing and how it
is managed in SCIP. If I understand how variables are added
in SCIP, I can't think of a scenario when branching decisions
really affect pricing. A branching decision is made on
variables known to SCIP (those that have been already
generated/ present in SCIP), so a branching constraint
involving these variables is not taken into account when we
price new variables. I would appreciate if someone could clear
that out. <br>
<br>
<br>
Thanks, <br>
<br>
Myroslav <br>
<br>
_______________________________________________ <br>
Scip mailing list <br>
<a class="moz-txt-link-abbreviated" href="mailto:Scip@zib.de"
moz-do-not-send="true">Scip@zib.de</a> <br>
<a class="moz-txt-link-freetext"
href="https://listserv.zib.de/mailman/listinfo/scip"
moz-do-not-send="true">https://listserv.zib.de/mailman/listinfo/scip</a>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</body>
</html>