Minimum-cost flow
Also known as: min-cost flow · MCMF · transportation problem · Monge–Kantorovich problem · successive shortest paths · cycle cancelling · potentials · Suurballe's algorithm
How to carry cargo through a network so that the total cost is smallest. Cancelling a shipment has a negative price, and a plan is best when the residual network has no circle of negative cost; this is proved by “prices” of the vertices, potentials, and the plan is built by shortest paths.
In 1930 A. N. Tolstoi published a paper, “Methods of finding the minimal total kilometrage in cargo-transportation planning in space”. It contained a problem: ten sources of cargo, sixty-eight stations, a hundred and fifty-five railway routes with known distances. 543 thousand tonnes had to be distributed so that the sum of “tonnes × kilometres” was smallest. Tolstoi solved it by hand and checked the solution by going through circles of several shipments. Below is his whole table and a solution by computer.
First, the plan found by an ordinary flow: everything shipped out, every station supplied, but this plan knew nothing of distances: 398,548 thousand tonne-kilometres. Then 30 circles. Each circle is a set of shipments that can be changed at once without breaking a single supply or demand: carry more here, less there. If the sum of distances with signs is negative, the change pays off. The most profitable circle saves 1224 thousand tonne-kilometres: Artemovsk starts shipping to Moscow, Balakhonikha ships to Samara instead of Moscow, Iletsk to Tashkent instead of Samara, and Artemovsk, conversely, no longer ships to Tashkent, 3051 kilometres away.
When no circles are left, the plan costs 395,052 thousand tonne-kilometres, exactly as much as Tolstoi’s plan. A detail Tolstoi wrote out in the paper matches too: from Dzerzhinsk, 25 thousand tonnes to Nizhny Novgorod, 35 to Moscow, 15 to Likino, 10 to Berendeevo, 6 to Ivanovo, 5 to Nerekhta, 4 to Aleksandrov. In 2002 Alexander Schrijver checked the plan with a linear programming program: it is the best. At the end of the scene are the prices that prove this without any program.
The idea
Every arc of the network has, besides its capacity, a cost: the price of carrying one unit along it, in kilometres, tenge, minutes. The cost of a flow is the sum over arcs of “flow × cost”. The minimum-cost flow problem: carry a given amount, or distribute given supplies to given demands, as cheaply as possible. Tolstoi’s transportation problem is a special case: sources, stations and routes between them with no capacity limit.
As in the maximum flow problem, the key tool is the residual network: an arc keeps what can still be added, and its reverse what can be cancelled. Only one thing is new: the reverse arc costs minus the cost of the forward one. Cancelling a shipment of 400 kilometres saves 400 kilometres per tonne. Arcs of negative cost appear in the residual network, and with them circles of negative cost.
A flow is best when its residual network has no circle of negative cost. It can be improved in two ways: take any flow and send units along negative circles while there are any, or grow the flow from zero, each time along the cheapest path of the residual network.
The first way is in the scene above, the second in the code below. Both arrive at the same answer, and for both the same property matters.
Why the plan is the best
A flow with given supplies and demands has the least cost if and only if its residual network has no circle of negative cost.
If there is a negative circle, send along it as much as its narrowest arc allows. Into each vertex of the circle as much comes in as goes out, so supplies and demands do not change, capacities are not violated, and the cost decreases. So the flow was not the best.
Suppose there are no negative circles, and let f* be any other flow with the same supplies and demands. The difference f* − f reads as a flow in the residual network: where f* carries more along an arc, the difference takes its residual, where less, the reverse arc. At every vertex as much of this difference flows in as flows out, since both flows have the same supplies and demands. Such a flow splits into circles: start from any arc where something flows and keep going along arcs with flow (from a vertex where something flowed in, something must flow out) until you come to a vertex already visited. That gives a circle; subtract its smallest flow and repeat. All the circles lie in the residual network and cost at least zero, so the cost of f* − f is at least zero, that is, f* is no cheaper than f.
Tolstoi was apparently the first to notice that the best plan has no such circles, and he checked his plan by circles. But going through all the circles by hand is impossible, and a few found guarantee nothing. Schrijver calculated that a plan with no negative circle of four shipments and none of the seven longer circles Tolstoi checked can cost up to 397,226, 2174 more than the best. A certificate checkable in one pass is needed. Potentials provide it.
The residual network has no circle of negative cost if and only if the vertices can be assigned numbers π(v) so that every arc of the residual network has a reduced cost c(u, v) + π(u) − π(v) of at least zero.
If such numbers exist, take any circle: at each of its vertices π is added once and subtracted once, so the cost of the circle equals the sum of the reduced costs of its arcs, and that is at least zero. Conversely: add a vertex with arcs of zero cost to all the others and compute the shortest distances d(v) from it, say with Bellman–Ford. Without negative circles they are finite, and for any arc the triangle inequality d(v) ≤ d(u) + c(u, v) holds. Set π = d.
In the transportation problem potentials read as prices. The price of a tonne at a source is π(i), the price at a station π(j). A route from i to j always has a forward arc in the residual network, and the condition for it is that the price at the station is at most the price at the source plus carriage, π(j) − π(i) ≤ cij. If cargo goes along the route, there is also a reverse arc of cost −cij, and its condition turns the inequality into an equality. The upshot: a plan is the best if there are prices at which no shipment is cheaper than the difference in prices, and where cargo goes, the difference in prices equals the carriage. Checking this is one pass over 155 routes. That is what the end of the scene does: equality on all 76 routes where cargo goes, inequality on the rest. Leonid Kantorovich in 1939 called such prices “resolving multipliers”, and later “objectively determined valuations”.
Shortest paths one after another
Cancelling circles can take long, and the first plan has to be found separately. Usually one acts differently: start with the empty flow, which has no negative circles, and add flow along the cheapest path from the source to the sink in the residual network. It turns out that the property “no negative circles” is preserved, which means that after each step the flow is the best for its value.
Let the flow f have no negative circles, and let π be potentials with non-negative reduced costs. Find the shortest distances d from the source by reduced costs and send flow along a shortest path to the sink. Then with the potentials π + d all arcs of the new residual network also have reduced costs of at least zero.
We argue about the vertices reachable from the source: flow does not get into the others now or later, because new arcs appear only along the path found. For an arc u → v of the old residual network d(v) ≤ d(u) + cπ(u, v), so the new reduced cost cπ(u, v) + d(u) − d(v) is at least zero. On the arcs of the shortest path the inequality becomes an equality, and their new reduced cost is zero. Sending flow, we add only their reverse arcs, and those have reduced cost zero too. The other arcs of the new network were in the old one as well.
Two consequences follow. Since reduced costs are non-negative, the shortest path can be sought with Dijkstra, although the network has negative arcs; this was noticed by N. Tomizawa in 1971 and by Edmonds and Karp in 1972, with the same trick as in Johnson’s algorithm. And the price of each next unit is at least that of the previous one: in the new network any path from the source to the sink costs at least π(t) − π(s) + d(t), which is the price of the path just found. Tolstoi’s problem takes 89 paths, and their price per unit grows from 0 kilometres (cargo from Murom to Kasimov goes by water) to 2643: the last tonnes are always the most expensive.
Reverse arcs are no decoration here. Here is a simpler problem: a primary and a backup route across the city without common crossings, so that closing one does not affect the other, and together as short as possible. It is a flow of two units where each crossing has capacity 1 and the cost of a street is its length. A greedy way suggests itself: the shortest route, then the shortest around its crossings.
From the Green Bazaar to Panfilov Park the shortest route is 496 metres, and the second one around it 932, together 1428. A flow of two units finds a pair of 1000 metres. Its second path goes 223 metres along the first route against it, and the first route gives up those streets: the cancellations cut out, leaving two routes without common crossings. And from fire station SPCh-7 to MEGA the shortest route cuts across all the roads, and there is no second route around it at all, although a pair exists: 14,663 metres. Giving up the shortest for the sake of the pair is exactly what a reverse arc does.
Code
The network is stored as in the article on maximum flow: arcs in pairs, the partner of arc a is a ^ 1, and the reverse arc has the cost with a minus sign. The path search is Dijkstra by reduced costs, and after each search the distances are added to the potentials. The costs in Tolstoi’s problem are non-negative, so the initial potentials are zeros; if the network has negative costs, Bellman–Ford computes them first.
The last line is a circle from Tolstoi’s paper: if Rostov is given to Dzerzhinsk, Leningrad to Yaroslavl and Moscow to Artemovsk, the circle comes out at +65 kilometres per tonne. The change does not pay, and Tolstoi left Rostov to Yaroslavl. Circles, as in the scene, give the same answer. The circle cheapest by the mean cost of an arc is found by Karp’s algorithm: a table of “the cheapest path of exactly k arcs ending at v” and the minimum over vertices of the maximum over k. Andrew Goldberg and Robert Tarjan recommend choosing the circle this way: then the number of cancellations does not depend on the numbers in the problem.
And the primary and backup routes along the streets of Almaty. Each crossing is split into an entrance and an exit with capacity 1, like the airports in the article on Dinic’s algorithm, only the streets also have a length.
From the Central Stadium to Esentai Mall the greedy way guessed right by chance: the flow’s second path cancels nothing. On the other pairs the flow’s pair is 3.5–30 per cent shorter than the greedy one, and for the fire station the greedy way finds no backup route at all.
What it costs
| Algorithm | Time | Notes |
|---|---|---|
| Successive shortest paths with potentials | O(F · E log V) | F is how many units are carried; each path adds at least one |
| The same with capacity scaling | O(E log U · (E + V log V)) | first in large portions, then smaller; U is the largest capacity |
| Minimum-mean cycle cancelling | polynomial in V and E | Goldberg and Tarjan, 1989: the number of cancellations does not depend on the numbers |
| Network simplex | depends on the arc selection rule | one of the fastest in practice; networkx works this way |
A measurement on networks built like Tolstoi’s: d stations and d/8 sources, each station linked to the three nearest sources. Three ways: shortest paths with potentials and Dijkstra; shortest paths without potentials, in which case the network has negative arcs and each path is found by Bellman–Ford with a queue; and cancelling circles found by Bellman–Ford, starting from an ordinary flow’s plan.
Cycle cancelling at 128 stations is 26 times slower than shortest paths in Python and 8 times in Go, and grows more steeply. And Bellman–Ford with a queue is faster than Dijkstra here, one and a half times in Python and five in Go. This is not a typo: such a network has almost no circles, a vertex enters the queue one and a half times per search on average, while Dijkstra’s heap pays a logarithm for every step. Potentials buy not speed on a convenient network but a guarantee: Dijkstra spends O(E log V) per path on any network, while the Bellman–Ford queue on an unlucky network accelerates to O(V E).
Where it is easy to go wrong
- Dijkstra without potentials. After the first path, arcs of negative cost appear in the residual network, and Dijkstra on the original costs may return a path that is not shortest. The answer is then simply wrong, with no runtime error at all.
- Potentials of unreachable vertices. The distance to a vertex the search did not find is infinite and must not be added to its potential: the potential is left as it is. This is safe, because flow will no longer pass through such vertices.
- Greedily, without reverse arcs. Finding the cheapest path, closing it and looking for the next is the mistake from the routes scene. Without reverse arcs a flow cannot back out of a choice it has made.
- Overflow. The cost is a product of amount and price summed over all arcs. In Tolstoi’s problem it is 3.95 million in hundreds of tonnes per kilometre, but on large networks 32 bits are not enough.
- Not everything distributed. If the sink became unreachable before all supplies were shipped, the problem is infeasible: compare the final flow with the sum of demands rather than silently returning the cost of a partial plan.
Where it works
Transportation problems, warehouses and shops, plants and stations, and assignment problems with capacities. The Hungarian algorithm is successive shortest paths with potentials on a two-part network. Primary and backup paths without common nodes are sought in communication networks with Suurballe’s algorithm (1974), the same flow of two units arranged so that two searches suffice. The distance between two distributions, how much “earth” has to be moved for one histogram to become the other, was named the Earth Mover’s Distance by Yossi Rubner, Carlo Tomasi and Leonidas Guibas in 1998, who compared images by colour this way. In libraries: min_cost_flow in networkx (network simplex), SimpleMinCostFlow in OR-Tools, several algorithms in LEMON.
History
The problem of moving with the least work was posed by Gaspard Monge in 1781 in his “Mémoire sur la théorie des déblais et des remblais”: how to move soil from cuttings to embankments so that the sum of “volume × distance” is smallest. The discrete problem with sources and stations was solved by Tolstoi in 1930. He was apparently the first to notice that the best plan has no negative circles, although he did not prove that their absence is sufficient.
Leonid Kantorovich in 1939, in the book “Mathematical Methods of Organising and Planning Production”, introduced resolving multipliers, those very prices, and in 1942, in a note “On the translocation of masses”, returned to Monge’s problem. Frank Hitchcock formulated the transportation problem in 1941, Tjalling Koopmans studied it in 1948, and George Dantzig solved it with the simplex method in 1951. In 1975 Kantorovich and Koopmans received the Nobel Memorial Prize in Economic Sciences for contributions to the theory of the optimum allocation of resources.
Cycle cancelling as an algorithm was described by Morton Klein in 1967. Successive shortest paths appeared with William Jewell (1958), Masao Iri (1960) and Robert Busacker and Paul Gowen (1961), and the potentials with which Dijkstra suffices with Tomizawa (1971) and Edmonds and Karp (1972). Goldberg and Tarjan showed in 1989 that minimum-mean cycle cancelling makes a polynomial number of steps independent of the numbers, and James Orlin in 1988 gave the first fast such algorithm. In 2022 the almost-linear-time algorithm described in the course chapter solved the minimum-cost problem together with maximum flow.
Problems
In the first problem you have to distribute cargo according to a table, with Tolstoi’s table among the tests, where a greedy plan without cancellations gets stuck. In the second, find a primary and a backup route along the streets of Almaty, and the shortest route will not do for this.
A transport plan A spare routeData: A. N. Tolstoi’s problem (1930): the table from A. Schrijver, “On the history of the transportation and maximum flow problems” (2002) Almaty roads © OpenStreetMap contributors, ODbL Almaty fire stations © OpenStreetMap contributors, ODbL (export of 17 Oct 2026)