Full search tree information

[Dalinator]

Hi!

I'm looking into using RL to optimize the parameters of a MILP such to optimize the MILP for real world use. In this system the MILP is solved using branch and bound and then the solution is taken by a actor-critic model to optimize and create a policy. Currently i'm using a self implemented branch and bound algorithm but it is not robust and very simple. Therefore i'm looking into integrating a commercial solver to my program. However i need access to all information in the solution three. I.E pruned nodes, so to be able to create a stochastic policy. Is it possible to retrieve the entire search space/solution tree with all information intact?

[abb-omidi]

@Dalinator,

I am unsure if I fully understand what you mean by, is solved using branch and bound and then the solution is taken by a actor-critic model to optimize and create a policy.. However, if you would like to take the information of the B&B tree, the Event Handlers is what you are looking for. I hope it helps.

[Joao-Dionisio]

To expand on @abb-omidi 's answer (thank you!), you would likely want to catch a SCIP_EVENTTYPE.NODESOLVED event, which would trigger and allow you to run your callback. You can find the full list of SCIP events here.

On pyscipopt, you can just use the attach_event_handler functionality like so:

from pyscipopt import Model, SCIP_EVENTTYPE

m = Model()

# you build your model
...

def your_callback_function():
    # record whatever you want to record here. This function will run whenever a node is solved.
    ...

m.attachEventHandlerCallback(your_callback_function, [SCIP_EVENTTYPE.NODESOLVED])
m.optimize()

I haven't run this, so the syntax might be ever so slightly off, but it's roughly this. Hope it helps!

[Dalinator]

I'm sorry if i was unclear i will elaborate, what i need specifically is:

I need to extract from the complete B&B tree after solving is complete:

• The LP solution vector (primal solution x) for every node in the tree
• The dual variables for every node:
  • Shadow prices for equality constraints
  • Shadow prices for inequality constraints
  • Reduced costs for variable bounds
• Branching conditions for every node
• Complete node tree structure including all nodes (both integer-feasible and fathomed/pruned)

This is for machine learning - I need to access every explored node and its LP solution + duals
to compute policy gradients after the solve completes.

[Joao-Dionisio]

@Dalinator, you can collect all of this using the structure I provided above. Here's a semi-working example:

  from pyscipopt import Model, SCIP_EVENTTYPE

  def collect_tree_data(model):
      tree_data = []

      def node_callback(model, event):
          node = model.getCurrentNode()

          node_info = {
              "number": node.getNumber(),
              "depth": node.getDepth(),
              "type": node.getType(),
              "lowerbound": node.getLowerbound(),
              "estimate": node.getEstimate(),
              "parent": node.getParent().getNumber() if node.getParent() is not None else None,
          }

          # Branching decisions
          branchings = node.getParentBranchings()
          if branchings is not None:
              vars_, bounds, bound_types = branchings
              node_info["branchings"] = [
                  {"var": v.name, "bound": b, "type": "lower" if t == 0 else "upper"}
                  for v, b, t in zip(vars_, bounds, bound_types)
              ]

          # LP primal solution
          node_info["primal"] = {var.name: model.getSolVal(None, var) for var in model.getVars()}

          # Dual values
          conss = model.getConss()
          node_info["duals"] = {
              cons.name: model.getDualSolVal(cons)
              for cons in conss if cons.isLinear()
          }

          tree_data.append(node_info)

      model.attachEventHandlerCallback(node_callback, [SCIP_EVENTTYPE.NODESOLVED])
      return tree_data


  # Usage
  m = Model()
  # ... build your model ...

  tree_data = collect_tree_data(m)
  m.optimize()

  # tree_data now contains one dict per explored node
  for node in tree_data:
      print(f"Node {node['number']} (depth {node['depth']}): LB={node['lowerbound']:.4f}")

Please be aware that to access dual values of constraints, the LP solver needs to solve the node. What this means is that you need to disable other methods of solving a node, like presolving and heuristics. You can take a look at the documentation, which contains additional information.

I don't think there's a single nice method that builds the B&B tree, but this can be easily built given the information on the nodes parents.