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 be kits per week shipped on directed arc , with capacity and cost minutes per kit. Minimize subject to and
for every node , where positive is supply and negative is demand. Units balance only when .
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 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.
OPTIMALapplies to the encoded network; omitted handling constraints and uncertain travel times remain unvalidated.
Practice
Reduce capacity on arc 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.