7
$\begingroup$

What insights/info can be gathered from visualizing the Branch & Bound tree. Some commercial solvers (FICO Xpress) don't seem to provide any API to readily visualize the tree. It has to be implemented using callback functions.

$\endgroup$
2
  • 4
    $\begingroup$ Opinion: On most real-world problems, I would expect the B&B tree to be much too big for visualization. You could hypothetically program something that lets the user interactively expand nodes to obtain their children, but that would result in enough clicking to give the user a near-fatal repetitive strain injury with likely not much to show for it. $\endgroup$
    – prubin
    Commented Apr 27, 2022 at 18:32
  • $\begingroup$ Maybe the better visualization between the parent's nodes and whose children. Otherwise, AFAIK, all of the things you need can be invoked from the solving log or inside the callbacks. $\endgroup$
    – A.Omidi
    Commented Apr 27, 2022 at 18:37

1 Answer 1

7
$\begingroup$

Years ago I wrote an application that could visualize branch and bound trees. The tree was depicted on a scrollable canvas. You could zoom in and out and move similar to navigating Google maps. No clicking or expanding required. Nodes were colored. The colored nodes indicated where feasible solutions were found, which nodes were pruned, which nodes were infeasible, which node was optimal, etc. Arcs would show branching decisions. Vertices would show bounds, and a counter when the node was explored.

While all the information visualized in the tree could also be derived from log files, I found the visualization quite informative to look at. A few things that you could learn from the trees:

  • when implementing custom branching decisions, are the subtrees balanced?
  • where in the tree are the feasible solutions found?
  • do we run into symmetry problems where we spend a lot of time searching through subtrees representing symmetrical solutions?
  • how do different branching orders work, e.g. Dfs versus best first search, etc
  • how do the bounds improve throughout the search tree.
  • are there uninteresting parts of the tree that we want to avoid, e.g. through a heuristic?

Naturally there's a point where the trees become too big to extract useful information.

Although I can't seem to find the application I was referring to, here's an image I generated with a predecessor of the application in a Branch-and-Price application. This only shows a very small instance. You need the zooming capability to visualize larger trees: enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.