[SCIP] Processed / open / pruned nodes
Gregor Hendel
hendel at zib.de
Fri Aug 16 10:13:08 CEST 2019
Hi Lara,
Sorry, apparently I forgot to mention that there is also the category
SCIPgetNObjlimLeaves(), which is increased every time that the node LP
is interrupted because it hit the objective limit. This is also a sort
of pruning. If no nodes are "pruned" as in your formula below, the
search process solves all terminal nodes, such that they are either
"objlimleaves", integral (in which case, SCIPgetNFeasibleLeaves() is
increased by 1), or infeasible (in which case,
SCIPgetNInfeasibleLeaves() is increased by 1).
All the above types of nodes are accounted for by SCIPgetNNodes().
Does this explain the observation in your experiment?
Best,
Gregor
Am 14.08.19 um 10:44 schrieb Lara Scavuzzo:
> Dear SCIP community,
>
> I still have not been able to solve the problem I reported in my
> previous emails.
>
> Any help is appreciated.
>
> Best,
>
> Lara
>
>
> El lun., 5 ago. 2019 a las 17:23, Lara Scavuzzo (<lascavuzzo at gmail.com
> <mailto:lascavuzzo at gmail.com>>) escribió:
>
> 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
> <mailto: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 <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
>>
>
>
> _______________________________________________
> 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/20190816/2a40b2e2/attachment.html>
More information about the Scip
mailing list