Skip to content

Uncapacitated Facility Location (UFL) API Reference

Data

Data model for UncapacitatedFacilityLocation use case.

UflpData

Bases: UcData

Data for the Uncapacitated Facility Location Problem (UFLP).

Given a set of potential facility locations and a set of customers, each facility has a fixed opening cost and there is a transportation cost for serving each customer from each facility. The goal is to select which facilities to open and assign each customer to exactly one open facility, minimizing the total cost (opening + transportation).

Attributes:

  • name (Literal['uncapacitated_facility_location_problem']) –

    Identifier for this data type.

  • facility_costs (list[float]) –

    Fixed cost to open each facility. Length equals the number of potential facility locations.

  • transport_costs (list[list[float]]) –

    Transportation cost matrix of shape (n_customers, n_facilities). transport_costs[i][j] is the cost of serving customer i from facility j.

  • facility_names (list[str]) –

    Names for each facility. Defaults to F0, F1, etc.

  • customer_names (list[str]) –

    Names for each customer. Defaults to C0, C1, etc.

  • facility_positions ((dict[str, tuple[float, float]] | None, optional)) –

    Optional (x, y) coordinates for each facility, keyed by facility name. Used for visualisation.

  • customer_positions ((dict[str, tuple[float, float]] | None, optional)) –

    Optional (x, y) coordinates for each customer, keyed by customer name. Used for visualisation.

Examples:

Create a small instance with 3 facilities and 4 customers:

>>> data = UflpData(
...     facility_costs=[100.0, 150.0, 120.0],
...     transport_costs=[
...         [10.0, 20.0, 15.0],
...         [25.0, 10.0, 30.0],
...         [15.0, 25.0, 10.0],
...         [20.0, 15.0, 25.0],
...     ],
... )

n_facilities: int property

Return the number of potential facility locations.

n_customers: int property

Return the number of customers.

plot(*, ax: Axes | None = None) -> Axes

Plot the UFLP instance as a bipartite graph.

When explicit positions are provided, facilities and customers are plotted with their actual position. If no position is proivded, facilities are drawn on the left and customers on the right.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the UFLP data.

Returns:

  • str –

    String representation of the data.

from_cost_matrix(facility_costs: list[float] | NDArray[np.float64], transport_costs: list[list[float]] | NDArray[np.float64], facility_positions: dict[str, tuple[float, float]] | None = None, facility_names: list[str] | None = None, customer_positions: dict[str, tuple[float, float]] | None = None, customer_names: list[str] | None = None) -> UflpData staticmethod

Create data from explicit cost arrays.

Parameters:

  • facility_costs (list[float] | ndarray) –

    Fixed opening cost for each facility.

  • transport_costs (list[list[float]] | ndarray) –

    Transport cost matrix of shape (n_customers, n_facilities).

  • facility_positions (dict[str, tuple[float, float]] | None, default: None ) –

    Optional facility coordinates for visualisation.

  • facility_names (list[str], default: None ) –

    Names for each facility. Defaults to F0, F1, etc.

  • customer_positions (dict[str, tuple[float, float]] | None, default: None ) –

    Optional customer coordinates for visualisation.

  • customer_names (list[str], default: None ) –

    Names for each customer. Defaults to C0, C1, etc.

Returns:

Examples:

>>> data = UflpData.from_cost_matrix(
...     facility_costs=[100.0, 200.0],
...     transport_costs=[[10.0, 20.0], [30.0, 5.0]],
... )

generate_random(n_facilities: int = 5, n_customers: int = 10, facility_cost_range: tuple[float, float] = (50.0, 200.0), transport_cost_range: tuple[float, float] = (1.0, 50.0), seed: int | None = None) -> UflpData staticmethod

Generate a random UFLP instance.

Facility and customer positions are randomly placed in the unit square and transport costs are derived from Euclidean distances scaled into transport_cost_range.

Parameters:

  • n_facilities (int, default: 5 ) –

    Number of potential facility locations, by default 5.

  • n_customers (int, default: 10 ) –

    Number of customers, by default 10.

  • facility_cost_range (tuple[float, float], default: (50.0, 200.0) ) –

    Range for random facility opening costs, by default (50.0, 200.0).

  • transport_cost_range (tuple[float, float], default: (1.0, 50.0) ) –

    Range for random transportation costs, by default (1.0, 50.0).

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

  • UflpData –

    A randomly generated UFLP instance.

Examples:

>>> data = UflpData.generate_random(
...     n_facilities=5,
...     n_customers=10,
...     seed=42,
... )

Formulation

Formulation for UncapacitatedFacilityLocation use case.

UflpFormulation

Bases: UcFormulation[UflpData, UflpSolution]

Constraint-based formulation for the Uncapacitated Facility Location Problem.

Mathematical Formulation

Given: - m potential facility locations with opening costs f_j - n customers with transport costs c_ij from customer i to facility j

Decision Variables: y_j ∈ {0,1} for each facility j ∈ {0, ..., m-1} y_j = 1 if facility j is opened, 0 otherwise x_ij ∈ {0,1} for each customer i and facility j x_ij = 1 if customer i is assigned to facility j

Objective: minimize Σ_j f_j · y_j + Σ_i Σ_j c_ij · x_ij

Constraints: 1. Each customer assigned to exactly one facility: Σ_j x_ij = 1 for all i 2. Customers can only be assigned to open facilities: x_ij ≤ y_j for all i, j

References
  • Wikipedia: https://en.wikipedia.org/wiki/Facility_location_problem

to_string(data: UflpData) -> str staticmethod

Return a string describing the formulation.

Parameters:

Returns:

  • str –

    String representation of the formulation.

formulate(data: UflpData) -> Model staticmethod

Formulate the UFLP using a constraint-based approach.

Parameters:

Returns:

  • Model –

    A Luna Model ready to be solved.

Raises:

interpret(solution: Solution, data: UflpData) -> UflpSolution staticmethod

Extract the UFLP solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution containing variable assignments.

  • data (UflpData) –

    The original problem data.

Returns:

  • UflpSolution –

    Structured solution with cost breakdown and validity.

Raises:

Solution

Solution model for UncapacitatedFacilityLocation use case.

UflpSolution

Bases: UcSolution

Solution for the Uncapacitated Facility Location Problem (UFLP).

Attributes:

  • name (Literal['uncapacitated_facility_location_problem']) –

    Identifier for this solution type.

  • open_facilities (list[str]) –

    Names of the facilities that are opened.

  • assignments (dict[str, str]) –

    Mapping from customer name to the facility name it is assigned to.

  • total_cost (float) –

    Total cost (facility opening costs + transportation costs).

  • facility_cost (float) –

    Sum of opening costs of all opened facilities.

  • transport_cost (float) –

    Sum of transportation costs for all customer assignments.

  • is_valid (bool) –

    Whether the solution is valid (every customer assigned to an open facility).

plot(data: UflpData | None = None, *, ax: Axes | None = None) -> Axes

Plot the UFLP solution as a bipartite graph.

Open facilities are highlighted, closed facilities are greyed out. Assignment edges are drawn in colour; unused edges are omitted for clarity.

Parameters:

  • data (UflpData | None, default: None ) –

    Problem data. Required for layout and labels.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Return a string describing the solution.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for UncapacitatedFacilityLocation use case.

UflpInstance

Bases: UcInstance[UflpData, UflpFormulation, UflpSolution]

Instance combining data and formulation for UncapacitatedFacilityLocation.

Collection

Collection of UncapacitatedFacilityLocation instances.

UflpCollection

Bases: UcInstanceCollection[UflpInstance]

Collection of Uncapacitated Facility Location Problem instances.

Provides factory methods to generate benchmark instances with various cost structures for testing and evaluation.

from_random(min_num_facilities: int, max_num_facilities: int, num_instances: int = 1, *, customer_ratio: float = 2.0, seed: int | None = None) -> UflpCollection classmethod

Generate random UFLP instances.

Parameters:

  • min_num_facilities (int) –

    Minimum number of facilities per instance.

  • max_num_facilities (int) –

    Maximum number of facilities per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • customer_ratio (float, default: 2.0 ) –

    Ratio of customers to facilities, by default 2.0.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = UflpCollection.from_random(
...     min_num_facilities=3,
...     max_num_facilities=6,
...     num_instances=2,
...     seed=42,
... )

from_clustered(min_num_facilities: int, max_num_facilities: int, num_instances: int = 1, *, customer_ratio: float = 2.0, cluster_std: float = 0.1, seed: int | None = None) -> UflpCollection classmethod

Generate clustered UFLP instances.

Customers are clustered around facility locations, producing instances where the optimal solution tends to open nearby facilities.

Parameters:

  • min_num_facilities (int) –

    Minimum number of facilities per instance.

  • max_num_facilities (int) –

    Maximum number of facilities per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • customer_ratio (float, default: 2.0 ) –

    Ratio of customers to facilities, by default 2.0.

  • cluster_std (float, default: 0.1 ) –

    Standard deviation of customer clusters around facilities, by default 0.1.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = UflpCollection.from_clustered(
...     min_num_facilities=3,
...     max_num_facilities=6,
...     cluster_std=0.15,
...     seed=42,
... )

from_uniform(min_num_facilities: int, max_num_facilities: int, num_instances: int = 1, *, customer_ratio: float = 2.0, facility_cost: float = 100.0, seed: int | None = None) -> UflpCollection classmethod

Generate UFLP instances with uniform facility costs.

All facilities have the same opening cost so the optimal solution depends purely on transport cost structure.

Parameters:

  • min_num_facilities (int) –

    Minimum number of facilities per instance.

  • max_num_facilities (int) –

    Maximum number of facilities per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • customer_ratio (float, default: 2.0 ) –

    Ratio of customers to facilities, by default 2.0.

  • facility_cost (float, default: 100.0 ) –

    Fixed opening cost for every facility, by default 100.0.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = UflpCollection.from_uniform(
...     min_num_facilities=3,
...     max_num_facilities=6,
...     facility_cost=150.0,
...     seed=42,
... )