How to see each branch and bound node (instance trivially solved)

[alonsoleal1]

Hello everyone,
I have recently started using this library along with the python SCIOPT library, I am trying to visualize what is actually happening in the code, and before trying complicated models I would like to see the steps on how to resolve the following problem model written in SCIOPT using Branch and Bound:

model = Model("Example")  # model name is optional
x = model.addVar("x", vtype="INTEGER")
y = model.addVar("y", vtype="INTEGER")
model.setObjective(-1*(3*x + 5*y))
model.addCons(x + y <= 10)
model.addCons(2*x + 4*y <= 25)
model.addCons(x <= 8)
model.addCons(2*y <= 10)
model.setPresolve(PY_SCIP_PARAMSETTING.OFF)
model.writeProblem(filename="model1.cip")
model.optimize()
sol = model.getBestSol()
print("x: {}".format(sol[x]))
print("y: {}".format(sol[y]))

This code in fact returns the MAX solution to this problem. But now using Ecole I would like to see the steps that are taken in order to get to this result. I have followed the source code and have defined the simple branching class with presolve and separating off, now if i run the following code:

for _ in range(1):
    observation, action_set, reward_offset, done, info = env.reset("model1.cip")
    print(observation, action_set, reward_offset, done, info)
    while not done:
        observation, action_set, reward, done, info = env.step(action_set[0])

The output is only : None None 1.0 True {}

Does anyone know how i could actually see the observation, action_set and reward_offset for every node or every x nodes that is being worked on?
Thanks a lot.

[AntoinePrv]

Hello @alonsoleal1 ,

Could you provide some details on what env is here, i.e. how you constructed it?

It looks like here, your model1.cip got solved during env.reset, so you never go into the inner loop while not done.
Furthermore, the observation in reset is None because if the model is solved duing reset, some observation_functions are not able to extract an observation (due to SCIP functions no longer being available) and simply return None.

[alonsoleal1]

One last thing, removing the integer constraint from the model I get the solution (7.5,2.5), that means that the (8,2) isn't the initial linear solution. Is there any way for the SCIP to perform one node branch per step, that is showing the step or steps from (7.5,2.5) to (8,2)

[AntoinePrv]

You're correct! Looking at the log in your PySCIPOpt example, even with

model.setPresolve(pyscipopt.scip.PY_SCIP_PARAMSETTING.OFF)
model.setSeparating(pyscipopt.scip.PY_SCIP_PARAMSETTING.OFF)

No branching is done (Solving Nodes : 1).
This seems to come from the heuristics run by SCIP at the root node (the four lines in the table).

Details

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
presolving (0 rounds: 0 fast, 0 medium, 0 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 2 variables (0 bin, 2 int, 0 impl, 0 cont) and 4 constraints
      4 constraints of type <linear>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
i 0.0s|     1 |     0 |     0 |     - |  oneopt|   0 |   2 |   2 |   2 |   0 |  0 |   0 |   0 |-4.900000e+01 |-3.100000e+01 |  58.06%| unknown
  0.0s|     1 |     0 |     2 |     - |   564k |   0 |   2 |   2 |   2 |   0 |  0 |   0 |   0 |-3.500000e+01 |-3.100000e+01 |  12.90%| unknown
r 0.0s|     1 |     0 |     2 |     - |randroun|   0 |   2 |   2 |   2 |   0 |  0 |   0 |   0 |-3.500000e+01 |-3.400000e+01 |   2.94%| unknown
  0.0s|     1 |     0 |     2 |     - |   568k |   0 |   2 |   1 |   2 |   0 |  1 |   0 |   0 |-3.400000e+01 |-3.400000e+01 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : -3.40000000000000e+01 (5 solutions)
Dual Bound         : -3.40000000000000e+01
Gap                : 0.00 %
x: 8.0
y: 2.0

If you are looking for a simple model to try out Ecole, you should play with one of our generator to get models that solves fast enough, but for which SCIP still need to branch.

[alonsoleal1]

Thanks a lot!
Assuming I have a harder model, is there a config to specify the amount of nodes to advance every step? and also is there anyway to bypass that heuristic run at the root node?

[AntoinePrv]

Not at the moment, but I'm working on making this possible. Basically you will be able to not give any variable to let SCIP do it's thing.

[gasse]

Assuming I have a harder model, is there a config to specify the amount of nodes to advance every step? and also is there anyway to bypass that heuristic run at the root node?

You can deactivate all primal heuristics of scip. That can be done using PySCIPOpt, something like this:

model.setHeuristics(pyscipopt.scip.PY_SCIP_PARAMSETTING.OFF)

[gasse]

Hello @alonsoleal1 , aren't you just missing a print in the while not done loop ?

for _ in range(1):
    observation, action_set, reward_offset, done, info = env.reset("model1.cip")
    print(observation, action_set, reward_offset, done, info)
    while not done:
        observation, action_set, reward, done, info = env.step(action_set[0])

Best

[alonsoleal1]

Hello, indeed but i only failed to copy and paste it here, the code itself does have the print. Just as @AntoinePrv said, its being solved during the reset and not even starting the while not done loop