search

ds4dm / ecole

Extensible Combinatorial Optimization Learning Environments
https://www.ecole.ai
BSD 3-Clause "New" or "Revised" License
324 stars 68 forks source link

Fair node counting #92

Open dchetelat opened 4 years ago

dchetelat commented 4 years ago

For benchmarking purposes (I think mostly for reliability pseudocost and allfullstrong in branching?), it would be good to implement as a reward/metric fair node counting.

Currently, this is implementing in the branching work by monitoring the SCIP branching results SCIP_RESULT.REDUCEDDOM and SCIP_RESULT.CUTOFF, and the fair node count is nnodes+2*(ndomchgs+ncutoffs). We could do the same thing, although maybe it is inefficient. Perhaps there is a way to implement this with an event handler, which would probably be more efficient, although I am not certain how.

Alternatively, in the SCIP 7 release nodes, there is a mysterious sentence:

SCIP 7.0 comes with an updated version of the look ahead branching rule introduced in SCIP6.0 [36]. First, new scoring schemes have been introduced to compute a score fora candidate variable based on the LP bounds predicted for the child nodes and potential grand child nodes. The new default scheme computes the score as the product of the products of the dual bound gains for the two best pairs of grandchild nodes, with one pair per child node. This approach is similar to the product score (13). Additionally, the relative number of infeasible grandchild nodes is added, weighted with the average score obtained from any pairs of grandchild nodes. In computational experiments on the MMMC test set, the new scoring scheme reduced the average solving time, tree size, and fair node number [30] for instances solved within the time limit of two hours by more than 15 % compared to the old SCIP default.

This makes me wonder if it was implemented as a metric in SCIP 7, but I could not find it anywhere, so I supposed they computed it by hand in this experiment. That is, there doesn't seem to be any easy SCIPgetFairNNodes function.

elichienxD commented 3 years ago

Hi,

I wonder if the fair node counting feature is implemented. If not do you have any suggestion for ad-hoc modification to get the fair node counting?

Thanks!

dchetelat commented 3 years ago

No this has not been implemented yet! What are you trying to do, exactly?

elichienxD commented 3 years ago

Just wanna see the fair node counting in addition to the standard one. From this paper [1] it seems like it is more appropriate to compare ML methods with SCIP default policy with fair node counting?

[1] Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies, Zarpellon et al. https://arxiv.org/pdf/2002.05120.pdf

gasse commented 3 years ago

SCIP's default policy is not really compatible with fair node counting, as it has many side-effects besides taking branching decisions. Tracking all those side-effects (mostly variable tightenings) to compute a fair number of nodes is technically hard, and has not been implemented in Ecole. However, in general any branching policy which is implemented via the Ecole API can be interpreted as an oracle with no side-effect, and can directly be evaluated in terms of fair node counting by measuring the final number of nodes (tree size).

Finally, note that the fair node number should not be measured in a default solving setting, as the optimal solution should be provided from the start to alleviate any side-effect due to node selection and primal heuristics. See Measuring the Impact of Branching Rules for Mixed-Integer Programming Gerald Gamrath, Christoph Schubert, 2018