[SCIP] Processed / open / pruned nodes

[Lara Scavuzzo]

Dear Gregor,

I have experienced some weird behavior using the method that I implemented
following your instructions.


In particular, I noticed that if I enable all default heuristics the number
of pruned nodes remains zero during the whole process. In order to
investigate this, I observed the evolution of the number of open nodes
(obtained as SCIPgetNChildren() + SCIPgetNLeaves() + SCIPgetNSiblings() ).
If no nodes are pruned, the number of open nodes should increase linearly.
However, this is not the case (see attached figure).


I wonder if this has anything to do with heuristics, cutting planes, etc. ?

As I mentioned in my first email, I would like to know the number of pruned
nodes by all processes (bound, integrality and infeasibility).


Best regards,


Lara Scavuzzo

El jue., 25 jul. 2019 a las 19:06, Gregor Hendel (<hendel at zib.de>) escribió:

> 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>)
> 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 listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>>
>>
>> _______________________________________________
>> 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/20190805/a319af42/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: openn.png
Type: image/png
Size: 107564 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20190805/a319af42/attachment.png>