[SCIP] Processed / open / pruned nodes

[Gregor Hendel]

Hi Lara,

Am 25.07.19 um 18:23 schrieb Lara Scavuzzo:
>
> Dear Gregor,
>
>
> Thank you very much for your detailed explanation. As you suggested, I 
> used the ncreatednodesrun counter, although I think you meant to write
>
> <pruned nodes> = scip->stat->ncreatednodesrun - SCIPgetNNodes() - ( 
> SCIPgetNChildren() + SCIPgetNLeaves() + SCIPgetNSiblings() )
>
that is what I meant indeed.
>
>
> If I may ask for one last clarification: from what you write I 
> understand that the children/siblings/leaves distinction is made based 
> on the depth of each open node with respect to the focus node. Is this 
> correct?
>
It is not the depth that decides. It is the parent-child relation with 
the focus node. If the focus node has already been branched on, the 
newly created nodes are stored as children. Similarly, when the focus 
node was created as a branching child itself, the other node with the 
same parent is the sibling of the focus node. All other open nodes are 
maintained as leaves. Recall that SCIP admits n-ary user branching 
schemes, which is why even the siblings are kept as array, although 
there is usually at most 1 sibling.

Best regards,
Gregor

>
> Thank you again.
>
>
> Best,
>
>
> Lara
>
>
> El jue., 25 jul. 2019 a las 14:46, Gregor Hendel (<hendel at zib.de 
> <mailto:hendel at zib.de>>) escribió:
>
>     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  <mailto:Scip at zib.de>
>>     https://listserv.zib.de/mailman/listinfo/scip
>
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto: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/913154a1/attachment.html>