Minimum-cost circulation with lower bounds: Hoffman's theorem, node potentials and an optimality certificate

A city runs night buses between its stops. Each route has a contract: at least a minimum number of buses must run it every night, and the road allows at most a maximum. Every bus costs money to run, except on routes an advertiser sponsors, where the city is paid. Buses end the night where they started, so at every stop as many buses arrive as leave. A schedule like that is a circulation, and the city wants the cheapest one.

Each route is labelled [minimum, maximum] · cost per bus. The advertiser pays 8 for every bus from Harbour to Depot.

Minimums make this harder than a flow problem. With no minimums the empty schedule is always possible, but with them there may be no schedule at all, and when there is one it is not obvious where to start. Two kinds of proof settle each case:

Prices. Give every stop a price $p$ . A route $u \to v$ with cost $c$ has reduced cost $c + p_{u} - p_{v}$ . If every route with a positive reduced cost runs at its minimum and every route with a negative reduced cost runs at its maximum, no schedule is cheaper.
A crowded set of stops. If the minimums force more buses into a set of stops than its outgoing routes can carry, or more out than its incoming routes can bring, there is no schedule.

In code, the stops are numbered $0$ to $n - 1$ (Depot 0, Market 1, Station 2, Harbour 3 above), and a route is (u, v, low, cap, cost).

Background: Minimum-Cost Flow.

Part A: fill the advertiser's route, then pay to feed it

Running every route at its minimum costs 9, but it does not balance. Market receives 3 buses and sends none, while Depot, Station and Harbour each send one more than they receive. The cheapest schedule costs 7:

Route	Buses	Cost
Depot → Market	4	12
Market → Station	3	6
Station → Depot	1	1
Market → Harbour	2	8
Harbour → Depot	3	−24
Station → Harbour	2	2
Harbour → Market	1	2

All 3 buses Harbour → Depot can take are run, and they earn 24. Getting them to Harbour costs something: Station → Harbour is cheap but holds only 2, so the third bus comes Market → Harbour at 4. No other schedule costs 7 or less.

The prices Depot $- 7$ , Market $- 4$ , Station $- 2$ , Harbour $0$ prove it. Station → Depot has reduced cost $1 - 2 + 7 = 6 > 0$ and runs at its minimum. Harbour → Depot has $- 8 + 0 + 7 = - 1 < 0$ and runs at its maximum. Every route strictly between its minimum and maximum has reduced cost 0.

Part B: a crowded pair of stops

The routes into ${1, 2}$ include $0 \to 1$ , whose minimum is 3. The routes out of ${1, 2}$ are $1 \to 0$ and $2 \to 3$ , and they hold only 1 each. So 3 buses must arrive every night and at most 2 can leave, and no schedule exists. The complement ${0, 3, 4}$ proves the same thing from the other side. No other set of stops proves it, and no single stop does.

Hoffman's circulation theorem (1960) says this kind of proof always exists. A schedule exists if and only if, for every set $S$ of stops, the minimums of the routes entering $S$ add up to no more than the maximums of the routes leaving $S$ . It is the max-flow min-cut theorem in other clothes, as part C shows.

Part C: shift, augment, and read the prices off the end

Shift by the minimums. Write each route's flow as its minimum plus an extra amount between 0 and $cap - low$ . Running every route at its minimum leaves each stop with a surplus or a shortfall. What remains is an ordinary flow problem: route the surpluses to the shortfalls using the extra room. Add a source joined to every stop with a surplus and a sink joined from every stop with a shortfall. A schedule exists exactly when the maximum flow from source to sink fills every one of those arcs. If it does not, the stops still reachable from the source in the residual network form part B's proof. Their surplus is stuck behind full routes.

Cheapest paths. Start every paying route at its maximum and every other route at its minimum. Then every arc of the residual network has a cost of at least zero. Successive shortest paths keeps it that way: augment along a cheapest source–sink path each time, using Dijkstra's algorithm with Johnson's potentials. At the end, the residual network has no cycle of negative cost. Its shortest-path distances $d$ satisfy $d_{v} \leq d_{u} + c$ on every residual arc, and they are the prices:

A route below its maximum has a forward residual arc, so $c + d_{u} - d_{v} \geq 0$ .
A route above its minimum has a backward residual arc of cost $- c$ , so $c + d_{u} - d_{v} \leq 0$ .

That is exactly the condition the grader checks.

Why the prices prove it (part D). For any circulation $f$ , the prices cancel out: $\sum_{u \to v} (p_{u} - p_{v}) f_{u v} = \sum_{w} p_{w} ({out}_{w} - {in}_{w}) = 0$ . So every circulation's cost equals its cost under the reduced costs $c^{'}$ . Under $c^{'}$ , a route with $c^{'} > 0$ is cheapest at its minimum and a route with $c^{'} < 0$ at its maximum. Your schedule does both, so no schedule costs less. For the converse: if a cheapest schedule had no prices, its residual network would contain a cycle of negative cost. Pushing one bus round that cycle keeps every contract and saves money, a contradiction.

Going further

Linear programming. The prices are the dual variables of the minimum-cost circulation LP, and the price condition is complementary slackness (LP Duality).
Strongly polynomial algorithms. Successive shortest paths can take as many augmentations as there are buses to move. Tardos gave the first algorithm whose running time does not depend on the numbers at all, and Goldberg and Tarjan showed that cancelling cycles of minimum mean cost is also strongly polynomial.
Almost-linear time. In 2022, Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva solved minimum-cost flow, and with it this problem, in $m^{1 + o (1)}$ time.

References

A. J. Hoffman. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Proceedings of Symposia in Applied Mathematics 10, 1960.
É. Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 1985.
A. V. Goldberg, R. E. Tarjan. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM 36(4), 1989.
L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. Proceedings of FOCS, 2022.

The Night Bus Contracts

Try your rule first

Part A: fill the advertiser's route, then pay to feed it

Part B: a crowded pair of stops

Part C: shift, augment, and read the prices off the end

Going further

References

Price the four stops