Data Pattern Pro

Mathematical programming / Networks and location

Network flows

Route flow through a network of nodes and capacity-limited arcs at minimum cost — the general pattern underlying transportation, assignment, and many logistics problems.

Note Intermediate

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

Given a directed graph with arc capacities and costs, and supply/demand at nodes, find the cheapest way to route flow so every node’s net flow matches its supply or demand requirement.

When to use it

Whenever a problem can be drawn as “stuff flows through a network of nodes and pipes with limited capacity” — traffic routing, supply chain flow across multiple echelons, even project scheduling (as a flow on a precedence graph) can be cast this way. The transportation problem and assignment problem are both special cases of this general pattern.

Formulation

Continuous x_ij = flow on arc (i, j), bounded by capacity u_ij:

minimize   sum(c_ij * x_ij)
subject to:
  sum_j(x_ij) - sum_k(x_ki) = b_i    for all i    # flow conservation
  0 <= x_ij <= u_ij                                for all (i, j)

b_i is the net supply (positive) or demand (negative) at node i; nodes with b_i = 0 are pure transshipment points.

Code sketch

import networkx as nx

G = nx.DiGraph()
G.add_node("plant", demand=-100)
G.add_node("warehouse", demand=0)
G.add_node("store", demand=100)
G.add_edge("plant", "warehouse", weight=2, capacity=80)
G.add_edge("warehouse", "store", weight=1, capacity=100)

flow_cost, flow_dict = nx.network_simplex(G)

For larger instances, a solver like Gurobi/OR-Tools with a dedicated network-simplex or min-cost-flow routine will vastly outperform a generic LP solve — this problem’s special structure means specialized algorithms run orders of magnitude faster than general simplex.

Pitfalls

  • Total supply must equal total demand (sum(b_i) = 0) for the flow conservation constraints to be feasible — add a dummy “slack” node if your real-world supply and demand don’t naturally balance.
  • If you need flow to pass through a node with a processing capacity (not just arc capacity), split that node into an in-node and out-node connected by a single capacitated arc — a standard trick for node-capacitated flow problems.
  • Multi-commodity flow (several distinct products sharing the same network) is a meaningfully harder generalization — don’t assume the same polynomial-time algorithms apply once you add a second commodity.