The BB tree tab of the Run Bar

The Branch and Bound tree is a representation of the search for an integer solution when optimizing MIP problems. To enable/disable drawing the BB tree use the Run Options dialog.

Notes:

• The tree is displayed for Mosel as well as Optimizer runs and it is updated continuously during the MIP search (to enable the names used in the Mosel model to appear in the tree, set the "mmxprs" boolean parameter XPRS_LOADNAMES to true).
• White nodes are either still active or in-tree.
• Red nodes are infeasible.
• Yellow nodes are cut off.
• The 20 most recent nodes are in decaying shades of blue, with bright blue being the most recent.
• The green nodes represent solutions. The best solution so far is green and large. The brighter the color, the more recent the solution.
• When hovering the mouse above a green solution node, a number will appear next to all solution nodes, indicating the order in which the solutions were found.
• If fewer than 5000 nodes have been visited so far, the entire tree will be drawn (see above).
• If more than 5000 nodes have been visited, only nodes up to a depth of 10 will be drawn fully. The rest of the tree is summarized by scattered dots (which will turn into real nodes when zooming). Solutions and the 20 most recent nodes (in blue) are displayed regardless of their depth:
  
• Zoom in by holding the left mouse button down, dragging right and down and releasing it. A rectangle will indicate the area to be zoomed.
• Return to full tree view by clicking the left mouse button when zoomed.
• When zoomed, the lower left corner shows a scheme of the entire tree, while the "porthole" (representing the area seen in the main tree window) is highlighted:
  
• To move around in the tree when zoomed, hold the right mouse button down and drag in any direction. The small preview window in the corner will continuously reflect the new position in the tree.
• The arrow keys will also move around in the tree (ensure the tree window has the focus by right-clicking in it - do not left click -- that will return to full tree view).
• If lost in the tree or if the image doesn't look correct, left click to return to full view.
• Hovering the mouse above nodes will produce tooltips with information on the current node.
• The tooltips at each non-terminal node contain the following information:
  – Node number
  – Depth
  – Initial branching direction
  – The branching variable and its current relaxed solution value
  – Relaxed objective
  – Current best bound
  – Current best solution
  – Number of descendants
  – How many descendants are cutoff, infeasible, solutions
  – The ten most recent ancestors of the node, each with info on branching direction
  
• Double click on a node to obtain a listing of all of its ancestors (shown in the View text dialog).
• When the optimization is complete, paused or stopped, search for specific branching variables in the tree using the tree highlighter tool (can be enabled/disabled from the Run Options dialog): just select a variable name from the drop list and all visible nodes branching on that variable will begin to flash in alternating blue and yellow.
• To stop highlighting, select the first item in the highlighter tool droplist: the blank.
• While there is no limit on the size of the displayed tree, if the tree is very large (e.g. over 200,000 nodes on a PIII 800Mhz machine), it will react slowly to user actions.

Parallel branch and bound trees

Note that each branch is colored according to the thread that processed the node. Shown below are trees obtained with 2, 4, and 8 threads.

2 threads	4 threads

8 threads