Hard-coded vanilla strong branching does not get the same performance as SCIP vanilla strong branching

[margotcosson]

Describe the bug

First, I apologize if it is not a bug but a misunderstanding on my part. I am studying learning on branching so I a am very glad to be able to use ecole. However, I encountered a strange behavior : when I compare the tree sizes (number of nodes) of problems solved with

• a hard-coded vanilla full strong branching thanks to ecole.dynamics.BranchingDynamics
• the vanilla full strong branching of SCIP observed via a ecole.dynamics.ConfiguringDynamics

I am getting smaller tree sizes with the second one. To be sure that it was not a question of random seed, I tested it on 500 set covering instances (n_rows=200, n_cols=200, density=0.1) and on 100 bigger set covering instances (n_rows = 300, n_cols = 300, density = 0.1). I got the following plots :

500 instances (200, 200, 0.1) :

100 instances (300, 300, 0.1) :

My code is the following :

import ecole
from pyscipopt import scip
import matplotlib.pyplot as plt
from tqdm import tqdm

generator = ecole.instance.SetCoverGenerator(n_rows=200, n_cols=200, density=0.1)

class SimpleBranchingDynamics(ecole.dynamics.BranchingDynamics):
    def __init__(self):
        super().__init__()

    def reset_dynamics(self, model):
        pyscipopt_model = model.as_pyscipopt()
        pyscipopt_model.setPresolve(scip.PY_SCIP_PARAMSETTING.OFF) # deactivate presolve
        pyscipopt_model.setHeuristics(scip.PY_SCIP_PARAMSETTING.OFF) # deactivate heuristics
        pyscipopt_model.setSeparating(scip.PY_SCIP_PARAMSETTING.OFF) # deactivate cutting planes
        pyscipopt_model.setParam('estimation/restarts/restartpolicy', 'n') # disable restarts
        return super().reset_dynamics(model)

class SimpleConfiguringDynamics(ecole.dynamics.ConfiguringDynamics):
    def __init__(self, branching_method=None):
        super().__init__()
        self.branching_method = branching_method

    def reset_dynamics(self, model):
        pyscipopt_model = model.as_pyscipopt()
        pyscipopt_model.setPresolve(scip.PY_SCIP_PARAMSETTING.OFF) # deactivate presolve
        pyscipopt_model.setHeuristics(scip.PY_SCIP_PARAMSETTING.OFF) # deactivate heuristics
        pyscipopt_model.setSeparating(scip.PY_SCIP_PARAMSETTING.OFF) # deactivate cutting planes
        pyscipopt_model.setParam('estimation/restarts/restartpolicy', 'n') # disable restarts
        if self.branching_method is not None: pyscipopt_model.setParam("branching/" + self.branching_method + "/priority", 10001)
        return super().reset_dynamics(model)

class SimpleBranching(ecole.environment.Environment):
    __Dynamics__ = SimpleBranchingDynamics

class SimpleConfiguring(ecole.environment.Environment):
    __Dynamics__ = SimpleConfiguringDynamics

vanilla_sb_env = SimpleConfiguring(observation_function=None,
                                   branching_method="vanillafullstrong",
                                   information_function=ecole.reward.NNodes())
vanilla_sb_env.seed(0)
full_sb_env = SimpleConfiguring(observation_function=None,
                                   branching_method="fullstrong",
                                   information_function=ecole.reward.NNodes())
full_sb_env.seed(0)
handwritten_sb_env = SimpleBranching(observation_function=ecole.observation.StrongBranchingScores(),
                                     information_function=ecole.reward.NNodes())
handwritten_sb_env.seed(0)

vanilla_scores = []
full_scores = []
handwritten_scores = []

nb_runs = 500 # put 1 if you want to debug only on one instance
for i in tqdm(range(nb_runs)):
    instance = next(generator)

    observation, action_set, _, done, info = vanilla_sb_env.reset(instance)
    _, _, _, _, info = vanilla_sb_env.step({})
    vanilla_scores.append(info)

    observation, action_set, _, done, info = full_sb_env.reset(instance)
    _, _, _, _, info = full_sb_env.step({})
    full_scores.append(info)

    observation, action_set, _, done, info = handwritten_sb_env.reset(instance)
    nb_nodes = info
    while not done:
        sb_scores = observation
        action = action_set[sb_scores[action_set].argmax()]
        observation, action_set, _, done, info = handwritten_sb_env.step(action)
        nb_nodes += info
    handwritten_scores.append(nb_nodes)

plt.plot(sorted(vanilla_scores), label = 'vanilla sb')
plt.plot(sorted(handwritten_scores), label = "handwritten sb")
plt.plot(sorted(full_scores), label= "full sb")
plt.title("Number of nodes comparison")
plt.legend()
plt.savefig("crashtest_results.png")

Once again, sorry if this is not a bug but a mistake on my part. Furthermore, I tried to understand the issue by mylself but I did not success to run SCIP vanilla strong branching inside ecole (with ecole.dynamics.ConfiguringDynamics or others) while getting the strong branching scores, the action set and the decision made by SCIP at each node.

Setting

• OS: Linux
• Python version: 3.7.3
• Ecole version: 0.8.0

To Reproduce

You can run the code above if you want to reproduce the plot. Otherwise, if you want to test the two models on one instance, you can run the code above with nb_runs = 1.

Expected behavior

As expected, full strong branching is getting better result than vanilla strong branching as it allows several deductions during gathering of strong branching scores. For the two others, I would expect hard-coded vanilla strong branching and SCIP vanilla strong branching to perform the same, at least in average.

Additional context

[gasse]

Hi @margotcosson ,

The origin of this discrepancy is in the branching/vanillafullstrong/idempotent parameter, which is set to False by default when you use the vanillafullstrong branching rule in SCIP. Without idempotence SCIP triggers side-effects during the computation of the strong branching scores, which reduces the tree size. When we extract strong branching scores in Ecole we set this parameter to True, so that extracting this observation does not change the state of the environment (or at least minimizes the amount of changes, some changes will still happen, such as the state of the LP solver).

Here is a reproduction of your experiment with the fix

 vanilla_sb_env = SimpleConfiguring(observation_function=None,                   
                                    branching_method="vanillafullstrong",        
                                    scip_params={"branching/vanillafullstrong/idempotent": True},
                                    information_function=ecole.reward.NNodes())

Hope that helps.

Best, Maxime

[margotcosson]

Hello Mr Gasse, Thank you very much for your answer, it does help a lot. I'll be able to make fair comparisons in my work. Thanks again ! Best, Margot