| |||||||||||
| |||||||||||
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. firestation_scipy.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# **Using a SciPy sparse matrix to model the fire station problem**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***firestation_scipy.ipynb***\n",
"\n",
"In this example, we solve the fire station location problem using a SciPy sparse matrix with the [xpress.Dot()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/xpress.Dot.html) operator.\n",
"\n",
"*A version of FICO® Xpress >=9.5 is required for being able to use SciPy matrices in the xp.Dot() operator.*\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": [
"## Problem description and formulation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The fire station problem attemps to minimize the number of fire stations to build amongst a set of towns, with each town being a candidate for hosting a fire station. Each town must be served by a fire station built on a town with a travel time no longer than a pre-defined threshold (e.g. 15 minutes).\n",
"\n",
"The travel times between six towns can be described as:\n",
"\n",
"| | Town 0 | Town 1 | Town 2 | Town 3 | Town 4 | Town 5 |\n",
"|---|---|---|---|---|---|---|\n",
"| **Town 0** | 0 | 15 | 25 | 35 | 35 | 25 |\n",
"| **Town 1** | 15 | 0 | 30 | 40 | 25 | 15 |\n",
"| **Town 2** | 25 | 30 | 0 | 20 | 30 | 25 |\n",
"| **Town 3** | 35 | 40 | 20 | 0 | 20 | 30 |\n",
"| **Town 4** | 35 | 25 | 35 | 20 | 0 | 19 |\n",
"| **Town 5** | 25 | 15 | 25 | 30 | 19 | 0 |\n",
"\n",
"Therefore, a binary matrix indicating whether each town can serve another considering a travel time threshold of 15 minutes would result in the following:\n",
"\n",
"| | Town 0 | Town 1 | Town 2 | Town 3 | Town 4 | Town 5 |\n",
"|---|---|---|---|---|---|---|\n",
"| **Town 0** | 1 | 1 | 0 | 0 | 0 | 0 |\n",
"| **Town 1** | 1 | 1 | 0 | 0 | 0 | 1 |\n",
"| **Town 2** | 0 | 0 | 1 | 0 | 0 | 0 |\n",
"| **Town 3** | 0 | 0 | 0 | 1 | 0 | 0 |\n",
"| **Town 4** | 0 | 0 | 0 | 0 | 1 | 0 |\n",
"| **Town 5** | 0 | 1 | 0 | 0 | 0 | 1 |\n",
"\n",
"\n",
"Based on this data, we can define a mathematical formulation for the problem as follows:\n",
"\n",
"Let $build_{i} \\in \\{0,1\\}, \\forall i \\in \\mathcal{T}$ represent the **decision of whether to select town $i \\in \\mathcal{T}$ for building a fire station**, and $avail_{i,j} \\in \\{0,1\\}, \\forall i,j \\in \\mathcal{T}$ a **given binary matrix representing whether town $i$ can serve town $j$** within the predefined travel time limit. The problem can be therefore formulated as follows:\n",
"$$\n",
"\\min \\sum_{i \\in \\mathcal{T}} build_{i}\n",
"$$\n",
"\n",
"subject to:\n",
"\n",
"* Each town $j$ must be served by at least one eligible fire station: \n",
"$$\n",
"\\sum_{i \\in \\mathcal{T}} avail_{i,j} \\cdot build_{i} \\geq 1, \\quad \\forall j \\in \\mathcal{T} \\\\\n",
"x_{i} \\in \\{0,1\\}, \\forall i \\in \\mathcal{T}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Data preparation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In such problem, the $A$ matrix can potentially be a large sparse matrix, in case e.g. most towns can only serve a few others or none at all. \n",
"\n",
"SciPy has a module [scipy.sparse](https://docs.scipy.org/doc/scipy/reference/sparse.html) for handling 2D sparse data in a compact format, which allows representing 2D arrays by using the row/column indices of the non-zero values only. Sparse array formats allow building models more efficiently by avoiding iterating over all the elements (including the zeros) of a conventional array.\n",
"\n",
"**The [xp.Dot()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/xpress.Dot.html) operator supports the most common SciPy sparse matrix formats (CSR and CSC)**, allowing to compute the product of a 1-D NumPy array of variables or expressions with a sparse matrix of\n",
"numbers.\n",
"\n",
"In the code cell below, an instance with $T$ = 6 towns is created and the travel times between towns is given as a NumPy array. Then, a time limit of 15 minutes is defined to compute the $A$ matrix of binary values named as <tt>avail</tt>. The 2D array is then converted into a SciPy sparse matrix format (using the method <tt>csr_array</tt>) before printing both matrices for visuzalization in the output log."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import xpress as xp\n",
"import numpy as np\n",
"import scipy\n",
"import time\n",
"\n",
"num_towns = 6 # Number of towns\n",
"\n",
"t_time = np.array([[ 0.,15.,25.,35.,35.,25.], # Travel times between towns\n",
" [15., 0.,30.,40.,25.,15.],\n",
" [25.,30., 0.,20.,30.,25.],\n",
" [35.,40.,20., 0.,20.,30.],\n",
" [35.,25.,35.,20., 0.,19.],\n",
" [25.,15.,25.,30.,19., 0.]])\n",
"\n",
"avail = (t_time <= 15).astype(int) # NumPy array of binary values which are equal to 1 when t_time <= 15, otherwise 0\n",
"\n",
"avail_sparse = scipy.sparse.csr_array(avail) # Convert to SciPy sparse matrix format\n",
"\n",
"print(\"NumPy format: \", avail, sep=\"\\n\")\n",
"print(\"SciPy format: \", avail_sparse, sep=\"\\n\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Model implementation and results"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The optimization problem is constructed in the code cell below, starting with the creation of a problem instance before adding the set of binary variables $x$. By using [p.addVariables](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addVariables.html) with an integer argument, a NumPy array of variables is created.\n",
"\n",
"Then, the [xp.Dot()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/xpress.Dot.html) operator is used for applying the <tt>dot</tt> product between matrix $A$ and the array of variables $x$. The result is a set of $|T|$ constraints created with a right-hand side equal of \"1\", which is broadcasted to all constraints.\n",
"\n",
"After setting the objetive to minimize the number of towns selected to build a fire station, the problem is optimized, exported in LP format, and the final solution and objective value are printed."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = xp.problem() # Create Xpress problem\n",
"\n",
"x = p.addVariables(num_towns, vartype=xp.binary) # Creates NumPy array of variables when integers are passed\n",
"\n",
"# Serve all tows, amongst those eligible to be selected for each\n",
"p.addConstraint(xp.Dot(avail_sparse,x) >= 1) # Creates T constraints with RHS = 1\n",
"\n",
"p.setObjective(xp.Sum(x)) # Minimize number of towns selected for a fire station\n",
"\n",
"p.optimize()\n",
"\n",
"p.write(\"prob.lp\")\n",
"\n",
"print(\"Minimum number of stations: \", round(p.attributes.objval))\n",
"print(\"Located at towns\",[s+1 for s in range(num_towns) if p.getSolution(x[s]) >= 0.99])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Comparison between using NumPy and SciPy arrays in the *xp.Dot()* operator for a large scale instance\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this part, we use the *randint* method of the *random* NumPy module to generate travel times randomly between 0 and 100 minutes for each pair of $T$ towns (uniform distribution, matrix not symmetrical). The number of towns (T) can be modified by the user to scale the size of the instance up or down.\n",
"\n",
"A threshold is then applied to define the density of the matrix. A value of 1 will correspond to (approximately) a matrix density of 1%, the percentage of non-zeros in the matrix.\n",
"\n",
"The matrix is then printed in both NumPy and SciPy formats, such as in the previous part."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"num_towns = 10000 # Number of towns\n",
"\n",
"rndseed = 10\n",
"np.random.seed(rndseed)\n",
"\n",
"t_time = np.random.randint(0, 100, (num_towns, num_towns))\n",
"\n",
"avail = np.array((t_time <= 1).astype(int)) # NumPy array of binary values which are equal to 1 when t_time <= 1, otherwise 0\n",
"\n",
"avail_sparse = scipy.sparse.csr_array(avail) # Convert to SciPy sparse matrix format CSR\n",
"\n",
"print(avail)\n",
"print(avail_sparse)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lastly, the *time* package is used to record the time needed to build the set of 10000 constraints using NumPy arrays versus using SciPy sparse arrays when applying the *xp.Dot()* product.\n",
"\n",
"Although using NumPy arrays with the *xp.Dot()* operator already allows building constraints much more efficiently than using conventional Python lists (by performing loop operations in lower level C and thus introducing a much lower overhead), we can see that further gains in modelling performance can be achieved by using SciPy arrays for matrices that are highly sparse. \n",
" \n",
"By changing the threshold value in the previous code cell and running both code cells again, one can verify that the lower the density of the original matrix, the more gains are achieved when using SciPy versus using NumPy arrays with regards to model building time. "
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Time with NumPy coefs matrix: 1.415 secs.\n",
"Time with SciPy sparse matrix: 0.703 secs.\n"
]
}
],
"source": [
"p = xp.problem() # Create Xpress problem\n",
"\n",
"x = p.addVariables(num_towns, vartype=xp.binary) # Creates NumPy array of variables when integers are passed\n",
"\n",
"# Constraints created with a NumPy matrix\n",
"start = time.time() # records start time\n",
"p.addConstraint(xp.Dot(avail,x) >= 1) # Creates T constraints with RHS = 1\n",
"stop = time.time() # record time\n",
"print(f\"Time with NumPy coefs matrix: {(stop-start):.03f} secs.\")\n",
"\n",
"# Constraints created with a SciPy sparse matrix\n",
"p.addConstraint(xp.Dot(avail_sparse,x) >= 1) # Creates T constraints with RHS = 1\n",
"end = time.time() # record end time\n",
"print(f\"Time with SciPy sparse matrix: {(end-stop):.03f} secs.\")"
]
}
],
"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. |
