Family 5 · OR Problem Family
Location & Covering
Problems of selecting candidate sites to open or activate, to optimally serve demand points according to criteria of coverage, distance, or cost.
Uncapacitated Facility Location
Given m potential facility sites with opening costs fi and n customers with assignment costs cij, select which facilities to open and assign each customer to an open facility to minimize total fixed plus assignment cost. Also known as the Simple Plant Location Problem (SPLP) in the European literature, this is a fundamental model for discrete location theory appearing in network design, service facility siting, server placement, and distribution logistics. The best polynomial-time approximation ratio is 1.488, close to the inapproximability threshold of 1.463 established by Guha & Khuller (1998).
s.t. ∑i=1..m xij = 1 ∀ j (each customer assigned to exactly one facility)
xij ≤ yi ∀ i, j (assign only to open facilities)
yi ∈ {0, 1}, xij ∈ {0, 1}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Add | Heuristic | O(m² · n) | Iterative facility opening |
| Greedy Drop | Heuristic | O(m² · n) | Iterative facility closing |
| Local Search (LS) | Varies | Add/drop/swap, best-improvement | |
| Simulated Annealing | Varies | Toggle/swap, Boltzmann acceptance | |
| Tabu Search | Varies | Sun (2006), aspiration criterion | |
| Iterated Greedy | Varies | Destroy-repair with acceptance | |
| Genetic Algorithm | Varies | Binary encoding, uniform crossover | |
| VNS | Varies | Mladenovic & Hansen (1997) |
p-Median Problem
Open exactly p facilities from m candidates to minimize total weighted distance from n demand points to their nearest open facility. Unlike the UFLP, there are no fixed opening costs — the constraint is on the number of facilities. Introduced by Hakimi (1964) for optimal switching center placement, the p-Median is a cornerstone of discrete location theory with applications in public facility siting, emergency service placement, and distribution network design. NP-hard for general p (Kariv & Hakimi, 1979).
s.t. ∑i=1..m xij = 1 ∀ j (each customer assigned)
xij ≤ yi ∀ i, j (assign to open facilities)
∑i=1..m yi = p (exactly p facilities)
yi ∈ {0, 1}, xij ∈ {0, 1}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy | Heuristic | O(p · m · n) | Iterative cost-reducing facility opening |
| Teitz-Bart Interchange | Heuristic | O(p · (m−p) · n) | Teitz & Bart (1968) |
| Local Search | Varies | Swap open/closed facility | |
| Simulated Annealing | Varies | Swap with Boltzmann acceptance | |
| Tabu Search | Varies | Facility swap with tabu memory | |
| Iterated Greedy | Varies | Close facilities + greedy reopen | |
| Genetic Algorithm | Varies | Binary/subset encoding | |
| VNS | Varies | 1-swap → 2-swap → block-swap |
Hub Location Problem
Given n nodes with inter-node flows Wij and distances Dij, select p hub nodes and assign each non-hub to a hub (single allocation). Flows between origin-destination pairs are routed through hubs, with inter-hub transportation receiving a discount factor α < 1 reflecting economies of scale from consolidation. Applications include airline hub-and-spoke networks, postal sorting centers, telecommunications backbone design, and freight distribution systems.
s.t. h(i) ∈ H ∀ i (each node assigned to a hub)
|H| = p (exactly p hubs selected)
α ∈ (0, 1) (inter-hub discount factor)
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Enumeration | Exact | O(C(n,p) · n²) | All p-subsets; feasible for small n |
| Greedy Hub Selection | Heuristic | O(n² · p) | Greedily open cost-minimizing hubs |
| Simulated Annealing | Varies | Hub swap with Boltzmann acceptance |
Maximum Coverage Problem
Given a universe U of n elements and a collection of m subsets, select at most k subsets to maximize the number of covered elements. The coverage function is monotone and submodular, which guarantees the greedy algorithm achieves a (1 − 1/e) ≈ 0.632 approximation ratio — the best possible for any polynomial-time algorithm under standard complexity assumptions (Feige, 1998). Maximum coverage is the dual perspective of set cover: instead of minimizing cost to cover everything, it maximizes coverage under a budget constraint. Applications include facility placement, sensor deployment, advertising reach, and influence maximization in social networks.
s.t. |T| ≤ k (budget constraint on selected subsets)
T ⊆ {1, …, m}
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Coverage | Heuristic | O(k · m · n) | Nemhauser, Wolsey & Fisher (1978) |
| LP Relaxation + Rounding | Heuristic | O(LP) | Round variables exceeding threshold |
| Local Search | O(k · m · n) per swap | Swap selected/unselected subsets |
Set Covering Problem
Given a universe U = {1, …, m} and a collection of n subsets Sj with costs cj, select a minimum-cost sub-collection such that every element in U is covered by at least one selected subset. The greedy algorithm that repeatedly selects the subset with the lowest cost per newly covered element achieves an H(m) = ln(m) + 1 approximation ratio — the best possible unless P = NP (Feige, 1998). Set covering is one of Karp's 21 NP-complete problems and arises in crew scheduling, facility placement, logical test design, and wireless base station deployment.
s.t. ∑j: i ∈ Sj xj ≥ 1 ∀ i ∈ U (every element covered)
xj ∈ {0, 1} ∀ j
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| ILP (HiGHS) | Exact | Exponential | MILP via scipy.optimize.milp |
| Greedy Set Cover | Heuristic | O(m · n) | Chvatal (1979), ln(m)+1 approx |
| LP Relaxation + Rounding | Heuristic | O(LP) | Round above 1/f threshold |
| Lagrangian Relaxation | Heuristic | O(n · T) | Beasley (1990), subgradient optimization |
Maximum Weight Set Packing
Given a universe U, a collection of m subsets Si with weights wi, select a sub-collection of pairwise disjoint subsets to maximize total weight. Set packing is the dual of set cover: cover seeks the cheapest way to cover all elements, while packing seeks the heaviest collection of non-overlapping sets. On the conflict graph (where nodes are subsets and edges connect intersecting subsets), set packing is equivalent to the Maximum Weight Independent Set (MWIS) problem. Applications include scheduling non-conflicting meetings, assigning non-overlapping frequency bands, and organ donor-recipient matching.
s.t. xi + xj ≤ 1 ∀ i, j where Si ∩ Sj ≠ ∅ (pairwise disjoint)
xi ∈ {0, 1} ∀ i
| Algorithm | Type | Complexity | Reference |
|---|---|---|---|
| Greedy Set Packing | Heuristic | O(m log m + m · |U|) | Hurkens & Schrijver (1989), 1/k-approx |
| ILP Formulation | Exact | Exponential | Binary IP with conflict constraints |
| Local Search | Varies | Swap/add/drop on selected subsets |
Key References
- Hakimi, S.L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459.
- Teitz, M.B. & Bart, P. (1968). Heuristic methods for estimating the generalized vertex median of a weighted graph. Operations Research, 16(5), 955–961.
- Cornuejols, G. et al. (1977). Location of bank accounts to optimize float. Management Science, 23(8), 789–810.
- Nemhauser, G.L., Wolsey, L.A. & Fisher, M.L. (1978). An analysis of approximations for maximizing submodular set functions. Math. Programming, 14(1), 265–294.
- Chvatal, V. (1979). A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3), 233–235.
- Kariv, O. & Hakimi, S.L. (1979). An algorithmic approach to network location problems. SIAM J. Applied Math., 37(3), 539–560.
- O'Kelly, M.E. (1987). A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res., 32(3), 393–404.
- Hurkens, C.A.J. & Schrijver, A. (1989). On the size of systems of sets every t of which have an SDR. SIAM J. Discrete Math., 2(1), 68–72.
- Beasley, J.E. (1990). OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc., 41(11), 1069–1072.
- Campbell, J.F. (1994). Integer programming formulations of discrete hub location problems. Eur. J. Oper. Res., 72(2), 387–405.
- Shmoys, D.B., Tardos, E. & Aardal, K. (1997). Approximation algorithms for facility location problems. Proc. 29th ACM STOC, 265–274.
- Feige, U. (1998). A threshold of ln n for approximating set cover. J. ACM, 45(4), 634–652.
- Jain, K. & Vazirani, V.V. (2001). Approximation algorithms for metric facility location and k-median problems. J. ACM, 48(2), 274–296.
- Reese, J. (2006). Solution methods for the p-median problem: An annotated bibliography. Networks, 48(3), 125–142.
- Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222, 45–58.
- Daskin, M.S. (2013). Network and Discrete Location: Models, Algorithms, and Applications, 2nd ed. Wiley.