Skip to main content

Network-Flow Problems

Flow models preserve a quantity as it moves through a network. Their central discipline is balance: every unit must have a declared origin, destination, and path through capacity-limited arcs.

Prerequisites​

Complete assignment and matching problems.

Learning goals​

  • Define nodes, directed arcs, capacities, supplies, demands, and per-unit costs.
  • Write flow conservation with a consistent sign convention.
  • Validate capacity, balance, and total cost independently.
  • Know when a min-cost-flow interface is narrower and clearer than a general MILP.

Formulation before solver choice​

Let fij∈Z≥0f_{ij}\in\mathbb{Z}_{\ge0} be kits per week shipped on directed arc (i,j)(i,j), with capacity uiju_{ij} and cost cijc_{ij} minutes per kit. Minimize ∑cijfij\sum c_{ij}f_{ij} subject to 0≤fij≤uij0\le f_{ij}\le u_{ij} and

∑jfij−∑jfji=bi\sum_j f_{ij}-\sum_j f_{ji}=b_i

for every node ii, where positive bib_i is supply and negative bib_i is demand. Units balance only when ∑ibi=0\sum_i b_i=0.

The repository-owned instance sends five kits from depot 0 to destination 3 through two transfer nodes. OR-Tools SimpleMinCostFlow uses integer capacities, supplies, and costs. It is a specialized exact interface for this encoded network, not a generic routing or nonlinear solver.

Worked example​

from ortools.graph.python import min_cost_flow

starts = [0, 0, 1, 2]
ends = [1, 2, 3, 3]
capacities = [3, 4, 3, 4]
unit_costs = [2, 1, 1, 3] # minutes per kit
supplies = [5, 0, 0, -5]

flow = min_cost_flow.SimpleMinCostFlow()
for arc in zip(starts, ends, capacities, unit_costs):
flow.add_arc_with_capacity_and_unit_cost(*arc)
for node, supply in enumerate(supplies):
flow.set_node_supply(node, supply)
status = flow.solve()
if status != flow.OPTIMAL:
raise RuntimeError(f"min-cost-flow status={status}")

arc_flows = [flow.flow(arc) for arc in range(flow.num_arcs())]
balances = []
for node in range(4):
outflow = sum(arc_flows[a] for a, start in enumerate(starts) if start == node)
inflow = sum(arc_flows[a] for a, end in enumerate(ends) if end == node)
balances.append(outflow - inflow)

print(f"status=OPTIMAL arc_flows={arc_flows} shipping_minutes={flow.optimal_cost()}")
print(f"capacities_respected={all(f <= u for f, u in zip(arc_flows, capacities))}")
print(f"net_outflow={balances} matches_supplies={balances == supplies}")

Expected output:

status=OPTIMAL arc_flows=[3, 2, 3, 2] shipping_minutes=17
capacities_respected=True
net_outflow=[5, 0, 0, -5] matches_supplies=True

The specialized solver reports OPTIMAL. Balance and capacity are then recomputed from returned arc flows, while enumerating the depot split f01=0,…,3f_{01}=0,\ldots,3 independently confirms that sending three kits through node 1 and two through node 2 gives the unique minimum cost of 17 minutes.

Limitations and common mistakes​

  • A missing arc means transport is impossible, not merely expensive.
  • Reversing the supply sign convention makes a valid network appear infeasible.
  • Arc capacity and node supply must use compatible units and time periods.
  • Fixed charges, shared vehicle decisions, time windows, or nonlinear congestion require a richer formulation.
  • OPTIMAL applies to the encoded network; omitted handling constraints and uncertain travel times remain unvalidated.

Practice​

Reduce capacity on arc 1→31\rightarrow3 from three to two kits. Re-solve, recompute every node balance, and explain why feasible total supply can still become infeasible when a cut lacks capacity.

Next steps​

Compare selecting value under one capacity with using the fewest containers in knapsack and bin packing.

Primary sources​

Checked 2026-10-19: Google OR-Tools 9.15, minimum-cost-flow guide and Python interface, flow overview, and OR-Tools Apache-2.0 license statement.