<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body>
<p>-------- Forwarded Message --------</p>
<div class="moz-forward-container">
<table class="moz-email-headers-table" cellspacing="0"
cellpadding="0" border="0">
<tbody>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">Subject:
</th>
<td>Re: Fwd: [SCIP] Large B&B trees with
Vanillafullstrong and idempotent=True</td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">Date: </th>
<td>Wed, 16 Aug 2023 16:30:49 +0200</td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">From: </th>
<td>Mark Turner <a class="moz-txt-link-rfc2396E" href="mailto:turner@zib.de"><turner@zib.de></a></td>
</tr>
<tr>
<th valign="BASELINE" nowrap="nowrap" align="RIGHT">To: </th>
<td>Mathieu Besançon <a class="moz-txt-link-rfc2396E" href="mailto:mathieu.besancon@gmail.com"><mathieu.besancon@gmail.com></a>,
<a class="moz-txt-link-abbreviated" href="mailto:scip@zib.de">scip@zib.de</a>, <a class="moz-txt-link-abbreviated" href="mailto:caroline.spieckermann@tum.de">caroline.spieckermann@tum.de</a></td>
</tr>
</tbody>
</table>
<br>
<br>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<p>Hey Caroline,</p>
<p><br>
</p>
<p>I will try and given a summary of what's going on and what the
probable issues are.</p>
<p>When you strong branch at a node you get much more information
than just pseudo-costs. Here's three examples:</p>
<p>- In all subproblems of a node you might find tighter common
bounds of a variable. <br>
</p>
<p>- One of the subproblems may end up yielding a primal solution</p>
<p>- You can update the relaxation value of the node because you
now know the relaxation value of all subproblems. This can help
with pruning nodes earlier. <br>
</p>
<p>When SCIP is performing strong branching, it not only logs the
LP values of each subproblem (as is done when you write out the
basic algorithm), but it actually uses information from the
subproblems. Using the examples above, SCIP may potentially
prune the node or change the domain of a variable. Many people
when they write their own branching rules find this comparison
unfair. This is because their approach is usually based on
scoring each variable as a branching candidate, and doesn't make
use of this additional information. <br>
</p>
<p>The vanilla strong branching was done by Maxime Gasse. So let's
imagine the scenario for his paper:</p>
<p>- He has constructed some graph neural network for imitating
strong branching scores. He can now produce "(predicted) strong
branching scores" much faster than solving all of the individual
LPs. <br>
</p>
<p>Even if he takes the exact same choice as strong branching
would, however, he is missing information that strong branching
would have access to. For example, maybe the node can be pruned
prematurely. This means even in the case where he would "mimic"
all the strong branching decisions, he can still end up with a
much larger search tree.</p>
<p>The idempotent parameter was made to fix this very issue.
Instead of competing against strong branching directly, it
allows competition against strong branching scores in isolation.
<br>
</p>
<p><br>
</p>
<p>The information above should hopefully answer why tree size in
general increases when idempotent=TRUE. As for the final
question on what is a fair comparison. This differs very heavily
depending on the context and the person you ask. In my opinion
you should simply compare to both. When presenting a branching
rule (likely based on machine learning), it is the standard to
produce a score for each variable to branch on for a given node.
Computing a score using such a method that outperforms strong
branching in tree size would be a huge result, however is
extremely unlikely, and impossible for many instances.
Therefore, comparing to vanilla with idempotent=FALSE is a fair
compromise provided adequate context is provided. So just make
sure to give context that performance is relative to scores
derived from strong branching, and not strong branching itself.
<br>
</p>
<p><br>
</p>
<p>Cheers and good luck with your branching rule,</p>
<p>Mark<br>
</p>
<br>
<blockquote type="cite"
cite="mid:CAP0C_zW9XpT=kjHDECrCL2ticL3aAFQS6+_S359UWPERzGfJWg@mail.gmail.com">
<div dir="ltr">
<div>
<div class="gmail_quote">
<div class="msg-645504120008900763">
<div dir="ltr">
<div id="m_-645504120008900763divtagdefaultwrapper"
style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif"
dir="ltr">
<p>Hello,</p>
<p><br>
</p>
<p>I'm trying to figure out which
(vanilla) fullstrong setup to use to have a fair
baseline for my own (learned) branching rule. In
particular, I'm unsure how to set the "<span>idempotent</span>"
parameter of <span>Vanillafullstrong</span>
branching as I do not fully understand what it
does. I read the documentation and looked into the
source code (<a
href="https://scipopt.org/doc/html/branch__vanillafullstrong_8c_source.php"
id="m_-645504120008900763LPlnk788392"
style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple
Color Emoji","Segoe UI
Emoji",NotoColorEmoji,"Segoe UI
Symbol","Android
Emoji",EmojiSymbols;font-size:16px"
target="_blank" moz-do-not-send="true"
class="moz-txt-link-freetext">https://scipopt.org/doc/html/branch__vanillafullstrong_8c_source.php</a>)
and, apparently, the idempotent parameter controls
whether pseudo costs are updated (but these are
not relevant for vanillafullstrong branching, are
they?) and whether lower bounds on the child nodes
get updated. How does the latter affect B&B
tree sizes? I would have expected that the Strong
Branching "side effects" mainly affect runtimes
but not so much tree sizes but as soon as I set <span
style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple
Color Emoji","Segoe UI
Emoji",NotoColorEmoji,"Segoe UI
Symbol","Android
Emoji",EmojiSymbols;font-size:16px">
idempotent</span>=True, tree sizes increase
significantly. <span style="font-size:12pt">Here
are some exemplary node averages when I solve 10
setcovering instances with three random seeds,
using different branching rules: <span>{relpscost:
330.67, fullstrong: 44.33, vanillafullstrong (<span
style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple
Color Emoji","Segoe UI
Emoji",NotoColorEmoji,"Segoe UI
Symbol","Android
Emoji",EmojiSymbols;font-size:16px">idempotent</span>=False):
103.63, vanillafullstrong (<span
style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple
Color Emoji","Segoe UI
Emoji",NotoColorEmoji,"Segoe UI
Symbol","Android
Emoji",EmojiSymbols;font-size:16px">idempotent</span>=True):
299.57}. This is just a small test set with
small instances but I observed the same
behavior on other problem classes and instance
sizes. Why are the B&B trees so much
larger when setting <span
style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple
Color Emoji","Segoe UI
Emoji",NotoColorEmoji,"Segoe UI
Symbol","Android
Emoji",EmojiSymbols;font-size:16px">
idempotent</span>=True and what is the
correct vanilla setup to have a fair
comparison?</span></span></p>
<p><span style="font-size:12pt"><span><br>
</span></span></p>
<p><span style="font-size:12pt"><span>Thanks in
advance!</span></span></p>
<p><span style="font-size:12pt"><span><br>
</span></span></p>
<p><span style="font-size:12pt"><span>Kind regards,</span></span></p>
<p>Caroline Spieckermann</p>
<p><span style="font-size:12pt"><span><br>
</span></span></p>
<p><span style="font-size:12pt"><span><br>
</span></span></p>
</div>
</div>
_______________________________________________<br>
Scip mailing list<br>
<a href="mailto:Scip@zib.de" target="_blank"
moz-do-not-send="true" class="moz-txt-link-freetext">Scip@zib.de</a><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip"
rel="noreferrer" target="_blank"
moz-do-not-send="true" class="moz-txt-link-freetext">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</body>
</html>