[SCIP] Fwd: Fwd: Large B&B trees with Vanillafullstrong and idempotent=True

[Turner]

-------- Forwarded Message --------

Subject: 	Re: Fwd: [SCIP] Large B&B trees with Vanillafullstrong and 
idempotent=True
Date: 	Wed, 16 Aug 2023 16:30:49 +0200
From: 	Mark Turner <turner at zib.de>
To: 	Mathieu Besançon <mathieu.besancon at gmail.com>, scip at zib.de, 
caroline.spieckermann at tum.de



Hey Caroline,


I will try and given a summary of what's going on and what the probable 
issues are.

When you strong branch at a node you get much more information than just 
pseudo-costs. Here's three examples:

- In all subproblems of a node you might find tighter common bounds of a 
variable.

- One of the subproblems may end up yielding a primal solution

- 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.

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.

The vanilla strong branching was done by Maxime Gasse. So let's imagine 
the scenario for his paper:

- 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.

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.

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.


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.


Cheers and good luck with your branching rule,

Mark


> Hello,
>
>
> 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 "idempotent" parameter of 
> Vanillafullstrong branching as I do not fully understand what it does. 
> I read the documentation and looked into the source code 
> (https://scipopt.org/doc/html/branch__vanillafullstrong_8c_source.php) 
> 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 
> idempotent=True, tree sizes increase significantly. Here are some 
> exemplary node averages when I solve 10 setcovering instances with 
> three random seeds, using different branching rules: {relpscost: 
> 330.67, fullstrong: 44.33, vanillafullstrong (idempotent=False): 
> 103.63, vanillafullstrong (idempotent=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 idempotent=True and what is the correct 
> vanilla setup to have a fair comparison?
>
>
> Thanks in advance!
>
>
> Kind regards,
>
> Caroline Spieckermann
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20230901/cb89bf6d/attachment.html>