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 Type Description
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:

Name Type Description Default
ax Axes | None

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

 None

Returns:

Type Description
Axes

The axes with the plot.

to_string() -> str

Return a string describing the UFLP data.

Returns:

Type Description
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:

Name Type Description Default
facility_costs list[float] | ndarray

Fixed opening cost for each facility.

 required
transport_costs list[list[float]] | ndarray

Transport cost matrix of shape (n_customers, n_facilities).

 required
facility_positions dict[str, tuple[float, float]] | None

Optional facility coordinates for visualisation.

 None
facility_names list[str]

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

 None
customer_positions dict[str, tuple[float, float]] | None

Optional customer coordinates for visualisation.

 None
customer_names list[str]

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

 None

Returns:

Type Description
UflpData

The data instance.

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:

Name Type Description Default
n_facilities int

Number of potential facility locations, by default 5.

 5
n_customers int

Number of customers, by default 10.

 10
facility_cost_range tuple[float, float]

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

 (50.0, 200.0)
transport_cost_range tuple[float, float]

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

 (1.0, 50.0)
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
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:

Name Type Description Default
data UflpData

The problem data.

 required

Returns:

Type Description
str

String representation of the formulation.

formulate(data: UflpData) -> Model staticmethod

Formulate the UFLP using a constraint-based approach.

Parameters:

Name Type Description Default
data UflpData

The problem data.

 required

Returns:

Type Description
Model

A Luna Model ready to be solved.

Raises:

Type Description
EmptyDataError

If facility costs or transport costs are empty.

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

Extract the UFLP solution from the solver result.

Parameters:

Name Type Description Default
solution Solution

The solver solution containing variable assignments.

 required
data UflpData

The original problem data.

 required

Returns:

Type Description
UflpSolution

Structured solution with cost breakdown and validity.

Raises:

Type Description
NoSolutionFoundError

If the solver did not find a solution.

Solution

Solution model for UncapacitatedFacilityLocation use case.

UflpSolution

Bases: UcSolution

Solution for the Uncapacitated Facility Location Problem (UFLP).

Attributes:

Name Type Description
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:

Name Type Description Default
data UflpData | None

Problem data. Required for layout and labels.

 None
ax Axes | None

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

 None

Returns:

Type Description
Axes

The axes with the plot.

Raises:

Type Description
ValueError

If data is None.

to_string() -> str

Return a string describing the solution.

Returns:

Type Description
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:

Name Type Description Default
min_num_facilities int

Minimum number of facilities per instance.

 required
max_num_facilities int

Maximum number of facilities per instance.

 required
num_instances int

Number of instances per size, by default 1.

 1
customer_ratio float

Ratio of customers to facilities, by default 2.0.

 2.0
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
UflpCollection

Collection containing generated instances.

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:

Name Type Description Default
min_num_facilities int

Minimum number of facilities per instance.

 required
max_num_facilities int

Maximum number of facilities per instance.

 required
num_instances int

Number of instances per size, by default 1.

 1
customer_ratio float

Ratio of customers to facilities, by default 2.0.

 2.0
cluster_std float

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

 0.1
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
UflpCollection

Collection containing clustered instances.

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:

Name Type Description Default
min_num_facilities int

Minimum number of facilities per instance.

 required
max_num_facilities int

Maximum number of facilities per instance.

 required
num_instances int

Number of instances per size, by default 1.

 1
customer_ratio float

Ratio of customers to facilities, by default 2.0.

 2.0
facility_cost float

Fixed opening cost for every facility, by default 100.0.

 100.0
seed int | None

Random seed for reproducibility, by default None.

 None

Returns:

Type Description
UflpCollection

Collection containing uniform-cost instances.

Examples:

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