# spopt.locate.LSCP

class spopt.locate.LSCP(name: str, problem: LpProblem)

  Implement the Location Set Covering Problem (LSCP) optimization model and solve it. A capacitated version, the Capacitated Location Set Covering Problem – System Optimal (CLSCP-SO), can also be solved by passing in client client demand and facility capacities.

  The standard LSCP, as adapted from [CM18], can be formulated as:

  \[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{j \in J}{Y_j} && & (1) \\ \displaystyle \textbf{Subject To} & \displaystyle \sum_{j \in N_i}{Y_j} \geq 1 && \forall i \in I & (2) \\ & Y_j \in \{0,1\} && \forall j \in J & (3) \\ & && & \\ \displaystyle \textbf{Where} && i & = & \textrm{index of demand points/areas/objects in set } I \\ && j & = & \textrm{index of potential facility sites in set } J \\ && S & = & \textrm{maximum acceptable service distance or time standard} \\ && d_{ij} & = & \textrm{shortest distance or travel time between locations } i \textrm{ and } j \\ && N_i & = & \{j | d_{ij} < S\} \\ && Y_j & = & \begin{cases} 1, \textrm{if a facility is sited at location } j \\ 0, \textrm{otherwise} \\ \end{cases} \end{array}\end{split}\]

  The CLSCP-SO, as adapted from [CM18] (see also [CS88]), can be formulated as:

  \[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{j \in J}{Y_j} && & (1) \\ \displaystyle \textbf{Subject to} & \displaystyle \sum_{j \in N_i}{z_{ij}} = 1 && \forall i \in I & (2) \\ & \displaystyle \sum_{i \in I} a_i z_{ij} \leq C_jx_j && \forall j \in J & (3) \\ & Y_j \in {0,1} && \forall j \in J & (4) \\ & z_{ij} \geq 0 && \forall i \in I \quad \forall j \in N_i & (5) \\ & && & \\ \displaystyle \textbf{Where:} && i & = & \textrm{index of demand points/areas/objects in set } I \\ && j & = & \textrm{index of potential facility sites in set } J \\ && S & = & \textrm{maximal acceptable service distance or time standard} \\ && d_{ij} & = & \textrm{shortest distance or travel time between nodes } i \textrm{ and } j \\ && N_i & = & \{j | d_{ij} < S\} \\ && a_i & = & \textrm{amount of demand at } i \\ && C_j & = & \textrm{capacity of potential facility } j \\ && z_{ij} & = & \textrm{fraction of demand } i \textrm{ that is assigned to facility } j \\ && Y_j & = & \begin{cases} 1, \text{if a facility is located at node } j \\ 0, \text{otherwise} \\ \end{cases} \end{array}\end{split}\]
  Parameters:
    name `python:str`

      The problem name.

    problem `pulp.LpProblem`

      A `pulp` instance of an optimization model that contains constraints, variables, and an objective function.

  Attributes:
    name `python:str`

      The problem name.

    problem `pulp.LpProblem`

      A `pulp` instance of an optimization model that contains constraints, variables, and an objective function.

    fac2cli `numpy.array`

      A 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated. An empty client array indicates the facility is associated with no clients.

    cli2fac `numpy.array`

      The inverse of `fac2cli` where client to facility relationships are shown.

    aij `numpy.array`

      A cost matrix in the form of a 2D array between origins and destinations.

  __init__(name: str, problem: LpProblem)

    Initialize.

    Parameters:
      name `python:str`

        The desired name for the model.

  Methods

  `__init__`(name, problem) | Initialize.
  `check_status`() | Ensure a model is solved.
  `client_facility_array`() | Create a 2D array storing client to facility relationships where each row represents a client and contains an array of facility indices with which it is associated.
  `facility_client_array`() | Create a 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated.
  `from_cost_matrix`(cost_matrix, service_radius) | Create an `LSCP` object based on a cost matrix.
  `from_geodataframe`(gdf_demand, gdf_fac, ...) | Create an `LSCP` object from `geopandas.GeoDataFrame` objects.
  `solve`(solver[, results]) | Solve the `LSCP` model.

  facility_client_array() → None

    Create a 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated. An empty client array indicates the facility is associated with no clients.

    Returns:
      `python:None`
  classmethod from_cost_matrix(cost_matrix: array, service_radius: float, predefined_facilities_arr: array = None, demand_quantity_arr: array = None, facility_capacity_arr: array = None, name: str = 'lscp')

    Create an `LSCP` object based on a cost matrix. A capacitated version of the LSCP (the CLSCP-SO) can be solved by passing in the `demand_quantity_arr` and `facility_capacity_arr` keyword arguments.

    Parameters:
      cost_matrix `numpy.array`

        A cost matrix in the form of a 2D array between origins and destinations.

      service_radius `python:float`

        Maximum acceptable service distance.

      predefined_facilities_arr `numpy.array` (default `python:None`)

        A binary 1D array of service facilities that must appear in the solution. For example, consider 3 facilites `['A', 'B', 'C']`. If facility `'B'` must be in the model solution, then the passed in array should be `[0, 1, 0]`.

      demand_quantity_arr `numpy.array` (default `python:None`)

        Amount of demand at each client location.

      facility_capacity_arr `numpy.array` (default `python:None`)

        Capacity for service at each facility location.

      name `python:str`, (default ‘lscp’)

        The name of the problem.

    Returns:
      `spopt.locate.coverage.LSCP`

    Examples

        >>> from spopt.locate import LSCP
        >>> from spopt.locate.util import simulated_geo_points
        >>> import geopandas
        >>> import numpy
        >>> import pulp
        >>> import spaghetti

    Create a regular lattice.

        >>> lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
        >>> ntw = spaghetti.Network(in_data=lattice)
        >>> streets = spaghetti.element_as_gdf(ntw, arcs=True)
        >>> streets_buffered = geopandas.GeoDataFrame(
        ...     geopandas.GeoSeries(streets["geometry"].buffer(0.2).unary_union),
        ...     crs=streets.crs,
        ...     columns=["geometry"]
        ... )

    Simulate points about the lattice.

        >>> demand_points = simulated_geo_points(streets_buffered, needed=100, seed=5)
        >>> facility_points = simulated_geo_points(streets_buffered, needed=5, seed=6)

    Snap the points to the network of lattice edges.

        >>> ntw.snapobservations(demand_points, "clients", attribute=True)
        >>> clients_snapped = spaghetti.element_as_gdf(
        ...     ntw, pp_name="clients", snapped=True
        ... )
        >>> ntw.snapobservations(facility_points, "facilities", attribute=True)
        >>> facilities_snapped = spaghetti.element_as_gdf(
        ...     ntw, pp_name="facilities", snapped=True
        ... )

    Calculate the cost matrix from origins to destinations.

        >>> cost_matrix = ntw.allneighbordistances(
        ...    sourcepattern=ntw.pointpatterns["clients"],
        ...    destpattern=ntw.pointpatterns["facilities"])

    Create and solve an `LSCP` instance from the cost matrix.

        >>> lscp_from_cost_matrix = LSCP.from_cost_matrix(
        ...     cost_matrix, service_radius=8
        ... )
        >>> lscp_from_cost_matrix = lscp_from_cost_matrix.solve(
        ...     pulp.PULP_CBC_CMD(msg=False)
        ... )

    Get the facility lookup demand coverage array.

        >>> for fac, cli in enumerate(lscp_from_cost_matrix.fac2cli):
        ...     print(f"facility {fac} serving {len(cli)} clients")
        facility 0 serving 0 clients
        facility 1 serving 63 clients
        facility 2 serving 85 clients
        facility 3 serving 0 clients
        facility 4 serving 58 clients

  classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, service_radius: float, predefined_facility_col: str = None, demand_quantity_col: str = None, facility_capacity_col: str = None, distance_metric: str = 'euclidean', name: str = 'lscp')

    Create an `LSCP` object from `geopandas.GeoDataFrame` objects. Calculate the cost matrix between demand and facility locations before building the problem within the `from_cost_matrix()` method. A capacitated version of the LSCP (the CLSCP-SO) can be solved by passing in the `demand_quantity_col` and `facility_capacity_col` keyword arguments.

    Parameters:
      gdf_demand `geopandas.GeoDataFrame`

        Demand locations.

      gdf_fac `geopandas.GeoDataFrame`

        Facility locations.

      demand_col `python:str`

        Demand sites geometry column name.

      facility_col `python:str`

        Facility candidate sites geometry column name.

      service_radius `python:float`

        Maximum acceptable service distance.

      predefined_facility_col `python:str` (default `python:None`)

        Column name representing facilities are already defined. This a binary assignment per facility. For example, consider 3 facilites `['A', 'B', 'C']`. If facility `'B'` must be in the model solution, then the column should be `[0, 1, 0]`.

      demand_quantity_col `python:str`

        Column name representing amount of demand at each client location.

      facility_capacity_arr `python:str`

        Column name representing capacity for service at each facility location.

      distance_metric `python:str` (default ‘euclidean’)

        A metric used for the distance calculations supported by scipy.spatial.distance.cdist.

      name `python:str` (default ‘lscp’)

        The name of the problem.

    Returns:
      `spopt.locate.coverage.LSCP`

    Examples

        >>> from spopt.locate import LSCP
        >>> from spopt.locate.util import simulated_geo_points
        >>> import geopandas
        >>> import numpy
        >>> import pulp
        >>> import spaghetti

    Create a regular lattice.

        >>> lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
        >>> ntw = spaghetti.Network(in_data=lattice)
        >>> streets = spaghetti.element_as_gdf(ntw, arcs=True)
        >>> streets_buffered = geopandas.GeoDataFrame(
        ...     geopandas.GeoSeries(streets["geometry"].buffer(0.2).unary_union),
        ...     crs=streets.crs,
        ...     columns=["geometry"]
        ... )

    Simulate points about the lattice.

        >>> demand_points = simulated_geo_points(streets_buffered, needed=100, seed=5)
        >>> facility_points = simulated_geo_points(streets_buffered, needed=5, seed=6)

    Snap the points to the network of lattice edges and extract as `GeoDataFrame` objects.

        >>> ntw.snapobservations(demand_points, "clients", attribute=True)
        >>> clients_snapped = spaghetti.element_as_gdf(
        ...     ntw, pp_name="clients", snapped=True
        ... )
        >>> ntw.snapobservations(facility_points, "facilities", attribute=True)
        >>> facilities_snapped = spaghetti.element_as_gdf(
        ...     ntw, pp_name="facilities", snapped=True
        ... )

    Create and solve an `LSCP` instance from the `GeoDataFrame` objects.

        >>> lscp_from_geodataframe = LSCP.from_geodataframe(
        ...     clients_snapped,
        ...     facilities_snapped,
        ...     "geometry",
        ...     "geometry",
        ...     service_radius=8,
        ...     distance_metric="euclidean"
        ... )
        >>> lscp_from_geodataframe = lscp_from_geodataframe.solve(
        ...     pulp.PULP_CBC_CMD(msg=False)
        ... )

    Get the facility lookup demand coverage array.

        >>> for fac, cli in enumerate(lscp_from_geodataframe.fac2cli):
        ...     print(f"facility {fac} serving {len(cli)} clients")
        facility 0 serving 0 clients
        facility 1 serving 0 clients
        facility 2 serving 100 clients
        facility 3 serving 0 clients
        facility 4 serving 0 clients

  solve(solver: LpSolver, results: bool = True)

    Solve the `LSCP` model.

    Parameters:
      solver `pulp.apis.LpSolver`

        A solver supported by `pulp`.

      results bool (default `python:True`)

        If `True` it will create metainfo (which facilities cover which demand) and vice-versa, and the uncovered demand.

    Returns:
      `spopt.locate.coverage.LSCP`