<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<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>
</body>
</html>