Problem Family
Location & Network
Foundational graph theory and discrete optimization problems spanning facility siting, network flow, shortest paths, and optimal assignment. These problems form the backbone of logistics, telecommunications, and infrastructure planning.
View Source on GitHubProblem Overview
Seven classical problems in location theory, graph algorithms, and combinatorial optimization
Quick Navigation
Facility Location UFLP
The Uncapacitated Facility Location Problem selects a subset of candidate facility sites to open and assigns each customer to an open facility. The objective minimizes the sum of fixed facility opening costs and variable customer-to-facility assignment costs. NP-hard in general; best known approximation ratio for metric UFLP is 1.488 (Li, 2013).
s.t. Σi∈F xij = 1 // each customer assigned to exactly one facility
xij ≤ yi // assign only to open facilities
yi ∈ {0, 1}, xij ≥ 0
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Greedy Add | Heuristic | O(m^2 * n) | Kuehn & Hamburger (1963). Iteratively open the facility yielding the largest cost reduction. |
| Greedy Drop | Heuristic | O(m^2 * n) | Start with all facilities open; iteratively close the least impactful one. |
| Simulated Annealing | O(iter * m * n) | Toggle/swap moves with Boltzmann acceptance criterion. |
Try It Yourself — Facility Location demo
| Algorithm | Total Cost | Facilities Open | Time |
|---|
p-Median Problem PMP
The p-Median Problem opens exactly p facilities from m candidates to minimize the total weighted distance from each customer to its nearest open facility. Unlike UFLP, there are no fixed opening costs -- the number of facilities is fixed by the parameter p. NP-hard for general p (Kariv & Hakimi, 1979).
s.t. Σi∈F xij = 1 ∀ j ∈ C // each customer assigned
xij ≤ yi ∀ i,j // only assign to open facilities
Σi∈F yi = p // open exactly p facilities
yi ∈ {0, 1}, xij ≥ 0
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Greedy | Heuristic | O(p * m * n) | Maranzana (1964). Iteratively add the facility that reduces total cost the most until p are open. |
| Teitz-Bart Interchange | Heuristic | O(iter * p * (m-p) * n) | Teitz & Bart (1968). Swap open/closed facilities if objective improves; repeat until no improvement. |
Shortest Path SPP
The Shortest Path Problem finds the minimum-weight path from a source vertex s to a target vertex t in a directed weighted graph. Two classical algorithms are implemented: Dijkstra's algorithm for graphs with non-negative weights, and Bellman-Ford for graphs that may contain negative weights (with negative cycle detection).
s.t. Σj xij - Σj xji = 1 if i = s
Σj xij - Σj xji = -1 if i = t
Σj xij - Σj xji = 0 otherwise // flow conservation
xij ≥ 0
// Dijkstra: requires wij ≥ 0 — returns incorrect paths if negative edges exist
// Bellman-Ford: handles negative weights; detects negative cycles via V-th pass
// A*: uses admissible heuristic h(v) to guide search toward t
Dijkstra's algorithm uses a priority queue (binary heap) to greedily select the nearest unvisited vertex. Correctness requires non-negative edge weights. Bellman-Ford relaxes all edges V-1 times; a V-th pass detecting further improvement indicates a negative-weight cycle.
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Dijkstra’s Algorithm | Exact | O((V+E) log V) | Dijkstra (1959). Binary heap; non-negative weights only. Incorrect results if negative edges exist. |
| Bellman-Ford | Exact | O(V * E) | Bellman (1958); Ford (1956). Handles negative weights; detects negative cycles via V-th relaxation pass. |
| Floyd-Warshall | Exact | O(V³) | Floyd (1962); Warshall (1962). All-pairs shortest paths via dynamic programming. Handles negative weights (no negative cycles). |
| A* Search | Exact | O(E) best case | Hart, Nilsson & Raphael (1968). Informed search with admissible heuristic h(v). Optimal with consistent h; widely used in game AI and navigation. |
Try It Yourself
| Algorithm | Distance | Path | Time |
|---|---|---|---|
| No results yet | |||
Need to Solve Larger Instances?
This demo handles up to 15 nodes for educational purposes. For real-world networks, custom solutions, or research collaboration:
Maximum Flow Max-Flow
The Maximum Flow Problem finds the maximum amount of flow that can be sent from a source vertex s to a sink vertex t through a capacitated directed network, respecting edge capacity constraints and flow conservation at all intermediate nodes. By the Max-Flow Min-Cut Theorem, the maximum flow value equals the minimum s-t cut capacity.
s.t. 0 ≤ fij ≤ cij ∀ (i,j) ∈ E // capacity constraints
Σi:(i,v)∈E fiv = Σj:(v,j)∈E fvj ∀ v ≠ s,t // flow conservation
In any network, the maximum value of a flow from s to t equals the minimum capacity of an s-t cut. An s-t cut (S, T) partitions V into S (containing s) and T (containing t); its capacity is Σ(i,j): i∈S, j∈T cij.
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Edmonds-Karp | Exact | O(V * E²) | Edmonds & Karp (1972). BFS augmenting paths (Ford-Fulkerson with BFS). Includes min-cut extraction. |
| Dinic’s Algorithm | Exact | O(V² * E) | Dinic (1970). Blocking flows on layered residual graph. Faster than Edmonds-Karp on dense networks. |
| Push-Relabel | Exact | O(V² * E) / O(V³) | Goldberg & Tarjan (1988). Preflow-push with relabeling. Practical state-of-the-art for dense networks; O(V³) with highest-label selection. |
Try It Yourself — Max Flow demo
| Algorithm | Max Flow | Min Cut | Aug. Paths | Time |
|---|
Minimum Spanning Tree MST
The Minimum Spanning Tree problem finds a subset of edges that connects all vertices in an undirected weighted graph with minimum total edge weight, using exactly n-1 edges. Unlike most problems in this family, MST is solvable in polynomial time via greedy algorithms. Both Kruskal's and Prim's algorithms are implemented.
s.t. T ⊆ E is a spanning tree of G = (V, E) // n-1 edges, connected, acyclic
|T| = |V| - 1
T connects all vertices in V
For any cut of the graph, the minimum-weight edge crossing the cut belongs to some MST. This property guarantees the correctness of both Kruskal's (globally sorted edges) and Prim's (locally grown tree) greedy strategies.
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Kruskal's Algorithm | Exact | O(E log E) | Kruskal (1956). Sort edges by weight; greedily add edges that do not form a cycle (union-find). |
| Prim’s Algorithm | Exact | O(E log V) | Prim (1957); Jarník (1930). Grow tree from arbitrary vertex; add cheapest crossing edge (binary heap). |
Try It Yourself — MST demo
| Algorithm | MST Weight | Edges | Time |
|---|
Linear Assignment LAP
The Linear Assignment Problem finds a minimum-cost one-to-one matching between n agents and n tasks, given an n×n cost matrix. Unlike most combinatorial optimization problems, LAP is solvable in polynomial time -- the Hungarian method (Kuhn, 1955; Munkres, 1957) achieves optimality in O(n³) via a primal-dual approach on the bipartite assignment polytope.
s.t. Σj=1n xij = 1 ∀ i // each agent assigned exactly once
Σi=1n xij = 1 ∀ j // each task assigned exactly once
xij ∈ {0, 1}
The constraint matrix of the assignment problem is totally unimodular, so the LP relaxation always yields an integer solution. This means the problem is equivalent to a linear program and can be solved in polynomial time, despite being formulated as an integer program.
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Hungarian (Kuhn-Munkres) | Exact | O(n^3) | Kuhn (1955); Munkres (1957). Shortest augmenting path variant (O(n³) refinement). Primal-dual with complementary slackness. |
| Greedy Min-Cost | Heuristic | O(n²) | Assign the cheapest available (agent, task) pair iteratively. Fast but no optimality guarantee. |
Try It Yourself
Generate or load a cost matrix, then click Solve.
| Algorithm | Total Cost | Assignment | Time |
|---|
Minimum Cost Flow MCF
The Minimum Cost Flow problem is the grand unifier of network optimization: shortest path, maximum flow, and linear assignment are all special cases. Given a directed graph with edge capacities uij, costs cij, and node supply/demand bi, find the cheapest feasible flow. Solvable in polynomial time via network simplex, successive shortest paths, or cost-scaling algorithms.
s.t. Σj fij - Σj fji = bi ∀ i ∈ V // flow balance (bi > 0: supply, < 0: demand)
0 ≤ fij ≤ uij ∀ (i,j) ∈ E // capacity bounds
Shortest Path: single source-sink pair, unit flow, bs=1, bt=−1, uij=∞.
Max Flow: zero costs except a large negative cost on a return arc (t→s).
Assignment: bipartite graph, unit supplies/demands, unit capacities.
Transportation: bipartite supply-demand with general bi and uij=∞.
| Algorithm | Type | Complexity | Description |
|---|---|---|---|
| Network Simplex | Exact | O(V² E log V) worst | Dantzig (1951); Orlin (1997). Specialization of LP simplex to network structure. Fastest in practice for most instances. |
| Successive Shortest Paths | Exact | O(V E + V² log V) · U | Busacker & Gowen (1961). Send flow along cheapest augmenting path; uses Dijkstra with reduced costs (Johnson potentials). |
| Cost Scaling | Exact | O(V² E log(VC)) | Goldberg & Tarjan (1990). Strongly polynomial when combined with ε-scaling. Theoretical best for dense networks. |
Complexity Landscape
What makes this family unique: polynomial and NP-hard problems side by side
Shortest Path (Dijkstra O((V+E) log V)), Max Flow (Dinic O(V²E)), MST (Kruskal O(E log E)), and Assignment (Hungarian O(n³)) are all solvable in polynomial time. These are the algorithmic workhorses of network optimization.
Facility Location and p-Median are NP-hard in general. They require heuristics or metaheuristics for large instances. The metric UFLP admits a 1.488-approximation (Li, 2013); p-Median is polynomial on trees but NP-hard on general networks (Kariv & Hakimi, 1979).
Dijkstra vs Bellman-Ford: Dijkstra for non-negative weights (faster); Bellman-Ford when negative edges exist or cycle detection is needed.
Kruskal vs Prim: Kruskal for sparse graphs (edge-sorted); Prim for dense graphs (adjacency-based, heap-driven).
Location problems: Greedy heuristics for fast approximations; SA/metaheuristics for better solutions; exact MIP for small instances.
Related Problems
Extensions and variants that build on the core problems
Capacitated Facility Location
Each facility has a maximum capacity. Combines facility opening decisions with capacity allocation. Significantly harder than UFLP.
Minimum Cost Flow
The grand unifier: shortest path, max flow, and assignment are all special cases. Send flow at minimum cost subject to capacity and supply/demand constraints.
All-Pairs Shortest Path
Floyd-Warshall computes distances between all vertex pairs in O(V³). Essential for dense distance matrices in location and routing problems.
Steiner Tree
Connect a subset of required vertices at minimum cost, possibly using non-required vertices. NP-hard generalization of MST.
Generalized Assignment
Assign tasks to agents with varying capacities and costs. NP-hard extension of LAP where agents have resource constraints.
Multicommodity Flow
Route multiple commodities through a shared network with shared edge capacities. Core model in telecommunications and logistics.
Standard benchmarks: OR-Library (Beasley, 1990) for UFLP and p-Median; DIMACS challenge sets for shortest path and max flow; standard graph generators for MST and assignment.
References
Shortest Path & Network Flow
Dijkstra, E. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1.
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1).
Floyd, R. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6).
Ford, L. & Fulkerson, D. (1956). Maximal flow through a network. Canadian J. Math, 8.
Edmonds, J. & Karp, R. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. JACM, 19(2).
Dinic, E. (1970). Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Doklady, 11.
Ahuja, R., Magnanti, T. & Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
MST & Assignment
Kruskal, J. (1956). On the shortest spanning subtree of a graph. Proceedings of the AMS, 7(1).
Prim, R. (1957). Shortest connection networks and some generalizations. Bell System Technical J., 36(6).
Kuhn, H. (1955). The Hungarian method for the assignment problem. Naval Research Logistics, 2(1-2).
Munkres, J. (1957). Algorithms for the assignment and transportation problems. JSIAM, 5(1).
Facility Location & p-Median
Li, S. (2013). A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222.
Kariv, O. & Hakimi, S. (1979). An algorithmic approach to network location problems. SIAM J. Applied Math, 37(3).
Teitz, M. & Bart, P. (1968). Heuristic methods for estimating the generalized vertex median. Operations Research, 16(5).
Beasley, J. (1990). OR-Library: distributing test problems by electronic mail. JORS, 41(11).
Algorithm Summary
All 19 algorithms across the Location & Network family
| Problem | Algorithm | Type | Complexity |
|---|---|---|---|
| Facility Location | Greedy Add | Heuristic | O(m² · n) |
| Greedy Drop | Heuristic | O(m² · n) | |
| Simulated Annealing | O(iter · m · n) | ||
| p-Median | Greedy | Heuristic | O(p · m · n) |
| Teitz-Bart | Heuristic | O(iter · p · (m-p) · n) | |
| Shortest Path | Dijkstra | Exact | O((V+E) log V) |
| Bellman-Ford | Exact | O(V · E) | |
| Floyd-Warshall | Exact | O(V³) | |
| A* Search | Exact | O(E) best case | |
| Maximum Flow | Edmonds-Karp | Exact | O(V · E²) |
| Dinic’s | Exact | O(V² · E) | |
| Push-Relabel | Exact | O(V³) | |
| Min. Spanning Tree | Kruskal | Exact | O(E log E) |
| Prim | Exact | O(E log V) | |
| Assignment | Hungarian | Exact | O(n³) |
| Greedy Min-Cost | Heuristic | O(n²) | |
| Min-Cost Flow | Network Simplex | Exact | O(V²E log V) |
| Successive SP | Exact | O((VE + V² log V) · U) | |
| Cost Scaling | Exact | O(V²E log(VC)) |