Network flow models

Network flow models: formulate, analyze, and optimize flows on directed graphs for max-flow/min-cut and minimum-cost flow, with variants like lower bounds, node capacities, and transshipment.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Network flow models let you size, schedule, and cost flows in logistics, production, utilities, and data networks with mathematical certainty. They turn messy routing decisions (what goes where, how much, at what cost) into solvable graph problems that scale and have provable guarantees.

Key ideas

  • A network flow problem is built on a directed graph G = (V, E).
    • A node (vertex) is a junction: a plant, warehouse, workstation, router, or time-stage.
    • An arc (edge) is a directed connection with a maximum capacity. Arc direction fixes the sign of flow.
  • A capacity u_ij on arc (i, j) limits how much can pass: 0 ≤ x_ij ≤ u_ij.
  • A source has net supply; a sink has net demand. All other nodes are transshipment nodes.
  • A feasible flow assigns x_ij to each arc so that:
    1. 0 ≤ x_ij ≤ u_ij for all arcs (i, j), and
    2. flow conservation holds at every node i: sum of outflows − sum of inflows = b_i, where b_i > 0 is supply, b_i < 0 is demand, b_i = 0 is transshipment. Sign convention: outflow positive.
  • The value of an s–t flow is the net outflow from source s (equal to net inflow at sink t) when all other nodes conserve flow.
  • A cut (S, T) partitions V into S and T = V \ S with s ∈ S and t ∈ T. The capacity of the cut is the sum of capacities of arcs from S to T.
  • A residual network G(x) shows remaining capacity to push more flow or to cancel flow:
    • For each original arc (i, j): residual forward arc (i, j) with capacity r_ij^+ = u_ij − x_ij; residual backward arc (j, i) with capacity r_ij^− = x_ij (if no lower bounds). If lower bounds l_ij exist, backward residual capacity is x_ij − l_ij.
    • For minimum-cost flow (MCF), residual arc costs are: forward residual arc cost = c_ij; backward residual arc cost = −c_ij.
  • An augmenting path is any path from source to sink in the residual network with positive residual capacities; pushing the minimum residual along that path strictly increases the flow value.

Max-flow model and results

  • Problem: Maximize the s–t flow subject to capacity and conservation constraints.
  • Assumptions: single commodity; deterministic capacities; static (no time variation); arcs directed.
  • Ford–Fulkerson method: repeatedly find augmenting paths in the residual network and push as much as possible. With arbitrary path choice and irrational capacities, it may not terminate; with integer capacities and any path rule, it terminates.
  • Edmonds–Karp algorithm: choose the shortest augmenting path in terms of arc count (BFS on residual network). It runs in O(V·E^2) time.
  • Max-flow min-cut theorem (exact statement): In any network with a single source s and sink t, the maximum value of an s–t flow equals the minimum capacity over all s–t cuts.
    • Proof idea outline (exam level): (i) Weak duality: flow value ≤ cut capacity (by summing constraints). (ii) Ford–Fulkerson finishes with no s–t augmenting path; the set of nodes reachable from s in the residual network forms a cut whose capacity equals the current flow value, proving optimality and equality. Equivalent LP duality proof: the dual of max-flow LP is min-cut.
  • Integrality property: If all capacities are integers, there exists an optimal maximum flow where every arc flow is an integer.
  • Variants:
    • Multiple sources/sinks: introduce a super-source connected to each source i with capacity equal to its supply, and a super-sink connected from each sink j with capacity equal to its demand.
    • Node capacities: split node i into i_in → i_out with arc capacity equal to node capacity; redirect incoming arcs to i_in and outgoing from i_out.
    • Undirected edges: replace by two opposite arcs each with that capacity. For max-flow/min-cut this preserves optimal values; simultaneous opposite-direction flows are not beneficial at optimum.

Minimum-cost flow (MCF) model and results

  • Problem: Minimize total cost of sending flow subject to capacity and balance:
    • Each arc (i, j) has unit cost c_ij (₹/unit; currency is not an SI unit but is standard in costing).
    • Node balances b_i sum to zero, with b_i > 0 supply, b_i < 0 demand.
    • Objective minimize Σ c_ij x_ij, subject to 0 ≤ x_ij ≤ u_ij and Σ_j x_ij − Σ_k x_ki = b_i for all i.
  • Assumptions: single commodity; linear costs; deterministic capacities and costs; static.
  • Optimality conditions (equivalent forms):
    • Negative-cycle optimality: A feasible flow is optimal iff the residual network contains no negative-cost directed cycle (using residual costs: forward c_ij, backward −c_ij).
    • Potentials and reduced costs: There exist node potentials π_i such that all residual arcs (p, q) have nonnegative reduced cost c̄_pq = c_pq + π_p − π_q ≥ 0. Complementary slackness ties zero reduced cost residual arcs to possible augmentations.
  • Algorithms:
    • Successive shortest path (SSP): repeatedly send flow from supply to demand along a shortest path by reduced costs (use potentials to keep reduced costs nonnegative so Dijkstra applies when arcs have nonnegative reduced costs). Complexity is polynomial for integer data.
    • Cycle canceling: while there exists a negative-cost cycle in the residual network, push as much as allowed around it; terminates for integer data but may be slower.
  • Integrality property: With integer supplies/demands and capacities, there exists an optimal integer flow.
  • Lower bounds on arcs: Each arc may have l_ij ≤ x_ij ≤ u_ij. Remove lower bounds by:
    • Replace capacity with u′_ij = u_ij − l_ij.
    • Adjust node balances: b′_i = b_i − Σ_out l_ij + Σ_in l_ji.
    • Keep the base cost term Σ l_ij c_ij to add to the transformed problem’s cost, or simply compute the final objective directly from reconstructed original flows.
  • Transshipment networks: All b_i = 0 except sources and sinks. Transportation and assignment are special cases handled elsewhere; both fit MCF structure.

Shortest path and matching as flows

  • Shortest path: A single-pair s–t shortest path (nonnegative arc lengths) is equivalent to a 1-unit min-cost flow from s to t; single-source SSSP is typically solved directly by graph algorithms (e.g., Dijkstra). The SSP link clarifies reduced costs/potentials.
  • Maximum bipartite matching can be solved as a max-flow by directing edges from left to right with capacity 1, plus super-source and super-sink.

Feasibility of circulation with demands

  • A circulation has b_i = 0 for all i (no external supply/demand). With lower/upper bounds, a feasible circulation exists iff for every cut (S, T) the sum of lower bounds from S to T is ≤ the sum of upper bounds from T to S, i.e., l(S, T) ≤ u(T, S) for all S ⊂ V (Hoffman circulation theorem). Practically, reduce to a feasible flow test by adding a super-source/super-sink and checking max-flow equals total required.

Sensitivity and interpretation

  • If you increase the capacity of an arc not present in any minimum cut, the max flow value stays unchanged; only arcs that appear in some minimum cut can be binding.
  • If you increase capacities on a particular minimum cut by increments {Δ_e} on its arcs e ∈ cut(S, T), the max flow can increase by at most Σ_e Δ_e. In particular, if a cut has m arcs and each is increased by Δ, the increase is at most m·Δ.
  • In MCF, node potentials (dual variables) act like marginal node prices; reduced cost c̄_ij reflects marginal penalty to use arc (i, j). Zero reduced cost residual arcs are candidates for alternative optimal flows.

Where real systems differ from the ideal

  • Capacities and demands are time-varying and uncertain (see Forecasting, Queuing models, and Production Planning and Control). Costs can be nonlinear (quantity discounts, startup/shutdown costs). Congestion and waiting are not captured unless you couple with Queuing Theory. Multi-commodity interactions (shared resources among products) break single-commodity integrality.

Formulas

0 ≤ x_ij ≤ u_ij

  • x_ij: flow on arc (i, j), unit s⁻¹ (units per second). u_ij: capacity on (i, j), s⁻¹. Applies to all capacity-constrained arcs.

Σ_j x_ij − Σ_k x_ki = b_i

  • At node i: sum over outgoing arcs minus sum over incoming equals node balance b_i. b_i in s⁻¹; positive supply, negative demand; Σ_i b_i = 0 for feasibility. Applies in all flow models.

value(x) = Σ_j x_sj − Σ_k x_ks

  • Net outflow from source s equals the flow value, s⁻¹. Applies to max-flow.

cap(S, T) = Σ_{i∈S, j∈T} u_ij

  • Capacity of s–t cut (S, T), s⁻¹. Applies to cuts in max-flow/min-cut.

r_ij^+ = u_ij − x_ij, r_ij^- = x_ij

  • Forward and backward residual capacities without lower bounds, s⁻¹. Applies to residual network construction.

Δ = min_{(p, q)∈P} r_pq

  • Augmentation along residual path P in Ford–Fulkerson: push Δ, s⁻¹. Applies when an augmenting path exists.

c̄_ij = c_ij + π_i − π_j

  • Reduced cost on residual arc (i, j). For MCF residual arcs, c_ij is the residual arc cost: forward = original c_ij, backward = −c_ij. π_i, π_j are node potentials in the same units as c (₹·unit⁻¹). Applies in MCF optimality checks.

min Σ c_ij x_ij

  • Objective for minimum-cost flow. Sum over all arcs. Units ₹·s⁻¹. Subject to capacity and balance constraints.

l_ij ≤ x_ij ≤ u_ij

  • Lower and upper bounds on arc flows, s⁻¹. Applies when minimum throughflow is required.

u′_ij = u_ij − l_ij, b′_i = b_i − Σ_out l_ij + Σ_in l_ji

  • Lower-bound elimination transform. Units s⁻¹. Applies before solving with standard solvers.

no negative-cost cycle in residual network ⇔ optimal (MCF)

  • Optimality condition for MCF. Dimensionless logical condition. Applies to feasible flows.

O(V·E^2)

  • Time complexity of Edmonds–Karp. V = number of nodes, E = number of arcs. Applies to algorithm analysis (dimensionless).

Worked examples

Example 1: Direct max-flow/min-cut Given:

  • Nodes: s, a, b, t. Arcs with capacities (s⁻¹): s→a: 10; s→b: 5; a→b: 15; a→t: 10; b→t: 10. All other arcs absent. Assume single-commodity, integer capacities, static.

Goal: Find maximum s–t flow value and one flow achieving it; identify a minimum cut.

Steps:

  1. Initialize x_ij = 0. Residual capacities r_ij = u_ij.
  2. Find augmenting path P1 = s→a→t.
    • Formula: Δ = min(r_sa, r_at)
    • Numbers: Δ = min(10, 10) s⁻¹ = 10 s⁻¹.
    • Update: x_sa = 10, x_at = 10. Residuals: r_sa = 0, r_at = 0; add back-edges a→s, t→a with r = 10.
  3. Find augmenting path P2 = s→b→t.
    • Formula: Δ = min(r_sb, r_bt)
    • Numbers: Δ = min(5, 10) s⁻¹ = 5 s⁻¹.
    • Update: x_sb = 5, x_bt = 5. Residuals: r_sb = 0, r_bt = 5; add back-edges b→s with r = 5, t→b with r = 5.
  4. Check for more s–t paths in residual network. From s, r_sa = 0 and r_sb = 0, so no path exists.
  5. Flow value:
    • Formula: value(x) = Σ_j x_sj
    • Numbers: value = x_sa + x_sb = 10 + 5 = 15 s⁻¹. Answer: Maximum flow value is 15 s⁻¹.
  6. Minimum cut: Reachable set S in residual network from s is {s}. Then T = {a, b, t}.
    • Formula: cap(S, T) = Σ_{i∈S, j∈T} u_ij
    • Numbers: cap({s}, {a, b, t}) = u_sa + u_sb = 10 + 5 = 15 s⁻¹.
    • Since cut capacity equals flow value, this cut is minimum by max-flow min-cut theorem.

Final answer: Maximum s–t flow = 15 s⁻¹. One optimal flow is x_sa = 10, x_sb = 5, x_at = 10, x_bt = 5. A minimum cut is ({s}, {a, b, t}) with capacity 15 s⁻¹. Final: 15 s⁻¹.

Example 2: Minimum-cost flow with a lower bound Given (single commodity, static):

  • Nodes: A (supply +10 s⁻¹), C (0), D (demand −10 s⁻¹). Transshipment node B (0).
  • Arcs (capacity s⁻¹, cost ₹/unit):
    • A→B: u = 6, c = 2
    • A→C: l = 2 (lower bound), u = 8, c = 4
    • B→D: u = 6, c = 3
    • C→D: u = 8, c = 1
  • All other arcs absent. Goal: Minimize total cost (₹·s⁻¹) of sending 10 s⁻¹ from A to D.

Steps:

  1. Eliminate the lower bound on A→C.
    • Formula: u′_ij = u_ij − l_ij, b′_i = b_i − Σ_out l_ij + Σ_in l_ji
    • Numbers: For A→C, u′ = 8 − 2 = 6 s⁻¹. Balances: b′_A = 10 − 2 = 8 s⁻¹; b′_C = 0 + 2 = +2 s⁻¹; b′_B = 0; b′_D = −10 s⁻¹.
    • Note: The base lower-bound cost term is 2 × 4 = 8 ₹·s⁻¹. You can add this to the transformed problem’s cost at the end, or equivalently compute the final cost directly from reconstructed original flows.
  2. Solve the transformed MCF (no lower bounds) on arcs A→B (6,2), A→C (6,4), B→D (6,3), C→D (8,1) with supplies b′.
  3. Use successive shortest path logic (costs nonnegative so Dijkstra applies on reduced costs; with zero initial potentials π = 0, reduced costs equal original costs).
    • From C (supply 2) to D: shortest path is C→D with cost 1; capacity min(2, 8) = 2 s⁻¹.
      • Send 2 s⁻¹. Cost contribution: 2 × 1 = 2 ₹·s⁻¹. Update: b′_C = 0, b′_D = −8.
    • From A (supply 8) to D: two equal-cost paths of length 5: A→B→D (2 + 3) and A→C→D (4 + 1).
      • First, send along A→B→D up to min(8, 6, 6) = 6 s⁻¹.
        • Cost contribution: 6 × 5 = 30 ₹·s⁻¹. Update: b′_A = 2, b′_D = −2.
      • Remaining 2 s⁻¹ from A: send along A→C��D with capacity min(2, 6, 6) = 2 s⁻¹.
        • Cost contribution: 2 × 5 = 10 ₹·s⁻¹. Update satisfied b′ balances.
  4. Collect flows in transformed problem:
    • x_A→B = 6 s⁻¹, x_B→D = 6 s⁻¹, x_A→C (extra) = 2 s⁻¹, x_C→D = 2 (from C’s supply) + 2 (from A via C) = 4 s⁻¹.
  5. Reconstruct original flows with lower bound on A→C:
    • Original x_A→C = lower bound 2 + extra 2 = 4 s⁻¹.
  6. Compute total cost.
    • Formula: total cost = Σ c_ij x_ij
    • Numbers:
      • A→B: 6 × 2 = 12 ₹·s⁻¹
      • B→D: 6 × 3 = 18 ₹·s⁻¹
      • A→C: 4 × 4 = 16 ₹·s⁻¹
      • C→D: 4 × 1 = 4 ₹·s⁻¹
      • Sum = 12 + 18 + 16 + 4 = 50 ₹·s⁻¹ (equivalently, transformed-flow cost 42 plus base 8).

Final answer: Minimum cost = 50 ₹·s⁻¹ with flows x_A→B = 6 s⁻¹, x_B→D = 6 s⁻¹, x_A→C = 4 s⁻¹, x_C→D = 4 s⁻¹. All node balances satisfied.

Common mistakes

  • Forgetting conservation sign convention: writing Σ inflow − Σ outflow = b_i instead of Σ outflow − Σ inflow = b_i; be consistent across all nodes.
  • Not adding a super-source/super-sink for multi-source/sink conversions, causing infeasible or miscounted flows.
  • Ignoring backward residual arcs when updating after augmentation; without them, you miss cancellation and fail to find optimality.
  • Treating cut capacity as including arcs from T to S; only arcs from S to T count in cap(S, T).
  • In min-cost with lower bounds, forgetting to: (i) shift balances, and (ii) include the base lower-bound cost in the objective (or compute directly from reconstructed flows).
  • Mixing units: reporting flow in “units/hour” in one place and “units/s” in another; stick to s⁻¹ here. Currency (₹) is non-SI but standard for cost—state it explicitly.
  • Assuming uniqueness: maximum flow value may be unique while the arc flows are not; minimum cut may also be non-unique.
  • Overlooking node capacities; must apply node-splitting before solving.
  • Using Dijkstra on negative-cost residual arcs without potentials; must use Bellman–Ford or maintain potentials so reduced costs are nonnegative.

For GATE ME

  • Concept checks: definitions (feasible flow, residual network, cut), and the exact statement of the max-flow min-cut theorem.
  • Short numericals: compute one or two Ford–Fulkerson augmentations, identify a minimum cut from a final residual graph, or read off the flow value.
  • Conversions: multi-source/sink via super nodes; node capacities via node-splitting; undirected edges to directed pair; lower bounds to standard form by balance shifting.
  • Min-cost flow: 4–6 node problems requiring 1–3 shortest path sends; verify optimality via absence of negative cycles or via nonnegative reduced costs with potentials.
  • Sensitivity: identify whether increasing a given capacity changes the max flow (check if the arc lies in some minimum cut), or bound how much the objective can improve by a small capacity change (by the total increase in a minimum cut’s capacity).
  • Graph-to-LP linkage: write the LP for max-flow or min-cost, identify dual variables (potentials) and complementary slackness meaning.
  • Practice: implement 3–4 Ford–Fulkerson iterations by hand, maintain residuals precisely, and run one SSP iteration with potentials (compute c̄_ij and pick shortest path).

Quick check

  1. Define a residual network and give the formula for forward and backward residual capacities on an arc with no lower bound.
  2. State the max-flow min-cut theorem exactly.
  3. A min-cost flow has no negative-cost cycle in its residual network. Is it optimal? Why?

Answers: (1) Residual network contains arcs with capacities showing how much more we can push or cancel: r_ij^+ = u_ij − x_ij, r_ij^- = x_ij; for MCF, residual arc costs are forward = c_ij, backward = −c_ij. (2) In any network with single source s and sink t, the maximum value of an s–t flow equals the minimum capacity over all s–t cuts. (3) Yes; absence of a negative-cost cycle is necessary and sufficient for optimality in MCF by the cycle optimality condition.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?