Uncapacitated Facility Location

UFLP · BALINSKI 1965

Logistics · Network & Facility · Strategic

The Uncapacitated Facility Location Problem asks: given candidate facility sites with fixed opening costs and assignment costs from each site to each customer, which facilities should be opened to minimise total fixed + assignment cost? No capacity constraints at the facilities — each open facility can serve arbitrary demand. Introduced as an integer program by Balinski (1965), solved by the seminal DUALOC dual-ascent algorithm of Erlenkotter (1978), and made an enduring object of approximation-algorithms research: Shmoys, Tardos & Aardal (1997) gave the first constant-factor approximation, Li (2013) the current best ratio of 1.488.

Mathematical formulation

Balinski (1965) integer program

SymbolMeaning
$I$candidate facility sites
$J$customers
$f_i$fixed opening cost at site $i$
$c_{ij}$assignment cost of customer $j$ to facility $i$
$y_i \in \{0,1\}$1 if facility $i$ is opened
$x_{ij} \in \{0,1\}$1 if customer $j$ is assigned to facility $i$
Objective: opening + assignment cost
$$\min \; \sum_{i \in I} f_i \, y_i \;+\; \sum_{i \in I} \sum_{j \in J} c_{ij} \, x_{ij}$$
(1) Each customer assigned to exactly one facility
$$\sum_{i \in I} x_{ij} = 1 \quad \forall j \in J$$
(2) Only open facilities can serve
$$x_{ij} \le y_i \quad \forall i \in I,\, j \in J$$
(3) Binary variables
$$x_{ij}, y_i \in \{0,1\}$$

Relaxation property. The LP relaxation ($x_{ij} \in [0,1]$) may have fractional solutions. The LP solution gives lower bounds that drive dual-ascent and branch-and-bound exact methods; gap is often small for natural instances.

Complexity. NP-hard even in the metric case (triangle inequality on $c_{ij}$). In the metric case, Shmoys-Tardos-Aardal (1997) gave the first constant-factor $3.16$-approximation via LP rounding; successive work drove this down to $1.488$ (Li 2013). Non-metric UFLP is as hard as set cover and cannot be approximated within $O(\log n)$ unless P = NP.

Solution methods. Erlenkotter's DUALOC (1978) is the classical fast exact method on small-medium instances. For large instances: Lagrangian relaxation on the assignment constraints (Cornuéjols-Fisher-Nemhauser 1977), Benders decomposition, commercial MIP (CPLEX/Gurobi), and LP-rounding approximation algorithms with tight analysis.

Key references

Balinski, M. L. (1965).
“Integer programming: Methods, uses, computation.”
Management Science, 12(3), 253–313. doi:10.1287/mnsc.12.3.253
Kuehn, A. A., & Hamburger, M. J. (1963).
“A heuristic program for locating warehouses.”
Management Science, 9(4), 643–666. doi:10.1287/mnsc.9.4.643
Erlenkotter, D. (1978).
“A dual-based procedure for uncapacitated facility location.”
Operations Research, 26(6), 992–1009. doi:10.1287/opre.26.6.992
Cornuéjols, G., Fisher, M. L., & Nemhauser, G. L. (1977).
“Location of bank accounts to optimize float.”
Management Science, 23(8), 789–810. doi:10.1287/mnsc.23.8.789
Shmoys, D. B., Tardos, É., & Aardal, K. (1997).
“Approximation algorithms for facility location problems.”
STOC 1997, 265–274. doi:10.1145/258533.258600
Li, S. (2013).
“A 1.488 approximation algorithm for the uncapacitated facility location problem.”
Information and Computation, 222, 45–58. doi:10.1016/j.ic.2012.01.007
Daskin, M. S. (2013).
Network and Discrete Location (2nd ed.).
Wiley. doi:10.1002/9781118537015

Where capacity isn't binding, UFLP is often the right model.
Let's scope your instance.

Get in Touch
Data and numerical examples are illustrative. Pages on this site are educational tools, not production software.