# Fire station location example using SciPy sparse arrays for efficiency.
#
# The fire station location 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 defined threshold (e.g. 15 minutes).
# In this example, we solve the location problem using a SciPy sparse
# matrix with the xpress.Dot() operator for efficiency.
#
# (C) 1983-2025 Fair Isaac Corporation

import xpress as xp
import numpy as np
import scipy

num_towns = 6     # Number of towns.

t_time = np.array([[ 0, 15, 25, 35, 35, 25],     # Travel times between towns.
                   [15,  0, 30, 40, 25, 15],
                   [25, 30,  0, 20, 30, 25],
                   [35, 40, 20,  0, 20, 30],
                   [35, 25, 35, 20,  0, 19],
                   [25, 15, 25, 30, 19,  0]])

avail = (t_time <= 15).astype(int)                # NumPy array of binary values equal to 1 if t_time <= 15.

avail_sparse = scipy.sparse.csr_array(avail)      # Convert to SciPy sparse matrix format.

# Print travel times in both formats for comparison.
print("NumPy format: ", avail, sep="\n")
print("SciPy format: ", avail_sparse, sep="\n")

p = xp.problem()      # Create Xpress problem.

x = p.addVariables(num_towns, vartype=xp.binary)  # Create NumPy array of variables.

# Serve all towns, amongst those eligible to be selected for each.
p.addConstraint(xp.Dot(avail_sparse,x) >= 1)      # Creates set of constraints with RHS = 1.

p.setObjective(xp.Sum(x))                         # Minimize number of towns selected for a fire station.

p.optimize()

# Print solution.
print("Number of stations: ", round(p.attributes.objval))
xsol = p.getSolution(x)
print("Located at towns",[s+1 for s in range(num_towns) if xsol[s] >= 0.99])