| |||||||||||
| |||||||||||
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. facility_location.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "a045a688",
"metadata": {},
"source": [
"# **Facility location problem**"
]
},
{
"cell_type": "markdown",
"id": "8302aba0",
"metadata": {},
"source": [
"***facility_location.ipynb***\n",
"\n",
"A facility location problem to select the location of parks over a set of candidate sites that are meant to serve public schools at minimum (average or maximum) distance.\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,
"id": "908cca61",
"metadata": {},
"outputs": [],
"source": [
"# Install the xpress package\n",
"%pip install -q xpress"
]
},
{
"cell_type": "markdown",
"id": "aa44a630",
"metadata": {},
"source": [
"## Problem description and formulation\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "0aa71950",
"metadata": {},
"source": [
"There are $n$ public schools in a region. The administration wants to create parks (or gyms, swimming pools, etc.) that can be used by these schools and has $m$ abandoned areas, currently unused, that could be converted for this purpose. The coordinates of both the public schools and the abandoned areas are therefore known. For budget reasons, the administration can only open $p$ parks.\n",
"\n",
"We formulate and solve the problem of choosing the $p$ parks among the abandoned areas in such a way as to minimize one of the following two objective functions:\n",
"\n",
"* the average (i.e. the sum divided by the number of schools) of the distances between each school and the closest (open) park;\n",
"* the maximum, calculated on the set of schools, of the distance between the school and the closest park.\n",
"\n",
"The **binary variables $serves_{i,j}$** indicate if school $i \\in SCHOOLS$ is served (=1) by the candidate site $j \\in SITES$ or not (=0). The **binary variables $build_j$** indicate if a certain candidate site $j$ is selected for creating a park (=1) or not (=0). \n",
"\n",
"$$\\min \\sum_{i \\in \\mathcal{I}} \\sum_{j \\in \\mathcal{J}} dist_{i,j} \\cdot serves_{i,j}$$\n",
"\n",
"Subject to:\n",
"\n",
"* Every school must be served by one park:\n",
"$$\\sum_{j \\in SITES} serves_{i,j} = 1, \\qquad \\forall i \\in SCHOOLS$$\n",
"\n",
"* Exactly $n$ parks are built:\n",
"$$\\sum_{j \\in SITES} build_{j} = p, \\qquad \\forall j \\in SITES$$\n",
"\n",
"* Only parks that are built can serve schools:\n",
"$$\\sum_{i \\in SCHOOLS} serves_{i,j} \\leq n \\cdot build_{j}, \\qquad \\forall j \\in SITES$$"
]
},
{
"cell_type": "markdown",
"id": "c4b894ed",
"metadata": {},
"source": [
"## Data preparation"
]
},
{
"cell_type": "markdown",
"id": "c2ffd5dd",
"metadata": {},
"source": [
"We start by importing the necessary modules, to then create random coordinates for school and candidate sites to calculate the distances between schools and sites. \n",
"\n",
"For a different instance, change the value of *rndseed*."
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "cff7654f",
"metadata": {},
"outputs": [],
"source": [
"import xpress as xp\n",
"import numpy as np\n",
"import networkx as nx\n",
"import matplotlib as mpl\n",
"import matplotlib.pyplot as plt\n",
"\n",
"rndseed = 10\n",
"np.random.seed(rndseed)\n",
"\n",
"num_parks = 4 # number of parks to be built\n",
"num_schools = 9 # number of schools to be served\n",
"num_sites = 11 # number of candidate sites to build parks\n",
"\n",
"SCHOOLS = range(num_schools) # set of schools\n",
"SITES = range(num_sites) # set of candidate sites\n",
"\n",
"coord_schools = 10 * np.random.random((num_schools, 2)) # x-y coordinates between 0 and 10 (in km)\n",
"coord_sites = 10 * np.random.random((num_sites, 2))\n",
"\n",
"# Create a dictionary with the distances between schools and candidate sites\n",
"dist = {(i,j): np.linalg.norm([coord_schools[i] - coord_sites[j]]) for i in SCHOOLS for j in SITES}"
]
},
{
"cell_type": "markdown",
"id": "55ee1038",
"metadata": {},
"source": [
"Now we define a function to be used for solution visualization using *matplotlib*."
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "534dd7e0",
"metadata": {},
"outputs": [],
"source": [
"def draw_sol(n, m, prob=None, x=None, y=None):\n",
" \"\"\"\n",
" Given the variables x and y and their value, display the possible locations for new facilities\n",
" selected by the model and the school-area assignment.\n",
" If x and y are not passed, it displays only the locations of schools and areas.\n",
" \"\"\"\n",
"\n",
" mpl.rcParams['figure.figsize'] = (7,7) # To plot with the right aspect ratio\n",
" \n",
" V = [i for i in range(n + m)] # Set of nodes\n",
"\n",
" # Set of edges: condition i<j implies these are EDGES, not arcs,\n",
" # and therefore they are not directed\n",
" E = []\n",
"\n",
" # If a solution is provided, use it to create the assignment graph.\n",
" if prob is not None:\n",
" xsol = prob.getSolution(x)\n",
" ysol = prob.getSolution(y)\n",
" E = [(i, n + j) for i in SCHOOLS for j in SITES if xsol[i,j] > 0.5]\n",
" print(E)\n",
"\n",
" # Create a dictionary with nodes as keys and (x,y) tuples as their values\n",
" coordS = {i: tuple(coord_schools[i]) for i in SCHOOLS}\n",
" coordA = {n + j: tuple(coord_sites[j]) for j in SITES}\n",
"\n",
" coord = {**coordS, **coordA}\n",
"\n",
" node_colS = { i: '#5555ff' for i in SCHOOLS}\n",
" node_colA1 = {n + j: '#ff5555' for j in SITES if y and ysol[j] > 0.5}\n",
" node_colA0 = {n + j: '#a0a0a0' for j in SITES if not y or ysol[j] < 0.5}\n",
" node_col = {**node_colS, **node_colA1, **node_colA0}\n",
" node_col = [node_col[i] for i in range(n+m)]\n",
"\n",
" g = nx.Graph()\n",
"\n",
" g.add_nodes_from(V)\n",
" g.add_edges_from(E)\n",
" \n",
"\n",
" # Offset the labels\n",
" offset = {node: (coord[node][0] + 0.2, coord[node][1] + 0.2) for node in g.nodes()}\n",
" nx.draw_networkx_labels(g, pos=offset)\n",
"\n",
" nx.draw_networkx(g, pos=coord, node_color=node_col, node_shape='.', with_labels=False)"
]
},
{
"cell_type": "markdown",
"id": "367faf68",
"metadata": {},
"source": [
"Plot the points for schools (blue) and sites (grey) using the previous function."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c9b5cf17",
"metadata": {},
"outputs": [],
"source": [
"# Pass None as solution to obtain just a map of all schools and of all candidate sites\n",
"draw_sol(num_schools,num_sites)\n",
"\n",
"print(\"Schools (blue) and candidate sites for parks (grey):\")\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "c54bb9db",
"metadata": {},
"source": [
"## Model implementation"
]
},
{
"cell_type": "markdown",
"id": "c97a3f3d",
"metadata": {},
"source": [
"When passing sets, lists, or range objects to [prob.addVariables()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addVariables.html), the result is a Python dictionary of variables, whose keys are tuples of indices. Variables $serves$ and $build$ are created this way.\n",
"\n",
"The objective and constraints are then created and added to the problem directly by passing the corresponding expression as a list comprehension in the code cell below."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ddf5c0a6",
"metadata": {},
"outputs": [],
"source": [
"prob = xp.problem()\n",
"\n",
"serves = prob.addVariables(SCHOOLS, SITES, vartype=xp.binary)\n",
"build = prob.addVariables(SITES, vartype=xp.binary)\n",
"\n",
"# Objective function and constraints\n",
"prob.setObjective(xp.Sum(dist[i,j] * serves[i,j] for i in SCHOOLS for j in SITES))\n",
" \n",
"# Every school must be served by one park\n",
"prob.addConstraint(xp.Sum(serves[i,j] for j in SITES) == 1 for i in SCHOOLS)\n",
" \n",
"# Exactly n parks are built:\n",
"prob.addConstraint(xp.Sum(build[j] for j in SCHOOLS) == num_parks)\n",
"\n",
"# Only parks that are built can serve schools\n",
"prob.addConstraint(xp.Sum(serves[i,j] for i in SCHOOLS) <= num_schools * build[j] for j in SITES)\n",
"\n",
"prob.optimize()\n",
"\n",
"prob.write(\"problem.lp\")\n",
"\n",
"# Draw solution: open parks and their closest schools\n",
"draw_sol(num_schools,num_sites,prob,serves,build)"
]
},
{
"cell_type": "markdown",
"id": "c74071ff",
"metadata": {},
"source": [
"To consider the **maximum distance** (as opposed to the sum of distances), we model the objective function:\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"\\max_{i \\in \\mathcal{I}} (\\sum_{j \\in \\mathcal{J}} dist_{i,j} . serves_{i,j}) \n",
"\\end{align*}\n",
"$$\n",
"\n",
"by creating an auxiliary variable $z$, and setting the objective function to ($\\min z$) and adding the constraint: \n",
"\n",
"$$\n",
"\\begin{align*}\n",
"& \\quad z \\geq \\sum_{j \\in \\mathcal{J}} dist_{i,j} . serves_{i,j}, \\qquad \\forall i \\in \\mathcal{I} \\\\\n",
"\\end{align*}\n",
"$$\n",
"\n",
"The new variable is created below, and the new constraints are added to the problem before setting a new objective with [problem.setObjective](), which replaces the old objective function when called again without the *objidx* argument. \n",
"\n",
"Run the cell below to verify if the optimal solution remains the same for the new objective."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f8bea8dc",
"metadata": {},
"outputs": [],
"source": [
"z = prob.addVariable() # add auxiliary variable to the problem\n",
"\n",
"prob.addConstraint(z >= xp.Sum(dist[i,j] * serves[i,j] for j in SITES) for i in SCHOOLS) \n",
"\n",
"prob.setObjective(z) # replaces the old objective function\n",
"\n",
"prob.optimize()\n",
"\n",
"# Draw solution: open parks and their closest schools\n",
"draw_sol(num_schools,num_sites,prob,serves,build)"
]
}
],
"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": 5
}
| |||||||||||
| © Copyright 2025 Fair Isaac Corporation. |
