Minimum-Cost Flow

Shortest path, maximum flow, transportation, assignment — you have met these as separate puzzles. Here is the surprise: they are all the same puzzle wearing different clothes. The minimum-cost flow problem is the master network model that contains them all. Once you can recognise a decision as "route flow through a network at least cost", you inherit fast algorithms, integer solutions for free, and a way of thinking that unifies half of operations research.

The model

Take a directed network — nodes joined by arcs. Each node i has a number b_i: positive if it is a supply (goods enter the network here), negative if it is a demand (goods must leave), zero if it merely passes flow through. Each arc (i,j) carries a flow x_{ij}, has a capacity u_{ij} it may not exceed, and a cost c_{ij} per unit sent along it. We choose the flows to

\min \sum_{(i,j)} c_{ij}x_{ij} \quad\text{s.t.}\quad \underbrace{\sum_{j} x_{ij} - \sum_{k} x_{ki} = b_i}_{\text{flow conservation}},\;\; 0 \le x_{ij} \le u_{ij}.

The heart of it is flow conservation: at every node, flow out minus flow in equals that node's supply/demand. Nothing is created or lost except at the sources and sinks. This is the language of network flows, now with a price tag on every arc.

Node S supplies 4 units; node T demands them; the middle nodes just relay. Each arc shows its cost and capacity as cost / cap. The task is to push all 4 units from S to T as cheaply as possible without overloading any arc.

One model, four disguises

The power of min-cost flow is how many familiar problems collapse into it once you set the numbers right:

Classic problem	How it becomes min-cost flow
Shortest path	Send 1 unit from source to sink; arc cost = length; capacities unlimited
Maximum flow	All arc costs 0; add a return arc from sink to source with cost −1 to reward flow
Transportation	Sources with supply s_i, sinks with demand d_j, direct arcs, uncapacitated
Assignment	A transportation problem with every supply and demand equal to 1

Learn to translate into this table and a huge range of problems becomes a single solved model.

Why integer data gives integer flow

Min-cost flow is a linear program, so in general its optimum could sit at fractional coordinates. It does not. The node–arc incidence matrix of any directed network is totally unimodular: every square sub-determinant is 0, +1 or -1. A classic result then guarantees that if all supplies, demands and capacities are integers, every vertex of the feasible region — and hence the optimal flow — is integer-valued.

The incidence matrix of a network is totally unimodular.
Therefore, with integer supplies, demands and capacities, an optimal integer flow always exists and is found by ordinary LP methods.
No branch and bound is needed — you never have to fight for whole numbers in a pure network.

Specialised algorithms beat the general simplex handsomely on networks. The network simplex keeps the basis as a spanning tree and pivots by swapping one arc for another — extremely fast in practice. Successive shortest paths repeatedly sends flow along the cheapest remaining route from a source to a sink (using arc costs as distances), while cycle-cancelling starts from any feasible flow and keeps pushing flow around any negative-cost cycle it can find until none remain — at which point the flow is provably optimal. All run in polynomial time.

The hard part of min-cost flow is almost never the arithmetic — solvers handle that. It is seeing that a messy operational question ("route these repairs", "schedule these shifts", "match these donations") is a min-cost flow in disguise, and modelling it as nodes, arcs, supplies, capacities and costs. Miss the pattern and you reach for a slow, bespoke solver; spot it and you get a polynomial algorithm and integer answers for nothing. When a problem smells like "move stuff through a network subject to limits", stop and ask whether it is really min-cost flow.