Network Flow Optimization
Push as much flow as possible, or the cheapest flow, through a capacitated network. Network flow models optimize movement through a system of nodes and capacitated arcs, solving maximum-flow and minimum-cost flow problems that underlie logistics, telecom and many other systems.
Solve Network Flow →What is Network Flow Optimization?
Network flow optimization concerns moving flow, of goods, traffic, data, or fluid, through a network of nodes connected by arcs, each arc having a capacity and sometimes a cost. The goal is to route flow optimally while respecting the capacities and the conservation of flow at each node (what enters a node must leave it, except at the source and sink).
Two problems are central. The maximum-flow problem finds the greatest total flow that can be pushed from a source node to a sink node given the arc capacities, revealing the network's throughput limit. The minimum-cost flow problem finds the cheapest way to send a required amount of flow from source to sink when each arc also has a cost per unit.
These models are foundational because many logistics and infrastructure problems reduce to them. The famous max-flow min-cut theorem states that the maximum flow equals the capacity of the smallest cut separating source from sink, which identifies the bottleneck. The transportation and assignment problems are themselves special cases of network flow.
In plain terms: Picture a network of pipes with capacity limits. Max-flow asks: how much can I push through from start to end? Min-cost flow asks: what's the cheapest way to send a given amount? These models underlie logistics, traffic, data networks, and even the transportation and assignment problems.
The Core Problems
Maximum Flow
The greatest total flow that can move from source to sink given arc capacities, revealing the network's throughput limit.
Minimum-Cost Flow
The cheapest way to send a required flow from source to sink when arcs carry a per-unit cost as well as a capacity.
Max-Flow Min-Cut
The maximum flow equals the capacity of the smallest cut separating source and sink, which pinpoints the bottleneck.
Key Formulas
Understanding the Solution
For maximum flow, the solution gives the flow on each arc and the total throughput, and the minimum cut identifies exactly which arcs form the bottleneck, the arcs to expand if you want more throughput. For minimum-cost flow, it gives the cheapest routing of the required amount.
Because so many problems map onto network flow, recognizing that a problem is a flow problem is often the key insight: it unlocks efficient, well-understood algorithms rather than a bespoke or brute-force approach. The transportation, assignment and shortest-path problems are all network-flow special cases.
Assumptions & Validation
Defined Network
The nodes, arcs, capacities and (for min-cost) costs are known.
If violated: Map the network structure and arc parameters.
Flow Conservation
Flow is conserved at every intermediate node.
If violated: Ensure the model captures all inflows and outflows.
Capacity Limits
Arc capacities are known and respected.
If violated: Provide realistic capacities for each arc.
⚠️ Check assumptions first
Network-flow models assume flow is conserved at each node and bounded by arc capacities, with known costs for min-cost flow. The main practical skill is recognizing when a real problem is actually a flow problem, since many logistics, matching and routing problems reduce to network flow and can then be solved efficiently. Modeling a flow problem as something more complex, or missing a capacity or conservation condition, leads to wrong or intractable formulations.
When NOT to Use Network Flow
Sequencing Visits
To order visits to many stops, use the traveling salesman or vehicle routing problem.
General Optimization
For problems without a natural flow structure, use general linear or integer programming.
Stochastic Systems
For random arrivals and service, use queuing or simulation models.
Industry Applications
Logistics Throughput
Find the maximum throughput of a distribution or transport network and its bottleneck.
Telecom & Data
Route data or calls through a capacitated network at maximum flow or minimum cost.
Supply Networks
Optimize flow of goods through a multi-stage capacitated supply network.
Project & Scheduling Models
Solve matching, scheduling and routing problems that reduce to network flow.
Frequently Asked Questions
What is a network flow problem?
A network flow problem involves moving flow, such as goods, traffic or data, through a network of nodes connected by arcs, each arc having a capacity and sometimes a cost. The aim is to route flow optimally while respecting arc capacities and conserving flow at each node. The two central versions are the maximum-flow problem and the minimum-cost flow problem, which underlie many logistics and infrastructure applications.
What is the maximum-flow problem?
The maximum-flow problem finds the greatest total flow that can be pushed from a designated source node to a designated sink node, given the capacities of the arcs. It reveals the throughput limit of the network. The solution specifies the flow on each arc and the total achievable flow, and it identifies the bottleneck that constrains further throughput through the minimum cut.
What is the max-flow min-cut theorem?
The max-flow min-cut theorem states that the maximum flow from source to sink equals the capacity of the minimum cut, the smallest total capacity of arcs whose removal disconnects the source from the sink. This elegant result means finding the maximum flow simultaneously identifies the network's bottleneck, the set of arcs that limit throughput and would need to be expanded to allow more flow.
What is minimum-cost flow?
The minimum-cost flow problem finds the cheapest way to send a required amount of flow from source to sink when each arc has both a capacity and a per-unit cost. Unlike maximum flow, which maximizes throughput, minimum-cost flow meets a specified flow requirement at the lowest total cost. It generalizes the transportation and shortest-path problems and is widely used in logistics and distribution planning.
How do the transportation and assignment problems relate to network flow?
Both are special cases of network flow. The transportation problem is a minimum-cost flow problem between supply and demand nodes, and the assignment problem is a further special case with unit supplies and demands. Recognizing this connection means these problems can be solved with efficient network-flow algorithms, and it places them within a unified framework alongside shortest-path and maximum-flow problems.
Why is recognizing a network-flow structure useful?
Many real problems in logistics, matching, scheduling and routing turn out to be network-flow problems in disguise. Recognizing this structure is valuable because network-flow problems have efficient, well-understood algorithms, so identifying the structure lets you solve the problem quickly and reliably rather than resorting to a bespoke or brute-force method. This modeling insight is often the key to a tractable solution.
Optimize Flow Through a Network
Solve maximum-flow and minimum-cost flow problems and find bottlenecks. Free during Beta.
Solve Network Flow →