The cheapest way to send

Every network in the essays on flows and cuts has had one number on each road: how much it can carry. The questions were how much can get through, and what is the cheapest way to stop it. A real network of pipes, or lorries, or packets, has a second number on every road — what it costs to send one unit along it — and the question that matters is usually not how much can get through but what is the cheapest way to get a given amount through.

That question, minimum-cost flow, contains a surprising amount of what came before. Send one unit through a network with unlimited capacities and it is the shortest-path problem, with prices as lengths. Make every price nought and ask for as much as possible and it is the maximum flow. Put people on one side, tasks on the other, a price on every person–task road and one unit of capacity everywhere, and it is the assignment problem. And the answer to every version comes with the same two certificates — one about cycles and one about prices — which prove a flow cheapest without comparing it with any other flow at all.

Three older problems inside this one #

Each of the special cases is worth seeing inside the general problem, because each certificate is a special case of the general certificate.

The shortest route. Give every road unlimited capacity and ask to send a single unit. The cheapest flow is a single route, and its cost is the length of the shortest route from $s$ to $t$ with prices as lengths. The prices at the places are then distances: the price at $v$ can be taken as the length of the shortest route from $s$ to $v$, and the certificate — every road costs at least the rise in price along it — is the statement that no road offers a shortcut, the familiar condition that distances satisfy the triangle inequality along every road.

The largest flow. Make every price nought, add one extra road from $t$ back to $s$ with price $-1$ and unlimited capacity, and ask for the cheapest circulation. Every unit that goes round saves one, so the cheapest circulation sends as much round as the network allows, and it is the maximum flow. The price certificate becomes a cut: the places whose price is nought on one side, the places whose price is one on the other, and every road crossing from the first set to the second full — which is the cheapest cut, recovered as a set of prices.

The assignment. Two layers, capacities of one, prices on the roads between the layers: the cheapest flow is the cheapest assignment, and the price certificate is the one that assignment essays call a price for every person and task.

Four units, twenty-eight ways #

The network below has five places, from $s$ to $t$, and eight one-way roads. Each road is labelled with its flow, its capacity, and its price per unit: $3/3$ @$1$ means three units flowing along a road that holds three, at one per unit.

There are exactly twenty-eight ways of sending four whole units from $s$ to $t$ within the capacities, and listing them all finds the cheapest: it costs 25. It sends three units $s \to a$ and one $s \to b$; two of the three at $a$ go down to $b$ and one goes across to $c$; three leave $b$ for $c$ and all four go $c \to t$. Read as routes, two units take $s\,a\,b\,c\,t$ at $5$ each, one takes $s\,b\,c\,t$ at $7$ and one takes $s\,a\,c\,t$ at $8$: $10 + 7 + 8 = 25$.

Two roads are not used. The direct $a \to t$ costs $9$ for a single unit and is too dear. The road $b \to t$, which looks like the obvious last step from $b$, costs $6$, and every unit at $b$ does better going to $c$ for $1$ and then to $t$ for $2$. Meanwhile the road $a \to c$, which at $5$ a unit is the second-dearest in the network, carries a unit — because the cheap route through $b$ and $c$ is already full where it matters.

The census shows the cheapest as one of many: costs run from $25$ to $38$, and only one flow reaches the bottom. For a network of five places and eight roads, listing every flow is easy. For any network worth the name it is hopeless — the number of flows grows like a product of capacities — and the whole interest of the subject is that the cheapest flow can be recognised without the list.

A cycle that pays to push round #

Take a flow that is not the cheapest: four units costing $31$, drawn below on the left. It sends two units along $b \to t$ at $6$ each.

The flow leaves some roads with room to spare, and it uses others that it could use less. Record both in a residual network: a road with room left appears forward, at its own price; a road carrying flow appears backward, at the negative of its price, because sending a unit “backward” along it means sending one fewer forward and getting its price refunded. In the residual network of this flow there is a cycle: forward $b \to c$ at $+1$, forward $c \to t$ at $+2$, and backward along $b \to t$ at $-6$. Going round it once costs $1 + 2 - 6 = -3$.

Pushing a unit round a cycle changes the flow without changing what arrives at $t$, since every place on the cycle gains one and loses one. So a cycle of negative cost is an improvement: the flow can send units round it, as many as the cycle’s tightest road allows, and save its cost on each. This one has room for two, saves $6$, and turns the $31$ flow into the $25$ one — the cheapest.

No negative cycle means cheapest #

The converse is the theorem, and it is what makes the cheapest flow recognisable. A flow is cheapest exactly when its residual network contains no cycle of negative cost. Morton Klein stated it as the basis of a method in 1967; the fact itself is older.

One direction was just seen: a negative cycle is a saving. For the other, take the cheapest-looking flow $f$ and any other flow $g$ delivering the same amount. Their difference $g - f$ is a circulation — every place gains what it loses — and every circulation splits into cycles, a unit at a time. Each of those cycles uses roads the way $g$ uses them relative to $f$: forward where $g$ sends more than $f$, backward where it sends less. So each is a cycle in $f$’s residual network, and if none of those costs less than nothing, $g$ costs at least as much as $f$. The census figure checks the statement on all twenty-eight flows: the twenty-seven dearer ones each leave a negative cycle, and the cheapest leaves none.

This is the same shape as the flow–cut theorem, where a flow is largest exactly when the residual network has no route from $s$ to $t$. There, the absence of a path is the certificate; here, the absence of a negative cycle. In both, the certificate is a statement about the one flow in hand, checkable without looking at any other.

Prices at the places #

The absence of a negative cycle has an equivalent form that is easier to check and more useful to have: a price at every place.

Give each place $v$ a price $p(v)$ — here $0$ at $s$, $1$ at $a$, $4$ at $b$, $6$ at $c$ and $8$ at $t$. Read a price as what a unit is worth at that place. A road from $u$ to $v$ with price $c$ is then profitable exactly when carrying a unit along it costs less than the rise in value, $c < p(v) - p(u)$. The prices certify the flow when they line up with it road by road:

• a road that is profitable at these prices is full — $a \to b$ costs $1$ against a rise of $3$, and carries its full two;
• a road that is unprofitable is empty — $b \to t$ costs $6$ against a rise of $4$, and carries nothing;
• a road that is used but not full breaks even — $s \to b$ costs $4$ against a rise of exactly $4$.

If such prices exist, no cycle of the residual network can cost less than nothing, because going round a cycle the price rises and falls back to where it started, and each road costs at least its rise. So the prices are a certificate of optimality that can be checked one road at a time. And they always exist when the flow is cheapest: the cheapest cost of reaching each place along residual roads is one such set of prices, which is how the figure’s were found.

For the assignment problem the same certificate appears as a price for every person and task, numbers on the two sides of a single layer whose sums bound every pairing’s cost. The network version is that idea spread over every place: prices now sit at places that are neither sources nor destinations, a unit’s value can rise along a road and fall again, and the certificate is read one road at a time instead of one pair.

The prices are the other half of a linear program. The flow problem is a program in the flows; its dual is a program in the prices; and the three conditions above are its complementary slackness, the statement that a constraint with slack has a price of nought and a price with slack has a constraint that binds. The prices are also exactly the shadow prices of the network: the rise in price from $s$ to $t$ tells how much the total cost would change if one more unit had to be sent — and it is bracketed by two things the reader can see. Every route in use costs at most $8 = p(t) - p(s)$, the dearest being $s\,a\,c\,t$ at exactly $8$; every route with room costs at least $8$.

Each extra unit costs more #

The cheapest cost of sending $d$ units, as $d$ runs from nought to the network’s maximum of five, is $0, 5, 10, 17, 25, 35$. The first two units cost $5$ each, by the cheapest route $s\,a\,b\,c\,t$; the third costs $7$, because the cheap route is full at $a \to b$; the fourth $8$, the fifth $10$. Each extra unit costs at least as much as the one before, so the curve bends upward — it is convex — and it is a general fact, not a feature of this network. The cheapest way to send $d + 1$ units can always be found by taking the cheapest way to send $d$ and adding one unit along the cheapest route in its residual network, and that route can only get dearer as the network fills.

Convexity is also what makes prices meaningful as a rate. The price rise from $s$ to $t$ at the cheapest flow of four units is $8$, the cost of the fourth unit, and the fifth costs $10$: any rise between $8$ and $10$ would serve as the marginal price of flow at four units, and which one the prices settle on is a choice the certificate does not need to make.

Why the cheapest flow is whole #

Every capacity in the network is a whole number, and the cheapest flow sends whole numbers along every road. That is not a coincidence of this example, and the cycle argument shows why.

Start from any whole-number flow of the right amount — one always exists when any flow does, by the flow–cut theorem’s own construction. If its residual network has a negative cycle, push round it as much as the cycle allows. The amount allowed is the smallest spare capacity or smallest flow along the cycle, and those are all whole numbers, so the new flow is whole too. The prices are whole numbers too, so each push lowers the cost by at least one, the cost is bounded below, and so the pushing stops, at a whole-number flow with no negative cycle — which the theorem says is cheapest. Fractions never enter, because nothing in the procedure ever divides.

That is the flow version of the corners of the assignment polytope being whole, and it is why the census above could list only whole-number flows without missing the answer. It is also the property the multiway cut lacks: there the natural fractional relaxation has corners that are not whole, and no pushing argument turns a fractional answer into a whole one of the same cost.

A problem older than networks #

The cheapest way to send has a much older name. In 1781 Gaspard Monge asked for the cheapest way to move a pile of earth into a hole of the same volume — each grain moved somewhere, at a cost proportional to the distance — and in 1939 Leonid Kantorovich reformulated it as a linear program over how much to send from each source to each destination. With finitely many sources and destinations, Kantorovich’s transport problem is exactly a minimum-cost flow through a network of two layers, and his prices at the sources and destinations are the prices of this essay. He shared the 1975 Nobel prize in economics with Tjalling Koopmans for the idea that such prices are not a bookkeeping device but the right way to plan an economy’s use of scarce roads.

The two-layer network also carries the other structure of these essays. With one unit at each source, one at each destination and capacities of one, the transport problem is the assignment problem, and the cheapest flow is a whole-number assignment — because every flow network with whole-number capacities has a cheapest flow in whole numbers, the same reason the corners of the assignment polytope are whole assignments. The weighted sites of power diagrams are the continuous version: there the prices become weights on the sites, and the regions they carve out are the destinations each source is sent to.

What the pictures cannot show #

Any network larger than this one. Every claim is checked by listing all twenty-eight flows of four units, and all 99 whole-number flows of every size, which is complete for this network and says nothing about how the cheapest flow of a large one is found. The certificates are what scale; the list is what the figures use to confirm the certificates are right.

The cycle decomposition. The argument that any other flow differs from the cheapest by a sum of residual cycles is stated, not drawn. The census checks its conclusion on every flow; it does not show the cycles into which each difference splits.

Fractional flows. Every flow counted has whole numbers on every road. The cheapest flow over all real-valued flows is the same, since the network’s corners are whole, but the figures do not show that; they compare whole flows with whole flows. Nor do they show the prices as the unique certificate — at four units any rise from $s$ to $t$ between the fourth unit’s $8$ and the fifth’s $10$ is consistent with the flow, and the figure draws one choice from that range.

Still open: how far apart two flows can be #

Pushing units round one cycle moves from one flow to another, and in the geometry of the problem that move is a step along an edge of a polytope — the set of all flows delivering a given amount, a many-sided solid whose corners are the whole-number flows. In a flow network the edges of that solid are cycles, and any two corners are joined by a short chain of them: the difference of two flows is a handful of cycles, so the number of steps is small.

For a general linear program the corresponding question is one of the best-known open problems about polytopes. How many edge steps can separate two corners of a polytope with $f$ faces in $d$ dimensions? Warren Hirsch conjectured in 1957 that $f - d$ steps always suffice, and Francisco Santos found a counterexample in 2010. Whether some polynomial in $f$ and $d$ always suffices — the polynomial Hirsch conjecture — is not known; the best general bound, due to Gil Kalai and Daniel Kleitman in 1992, grows faster than any polynomial. Flow polytopes are the tame case, where cycles give a short route between any two corners. Whether every polytope has short routes between its corners, or whether some are genuinely labyrinthine, is still open.