| |||||||||||
| |||||||||||
Python notebooks Description Python notebooks available in the GitHub repository python-notebooks.
Source Files By clicking on a file name, a preview is opened at the bottom of this page. callback_newnode.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# **Vizualizing the Branch-and-Bound tree of a problem after (partially) solving it**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***callback_newnode.ipynb***\n",
"\n",
"This example shows how to visualize the Branch-and-Bound (B&B) tree of a problem after (partially) solving it. It assumes that all variables to be branched on in the problem are binary variables.\n",
"\n",
"© Copyright 2025 Fair Isaac Corporation\n",
"\n",
"Licensed under the Apache License, Version 2.0 (the \"License\"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0.\n",
" \n",
"Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
"\n",
"This example uses FICO® Xpress software. By running it, you agree to the Community License terms of the [Xpress Shrinkwrap License Agreement](https://community.fico.com/s/contentdocument/06980000002h0i5AAA) with respect to the FICO® Xpress software. See the [licensing options](https://www.fico.com/en/fico-xpress-trial-and-licensing-options) overview for additional details and information about obtaining a paid license."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Install the xpress package\n",
"%pip install -q xpress"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this example, we read a problem from an external file and define **a callback function to save information of each node of the B&B tree during an optimization run**, which stops after a pre-defined number of nodes have been explored. The tree is plotted after the solve. \n",
"\n",
"*Note: Callback functions are user–defined routines to be specified to the Optimizer which are called at specific stages during the optimization process, prompting the Optimizer to return to the user's program before continuing with the solution algorithm. Check out the online documentation to learn more about [using callback functions](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/chCallbacks.html).*\n",
"\n",
"This example uses the [problem.addcbnewnode](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addcbnewnode.html) method, which declares a callback function that will be called every time a new node is created during the branch and bound search. \n",
"\n",
"\n",
"The *storeBBnode* function is defined in the code cell below to store information about each new node in the tree. This is the only operation that needs to be carried out at every node: given a node number (*newnode*), and its parent (*parent*), we store the information in the 'left' and 'right' arrays so that at the end of the B&B we have an explicit B&B tree stored in these arrays."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import networkx as nx\n",
"import xpress as xp\n",
"import time\n",
"\n",
"from matplotlib import pyplot as plt\n",
"\n",
"def storeBBnode(prob, Tree, parent, newnode, branch):\n",
" \"\"\"Store the branch-and-bound tree in a pair of dictionaries for left and right sides of branches\"\"\"\n",
" \n",
" nodes[newnode] = len(nodes) + 1 # store the nodes' labels in the order they are found\n",
"\n",
" if branch == 0: # check if left branch\n",
" left[parent] = newnode\n",
" else:\n",
" right[parent] = newnode"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now set up the B&B tree data objects and create a problem. We populate it by reading in a local matrix file. \n",
"\n",
"We then specify the node callback with [problem.addcbnewnode](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addcbnewnode.html) so that we can collect information at each new node. The first argument must be the function defined previously, while the second argumentis a data object (for example the graph *T*), which in this case is not used by the callback function.\n",
"\n",
"Furthermore, the [maxnode](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/HTML/MAXNODE.html) control defines the maximum number of nodes (10) that are explored in the B&B tree. This value is not a hard limit, particularly when exploring nodes using multiple threads. Therefore, we allow the use of only one thread via the [threads](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/HTML/THREADS.html) control, to ensure that the MAXNODE limit is fulfilled when searching the B&B tree."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"T = nx.Graph() # define a networkx graph to store the branch-and-bound tree\n",
"card_subtree = {} # to store the cardinality of the subtree rooted at each node\n",
"pos = {} # to store the position of each node in the plot\n",
"\n",
"# Define the dictionaries to store the left and right children of each node\n",
"left = {}\n",
"right = {}\n",
"nodes = {1: 1} # dictionary for labeling the nodes in the order they are found, root node indexed at 1\n",
"\n",
"start_time = time.time()\n",
"\n",
"p = xp.problem()\n",
"\n",
"p.read('sampleprob.mps.gz')\n",
"\n",
"p.addcbnewnode(storeBBnode, T)\n",
"\n",
"p.controls.maxnode = 10 # limit the number of nodes that will be explored\n",
"p.controls.threads = 1 # limit the number of threads to 1 to ensure that the maxnode limit is respected\n",
"\n",
"p.optimize()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The code cell below defines two functions: \n",
" - the function *postorder_count*, which computes the cardinality of a subtree for each node by recursively counting nodes.\n",
" - the function *setpos* that sets a position for each node in the graph depending on the cardinality of each subtree.\n",
"\n",
"\n",
"The nodes and corresponding edges are then plotted in a tree with numbered nodes in the order they were found by Xpress Optimizer, using the tree graph drawing functionality from the *network* package."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def postorder_count(node):\n",
" \"\"\"Recursively count nodes to compute the cardinality of a subtree for\n",
" each node\"\"\"\n",
"\n",
" card = 0\n",
"\n",
" if node in left.keys(): # see if node has a left key\n",
" postorder_count(left[node])\n",
" card += card_subtree[left[node]]\n",
"\n",
" if node in right.keys(): # see if node has a right key\n",
" postorder_count(right[node])\n",
" card += card_subtree[right[node]]\n",
"\n",
" card_subtree[node] = 1 + card\n",
"\n",
"def setpos(T, node, curpos, st_width, depth):\n",
"\n",
" \"\"\"\n",
" Set position depending on cardinality of each subtree\n",
" \"\"\"\n",
"\n",
" # Special condition: we are at the root\n",
" if node == 1:\n",
" T.add_node(node, pos=(0.5, 1))\n",
"\n",
" # Use a convex combination of subtree comparison and depth to assign a width to each subtree\n",
" alpha = 0.01\n",
"\n",
" if node in left.keys():\n",
"\n",
" # X position in the graph should not just depend on depth,\n",
" # otherwise we'd see a long and thin subtree and it would just\n",
" # look like a path\n",
"\n",
" leftwidth = st_width * (alpha * .7 + (1 - alpha) *\n",
" card_subtree[left[node]] /\n",
" card_subtree[node])\n",
" leftpos = curpos - (st_width - leftwidth) / 2\n",
"\n",
" T.add_node(left[node], pos=(leftpos, - depth))\n",
" T.add_edge(node, left[node])\n",
" setpos(T, left[node], leftpos, leftwidth, depth + 1)\n",
"\n",
" if node in right.keys():\n",
"\n",
" rightwidth = st_width * (alpha * .5 + (1 - alpha) *\n",
" card_subtree[right[node]] /\n",
" card_subtree[node])\n",
" rightpos = curpos + (st_width - rightwidth) / 2\n",
"\n",
" T.add_node(right[node], pos=(rightpos, - depth))\n",
" T.add_edge(node, right[node])\n",
" setpos(T, right[node], rightpos, rightwidth, depth + 1)\n",
"\n",
"\n",
"postorder_count(1) # assign card_subtree to each node\n",
"\n",
"# Determine the position of each node depending on subtree cardinalities\n",
"setpos(T, 1, 0.5, 1, 0)\n",
"\n",
"pos = nx.get_node_attributes(T, 'pos')\n",
"\n",
"nx.draw(T, pos, labels=nodes, font_color='white') # create B&B tree representation\n",
"plt.show() # display the tree"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.9"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
| |||||||||||
| © Copyright 2025 Fair Isaac Corporation. |
