Is there good choices of the rewards functions used for one-step updating of the RL policy .

[kevin031060]

We can optimize an instance to be solved and collect the getNNnodes() or Solvingtime() as the eposide reward. Is there good choices of the rewards functions used for one-step updating of the RL policy?
I'm new to this field of B&B. Can anybody give some advices.

[AntoinePrv]

That's a good and open question. It's true that the number of nodes will increase by one on every Branching transition and and so is a poor signal to immediately update the policy.
I believe the solving time per node would also be either quite similar, or widely different but unrelated to branching (e.g. running heuristics, generating cuts...).

That leaves us with things such as primal/dual bounds improvement, so perhaps Primal and Dual Integrals.

Alternatively, there are expert policies that give scores for each decision (Pseudo-costs, Strong Branching), so they may be adapted into a reward, but I'm not sure what would be the advantage of doing this over imitation learning.

[gasse]

Hi @kevin031060 ,

Yes, in Ecole's branching environment SCIP is always processing a specific node, the current node. SCIP's node selection strategy is responsible for deciding in which order nodes are processed. See the SCIP documentation. The default node selection strategy in SCIP is called best estimate search.

You can access and collect information from other nodes as well, such as their depth or their domain changes, although I believe only the currently focused node has its LP constructed, so you won't be able to extract much LP-related information until those nodes are themselves focused by SCIP.

Hope that helps,
Maxime

[kevin031060]

Thank you for your reply. It helps a lot!

[kevin031060]

That's a good and open question. It's true that the number of nodes will increase by one on every Branching transition and and so is a poor signal to immediately update the policy.

I saw that the "nb_nodes" sometimes might not increase by one (might increase a lot) on each Branching transition. It occurs because a feasible solution is found and some nodes are prune?

[gasse]

Hi @kevin031060 ,

Usually what happens is the following:

• SCIP selects an open node (non-processed)
• SCIP processes it (solves the LP) and finds a non-integer LP solution
• SCIP invokes the branching rule to split the node and create children nodes (usually 2)

So in-between each branching decision, SCIP only processes 1 additional node, hence the SCIPgetNNodes() value gains +1.

Sometimes, what might happen is that the LP is infeasible, or the LP solution is integral (satisfies the MILP integrality constraints). In that case, SCIP will not invoke the branching rule, and simply move on, select another node, and process it. In that case, the number of processed nodes in-between each branching decision can be greater than 1. This is not directly a result of pruning, but it is related in the sense that pruning can also happen when an integer solution is found.

Hope that helps,

Best,
Maxime

[kevin031060]

Really appreciate your response. I understand it now.