[SCIP] Processed / open / pruned nodes

[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>)
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>)
> 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/20190814/5ea07748/attachment.html>