Default SCIP branching achieving fewer nodes than FSB?

[cwfparsonson]

Hi,

I am trying to implement the default SCIP branching heuristic used as a benchmark by Gasse et al. 2019. I am using the ecole configuring environment as in the notebook example https://github.com/ds4dm/ecole/blob/master/examples/branching-imitation.ipynb. However, I am finding that the default SCIP branching heuristic is resulting in fewer nodes than full strong branching (FSB), which is different from what was reported in Table 2 of Gasse et al. Is it possible that the ecole configuring environment adds nodes to the B&B tree differently and therefore would result in a lower number of nodes than FSB? For example, I noticed that Zarpellon et al. 2021 https://arxiv.org/pdf/2002.05120.pdf refer to the 'fair number of nodes' for benchmarking relpscost branching - do I need to somehow measure the number of nodes differently to accurately benchmark the default SCIP branching heuristic?

Please let me know if it would be useful for me to post a minimal code example of my SCIP branching + FSB implementation.

[AntoinePrv]

Hi @cwfparsonson,

I have some partial answer, hope this can help you in some way.

Is it possible that the ecole configuring environment adds nodes to the B&B tree differently

The configuring environment itself is pretty light. It sets parameters on the solver, and then let it run as implemented in SCIP (simply calling SCIPsolve), so it would not be my #1 suspect.

which is different from what was reported in Table 2 of Gasse et al

There could be many difference between that enviornment and the setting of Gasse et al. (2019).

• They used SCIP6, while Ecole keeps up to date with latest SCIP (now 7, and soon 8);
• They have different setting, such as deactivating cutting planes, while the configuring environments keeps everything (except the parameters you pass) as default.

I am finding that the default SCIP branching heuristic is resulting in fewer nodes than full strong branching.

Although it is not a guarantee the FSB produce smaller tree, it is surprising. I don't have more insights to offer...

I noticed that Zarpellon et al. 2021 refer to the 'fair number of nodes' for benchmarking relpscost branching - do I need to somehow measure the number of nodes differently to accurately benchmark the default SCIP branching heuristic?

If I understand correctly, using fair node counting would result in FSB having even more node (looking at Gamrath and
Schubert (2018), it seem to be the case). So it does not answer your question...

[cwfparsonson]

Hi @AntoinePrv ,

Many thanks for the fast reply and apologies it has taken me a while to respond.

There could be many difference between that enviornment and the setting of Gasse et al. (2019).

Understood - I'm not really trying to reproduce the exact numbers, I'm more just trying to figure out if it makes sense for SCIP branching to be better than FSB (in terms of # nodes), and the Gasse et al. paper had a table showing that it wasn't the case, which makes more sense to me.

They have different setting, such as deactivating cutting planes, while the configuring environments keeps everything (except the parameters you pass) as default.

Just to point out, I am passing the exact same scip_params argument to both the configuring (SCIP branching) and the branching (FSB) environments, so they should both have the same things disabled. I'll add a minimal code example below just to be clear about this.

I suppose my real underlying question is: what is the most effective way to use ecole to establish an SCIP branching benchmark so that I can compare it with ML branching agents. My current thinking is that it seems unlikely SCIP branching beats FSB in terms of number of nodes (given how much faster SCIP branching is, I don't see how it could be doing something more effective than a lookahead for all actions), therefore the way nodes are added to the tree is different and so I should omit number of nodes comparisons and focus on solving time benchmarks?

SCIP params I'm using:

DEFAULT_SCIP_PARAMS = {'separating/maxrounds': 0,
                                                 'separating/maxroundsroot': 0,
                                                 'separating/maxcuts': 0,
                                                 'separating/maxcutsroot': 0,
                                                 'presolving/maxrounds': 0,
                                                 'presolving/maxrestarts': 0,
                                                 'propagating/maxrounds':0,
                                                 'propagating/maxroundsroot':0,
                                                 'lp/initalgorithm':'d',
                                                 'lp/resolvealgorithm':'d',
                                                 'limits/time': 3600}

Branching environment defined for FSB:

class EcoleBranching(ecole.environment.Branching):
    def __init__(
        self,
        observation_function='default',
        information_function='default',
        reward_function='default',
        scip_params='default',
        pseudo_candidates=False,
    ):
        self.pseudo_candidates = pseudo_candidates

        # init functions from strings if needed
        if reward_function == 'default':
            reward_function = ({
                     'num_nodes': -ecole.reward.NNodes(),
                     'lp_iterations': -ecole.reward.LpIterations(),
                     'solving_time': -ecole.reward.SolvingTime(),
                 })
        if information_function == 'default':
            information_function=({
                     'num_nodes': ecole.reward.NNodes().cumsum(),
                     'lp_iterations': ecole.reward.LpIterations().cumsum(),
                     'solving_time': ecole.reward.SolvingTime().cumsum(),
                 })
        if observation_function == 'default':    
            observation_function = (ecole.observation.NodeBipartite())
        if scip_params == 'default':
            scip_params = DEFAULT_SCIP_PARAMS
        
        super(EcoleBranching, self).__init__(
            observation_function=observation_function,
            information_function=information_function,
            reward_function=reward_function,
            scip_params=scip_params,
            pseudo_candidates=pseudo_candidates,
        )

Configuring environment defined for SCIP default branching:

class EcoleConfiguring(ecole.environment.Configuring):
    def __init__(self,
                 observation_function='default',
                 information_function='default',
                 scip_params='default'):

        # init functions from strings if needed
       if observation_function == 'default':    
            observation_function=None
        if information_function == 'default':
            information_function=({
                     'num_nodes': ecole.reward.NNodes().cumsum(),
                     'lp_iterations': ecole.reward.LpIterations().cumsum(),
                     'solving_time': ecole.reward.SolvingTime().cumsum(),
                 })
        if scip_params == 'default':
            scip_params = DEFAULT_SCIP_PARAMS

        super(EcoleConfiguring, self).__init__(observation_function=observation_function,
                                                                       information_function=information_function,
                                                                       scip_params=scip_params)

[AntoinePrv]

I suppose my real underlying question is: what is the most effective way to use ecole to establish an SCIP branching benchmark so that I can compare it with ML branching agents.

It's using the Configuring environment, as you've done and as is done in the notebook. This part looks correct.

My current thinking is that it seems unlikely SCIP branching beats FSB in terms of number of nodes.

While possible, I agree it is suspicisous. How did you setup strong branching baseline for your comparison? Same as in the notebook?

[cwfparsonson]

Hi @AntoinePrv,

Yes, I am using the same strong branching setup as in the notebook. Here is my implementation (using the above EcoleBranching and EcoleConfiguring classes):

num_instances = 10
seed = 0

SCIP Branching

# init env and instance generator
ecole.seed(seed)
env = EcoleConfiguring(observation_function='default',
                                  information_function='default',
                                  scip_params='default')
instances = ecole.instance.SetCoverGenerator(n_rows=500, n_cols=1000, density=0.05)

# solve instances
for i in range(num_instances):
    done = True
    while done:
        # find instance which is not pre-solved
        instance = next(instances)
        env.seed(seed)
        obs, action_set, reward, done, info = env.reset(instance)
    
    obs, action_set, reward, done, info = env.step({})
    print(f'Instance {i+1} num nodes with default SCIP: {info["num_nodes"]}')

Output:

Instance 1 num nodes with default SCIP: 1.0
Instance 2 num nodes with default SCIP: 3.0
Instance 3 num nodes with default SCIP: 1.0
Instance 4 num nodes with default SCIP: 3.0
Instance 5 num nodes with default SCIP: 5.0
Instance 6 num nodes with default SCIP: 1.0
Instance 7 num nodes with default SCIP: 8.0
Instance 8 num nodes with default SCIP: 1.0
Instance 9 num nodes with default SCIP: 9.0
Instance 10 num nodes with default SCIP: 1.0

Strong Branching

# init agent, env, and instance generator
class StrongBranchingAgent:
    def __init__(self, pseudo_candidates=False, name='sb'):
        self.name = name
        self.pseudo_candidates = pseudo_candidates
        self.strong_branching_function = ecole.observation.StrongBranchingScores(pseudo_candidates=pseudo_candidates)

    def before_reset(self, model):
        """
        This function will be called at initialization of the environment (before dynamics are reset).
        """
        self.strong_branching_function.before_reset(model)
    
    def extract(self, model, done):
        return self.strong_branching_function.extract(model, done)

    def action_select(self, action_set, model, done, **kwargs):
        scores = self.extract(model, done)
        action_idx = scores[action_set].argmax()
        return action_set[action_idx], action_idx
    
agent = StrongBranchingAgent()
ecole.seed(seed)
env = EcoleBranching(observation_function='default',
                      information_function='default',
                      reward_function='default',
                      scip_params='default')
instances = ecole.instance.SetCoverGenerator(n_rows=500, n_cols=1000, density=0.05)

# solve instances
for i in range(num_instances):
    done = True
    while done:
        # find instance which is not pre-solved
        instance = next(instances)
        agent.before_reset(instance)
        env.seed(seed)
        obs, action_set, reward, done, info = env.reset(instance)
    
    while not done:
        action, action_idx = agent.action_select(action_set=action_set, model=env.model, done=done)
        obs, action_set, reward, done, info = env.step(action)
    print(f'Instance {i+1} num nodes with Strong Branching: {info["num_nodes"]}')

Output:

Instance 1 num nodes with Strong Branching: 11.0
Instance 2 num nodes with Strong Branching: 7.0
Instance 3 num nodes with Strong Branching: 3.0
Instance 4 num nodes with Strong Branching: 21.0
Instance 5 num nodes with Strong Branching: 27.0
Instance 6 num nodes with Strong Branching: 9.0
Instance 7 num nodes with Strong Branching: 36.0
Instance 8 num nodes with Strong Branching: 5.0
Instance 9 num nodes with Strong Branching: 23.0
Instance 10 num nodes with Strong Branching: 11.0

As you can see, SCIP achieves a very low number of nodes (far lower than strong branching, pseudocost branching, trained imitation learning agents, etc.).

[AntoinePrv]

I made a minimally reproducible example, and I can confirm what you observe.

import ecole


DEFAULT_SCIP_PARAMS = {
    "separating/maxrounds": 0,
    "separating/maxroundsroot": 0,
    "separating/maxcuts": 0,
    "separating/maxcutsroot": 0,
    "presolving/maxrounds": 0,
    "presolving/maxrestarts": 0,
    "propagating/maxrounds": 0,
    "propagating/maxroundsroot": 0,
    "lp/initalgorithm": "d",
    "lp/resolvealgorithm": "d",
    "limits/time": 3600,
}


ecole.seed(43)
instances = ecole.instance.SetCoverGenerator(n_rows=500, n_cols=1000, density=0.05)
conf_env = ecole.environment.Configuring(
    information_function=ecole.reward.NNodes().cumsum(),
    scip_params=DEFAULT_SCIP_PARAMS,
)
conf_env.seed(43)
branch_env = ecole.environment.Branching(
    information_function=ecole.reward.NNodes().cumsum(),
    observation_function=ecole.observation.StrongBranchingScores(),
    scip_params=DEFAULT_SCIP_PARAMS,
)
branch_env.seed(43)

# solve instances
for i in range(10):
    # Find non easy instance
    while True:
        instance = next(instances)
        copy = instance.copy_orig()
        copy.set_params(DEFAULT_SCIP_PARAMS)
        copy.presolve()
        if not copy.is_solved:
            break

    # Solve with SCIP default
    _, _, _, _, info = conf_env.reset(instance)
    _, _, _, _, info = conf_env.step({})
    print(f"[Default] Instance {i+1} num nodes: {info}")

    # Solve with Strong branching
    obs, action_set, _, done, info = branch_env.reset(instance)
    while not done:
        obs, action_set, _, done, info = branch_env.step(action_set[obs[action_set].argmax()])
    print(f"[Strong]  Instance {i+1} num nodes: {info}")

Another experiment confirmed that ecole.observation.StrongBranchingScores does not change the number of nodes as observed by SCIP and ecole.reward.NNodes, so this is not a problem of measuring the wrong thing.

Then I ran strong branching as defined in SCIP:

import ecole

DEFAULT_SCIP_PARAMS = {
    "separating/maxrounds": 0,
    "separating/maxroundsroot": 0,
    "separating/maxcuts": 0,
    "separating/maxcutsroot": 0,
    "presolving/maxrounds": 0,
    "presolving/maxrestarts": 0,
    "propagating/maxrounds": 0,
    "propagating/maxroundsroot": 0,
    "lp/initalgorithm": "d",
    "lp/resolvealgorithm": "d",
    "limits/time": 3600,
}


ecole.seed(43)
instances = ecole.instance.SetCoverGenerator(n_rows=500, n_cols=1000, density=0.05)

# solve instances
for i in range(10):
    # Find non easy instance
    while True:
        instance = next(instances)
        copy = instance.copy_orig()
        copy.set_params(DEFAULT_SCIP_PARAMS)
        copy.presolve()
        if not copy.is_solved:
            break

    copy = instance.copy_orig()
    copy.set_params(DEFAULT_SCIP_PARAMS)
    copy.solve()
    print(f"[Default]             Instance {i+1} num nodes: {copy.as_pyscipopt().getNNodes()}")

    copy = instance.copy_orig()
    copy.set_params({**DEFAULT_SCIP_PARAMS, "branching/fullstrong/priority": 536870911})
    copy.solve()
    print(f"[FullStrong]          Instance {i+1} num nodes: {copy.as_pyscipopt().getNNodes()}")

    copy = instance.copy_orig()
    copy.set_params({**DEFAULT_SCIP_PARAMS, "branching/allfullstrong/priority": 536870911})
    copy.solve()
    print(f"[AllFullStrong]       Instance {i+1} num nodes: {copy.as_pyscipopt().getNNodes()}")

    copy = instance.copy_orig()
    copy.set_params({**DEFAULT_SCIP_PARAMS, "branching/vanillafullstrong/priority": 536870911})
    copy.solve()
    print(f"[VanillaFullStrong]   Instance {i+1} num nodes: {copy.as_pyscipopt().getNNodes()}")

Interestingly, we see that SCIP's VanillaFullStrongBranching (that we use in ecole.observation.StrongBranchingScores) does not perform well.

[Default]             Instance 1 num nodes: 1
[FullStrong]          Instance 1 num nodes: 1
[AllFullStrong]       Instance 1 num nodes: 1
[VanillaFullStrong]   Instance 1 num nodes: 5
[Default]             Instance 2 num nodes: 6
[FullStrong]          Instance 2 num nodes: 3
[AllFullStrong]       Instance 2 num nodes: 1
[VanillaFullStrong]   Instance 2 num nodes: 9
[Default]             Instance 3 num nodes: 1
[FullStrong]          Instance 3 num nodes: 1
[AllFullStrong]       Instance 3 num nodes: 1
[VanillaFullStrong]   Instance 3 num nodes: 1
[Default]             Instance 4 num nodes: 3
[FullStrong]          Instance 4 num nodes: 1
[AllFullStrong]       Instance 4 num nodes: 1
[VanillaFullStrong]   Instance 4 num nodes: 9
[Default]             Instance 5 num nodes: 1
[FullStrong]          Instance 5 num nodes: 1
[AllFullStrong]       Instance 5 num nodes: 1
[VanillaFullStrong]   Instance 5 num nodes: 1
[Default]             Instance 6 num nodes: 5
[FullStrong]          Instance 6 num nodes: 5
[AllFullStrong]       Instance 6 num nodes: 3
[VanillaFullStrong]   Instance 6 num nodes: 10
[Default]             Instance 7 num nodes: 5
[FullStrong]          Instance 7 num nodes: 3
[AllFullStrong]       Instance 7 num nodes: 3
[VanillaFullStrong]   Instance 7 num nodes: 13
[Default]             Instance 8 num nodes: 173
[FullStrong]          Instance 8 num nodes: 31
[AllFullStrong]       Instance 8 num nodes: 27
[VanillaFullStrong]   Instance 8 num nodes: 96
[Default]             Instance 9 num nodes: 7
[FullStrong]          Instance 9 num nodes: 7
[AllFullStrong]       Instance 9 num nodes: 1
[VanillaFullStrong]   Instance 9 num nodes: 13
[Default]             Instance 10 num nodes: 17
[FullStrong]          Instance 10 num nodes: 11
[AllFullStrong]       Instance 10 num nodes: 3
[VanillaFullStrong]   Instance 10 num nodes: 40

So my guess would be:

• a. ecole.observation.StrongBranchingScores + action_set[branching_scores[action_set].argmax()] is similar to SCIP's VanillaFullStrongBranching (@gasse is this correct ?)
• b. This branching rule is only a poor imitation of SCIP's full strong branching.

cc: @gasse @dchetelat If my hypothesis is correct, we should change the way we evaluate strong branching in the branching tutorial.

[gasse]

Hi all. To me the observed numbers are not surprising. There are a few different things to keep in mind.

1) SCIP branching rule vs Ecole branching policy

From a POMDP perspective, the internal branching rules of SCIP (or any other solver) are cheating, in the sense that they are allowed to do much more than branching:

• they can tighten the local LP through propagation
• they can prune nodes immediately (extreme case of LP tightening)
• they can update any solver statistics
• they can add extra cutting planes
• ...

Basically, most of the internal branching rules of SCIP will do everything they can to leverage the computations required by the branching rule, in order to speed up solving. But by doing so, they do not adhere to the POMDP framework of Ecole. As a result, the total number of nodes resulting from an internal branching rule can not be attributed solely to the branching decisions made, but also to all the other extra stuff that happened within the branching rule. This issue is very related to the fair node counting problem.

Note that the vanillafullstrong branching rule was implemented precisely to address this issue, and corresponds to the fullstrong branching rule deprived of everything except choosing a branching variable (even updating the solver statistics can be deactivated, with the parameter branching/vanillafullstrong/idempotent = True). Thus, the node count of vanillafullstrong is fair, while the node count of fullstrong in general is not.

2) Full Strong Branching is not always optimal

While everyone agrees that FSB results in general in small trees, it is also known that it is not optimal in general. There are plenty of smart things implemented in SCIP's default branching rule relpscost, which can result in smaller branching trees than FSB on some instances. Still, in general, and in particular with instances requiring more than 100 nodes, we observed that FSB results in smaller trees than the default rule.

3) Easy vs hard instances

Last, the experience you report seems to focus on easy instances (< 10 nodes), for which branching decisions do not have such a big impact. I would suggest repeating the experiment with more challenging ones (> 100 nodes with default SCIP) to better compare different branching rules.

Hope that helps !

Maxime