Load Balancing
Maximum Flow · Min-Cut · Polynomial
Transmission congestion costs North American grids $5–$12 billion annually in inefficient generation redispatch and lost renewable curtailment. Every 15 minutes, a grid operator must route power flows from generators to load centers through a capacitated transmission network. This is the Maximum Flow problem—solvable in polynomial time by Edmonds-Karp in O(VE²)—where transmission line ratings and transformer limits determine the bottleneck capacity.
Where This Decision Fits
Energy operations chain — the highlighted step is what this page optimizes
The Problem
From power grids to graph theory
A regional power grid connects 6 generators (sources) and 8 demand districts (sinks) through 15 transmission lines, each with a MW capacity limit set by thermal ratings and transformer constraints. The objective is to find the maximum power flow from all generators to all demand centers and identify the bottleneck (minimum cut) that limits total throughput.
This maps directly to the Maximum Flow problem on a directed graph. By the Max-Flow Min-Cut Theorem (Ford & Fulkerson, 1956), the maximum achievable flow equals the capacity of the minimum s-t cut—the smallest set of lines whose removal disconnects supply from demand.
| Energy Domain | Max-Flow Model | |
|---|---|---|
| Generator | Source node | |
| Demand district | Sink node | |
| Transmission line | Edge with capacity c(u,v) | |
| Thermal rating (MW) | Edge capacity | |
| Power flow | Flow f(u,v) | |
| Congested corridor | Min-cut edge |
Mathematical Formulation
The Maximum Flow LP relaxation
Subject To capacity: 0 ≤ f(u,v) ≤ c(u,v) ∀ (u,v) ∈ E // flow cannot exceed line rating
conservation: Σ(u,v)∈E f(u,v) = Σ(v,w)∈E f(v,w) ∀ v ≠ s,t // Kirchhoff's current law
skew symmetry: f(u,v) = −f(v,u) ∀ (u,v) ∈ E
Interactive Solver
Choose a scenario, pick an algorithm, and watch the flow
Network Flow Solver
All 15 transmission lines operational. Normal demand pattern across 8 districts.
| Algorithm | Max Flow (MW) | Augmenting Paths | Min-Cut Edges | Time |
|---|---|---|---|---|
| Press Solve to run all algorithms | ||||
Solution Algorithms
Three approaches to finding maximum flow
Edmonds-Karp
The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method that uses breadth-first search (BFS) to find augmenting paths. By always selecting the shortest augmenting path, it guarantees a polynomial bound of O(VE²), making it the standard choice for moderate-size networks.
In the energy context, each BFS traversal finds a transmission path from generators to loads that still has available capacity, pushing as much power through as the bottleneck link allows.
Ford-Fulkerson
The original augmenting-path method uses depth-first search (DFS) to find paths from source to sink with residual capacity. While simple, its worst-case complexity depends on the max-flow value |f*|, which can make it non-polynomial for irrational capacities.
For integer-capacity transmission networks (MW ratings are always integers), Ford-Fulkerson terminates in at most |f*| iterations, each augmenting flow by at least 1 MW.
Push-Relabel
Unlike augmenting-path methods, Push-Relabel maintains a preflow (flow that may exceed conservation at intermediate nodes) and uses local push and relabel operations to achieve feasibility. The highest-label variant achieves O(V²√E) in practice.
For dense transmission networks with many parallel paths, Push-Relabel often outperforms BFS-based methods due to its local operation model and better cache behavior.
Complexity Comparison
- Edmonds-Karp: O(VE²) — polynomial, BFS guarantees shortest augmenting paths
- Ford-Fulkerson: O(E × |f*|) — pseudo-polynomial, DFS may explore long paths
- Push-Relabel: O(V²E) — polynomial, best for dense graphs with high connectivity
- Max-Flow Min-Cut Theorem: the maximum flow from s to t equals the minimum cut capacity separating s and t (Ford & Fulkerson, 1956)
- Practical note: real grid solvers use DC power flow approximations and PTDF matrices rather than pure graph algorithms, but the combinatorial structure is identical
References
Key literature on network flow and power systems