[SCIP] Processed / open / pruned nodes

[Gregor Hendel]

Hi Lara,

the tree maintains three different types of open nodes: children, 
siblings, and leaves. The types are always relative to the focus node. 
It is correct that SCIPgetNNodes() returns the total number of processed 
nodes, ie, the nodes which have been focussed during the search so far.

The number of currently open nodes can therefore be accessed as the sum 
SCIPgetNChildren() + SCIPgetNSiblings() + SCIPgetNLeaves()

SCIPgetNFeasibleLeaves() and SCIPgetNInfeasibleLeaves() are referring to 
leaves from hindsight, i.e., they count how often the search encountered 
nodes where the relaxation was feasible (e.g, all variables integer) and 
how often a focus
node was pruned (either the relaxation hit the objective limit, or the 
node represents an infeasible subproblem).
On the contrary, SCIPgetNLeaves() reports the current number of leaf 
nodes in the queue, not the total number of leaf nodes.

It is not possible in the current SCIP version to access the number of 
pruned nodes. If nodes are pruned from the queue, e.g., because a new 
incumbent solution has been found, this happens silently at the solver's 
discretion.

There is a counter for the number of created nodes, which is not 
publicly accessible via methods.

scip->stat->ncreatednodesrun

You can (ab)use this counter to get the number of pruned nodes by the 
equation

<pruned nodes> = scip->stat->ncreatednodesrun - SCIPgetNNodes() - 
SCIPgetNChildren() + SCIPgetNLeaves() + SCIPgetNSiblings()

I don't see a reason why there is no public method to access this 
attribute of the stats struct, I suggest you add one, that you can wrap 
from the Python Interface in a second step.

Hope this helps,
Gregor


Am 25.07.19 um 13:21 schrieb Lara Scavuzzo Montana:
>
> Dear SCIP community,
>
>
> I am solving MILPs using SCIP’s Python interface with all default 
> parameters and a custom branching rule. I am a bit confused by the 
> terminology of the documentation, so I would be very thankful for the 
> following clarifications.
>
>
> During the solving process, I would like to keep track of some solving 
> statistics. In particular, at each step know:
>
> - *The number of processed nodes:* this can be accessed with (correct 
> me if I am wrong) SCIPgetNNodes().
>
> - *The number of open nodes:* is SCIPnodepqlen() the right function to 
> call?
>
> - *The number of pruned nodes* (by bound, infeasibility or 
> integrality): I was unfortunately unable to find a way to obtain this 
> value. Would it be (# of leaves) - (# of open nodes) ?
>
>
> I was also surprised to see that
>
> SCIPgetNLeaves() != SCIPgetNFeasibleLeaves() + SCIPgetNInfeasibleLeaves()
>
> Maybe I am misinterpreting the meaning of these.
>
>
> Just to clarify, I would of course be modifying the Python interface 
> to include all necessary functions.
>
>
> Thank you in advance for any help with this issue.
>
>
> Best,
>
>
> Lara Scavuzzo
>
>
> _______________________________________________
> 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/20190725/a6a8ffdb/attachment.html>