Circulation Problem, in depth: Hoffman's theorem, infeasibility certificates, minimum cost circulation and fleet sizing

The model and what it generalises

Take a directed graph G = (V, E). Each edge has a lower bound l(e), a capacity c(e) with l(e) <= c(e), and optionally a cost w(e) per unit. A circulation is an assignment f with l(e) <= f(e) <= c(e) on every edge such that, at every node, flow in equals flow out. The two questions are whether any circulation exists, and if so which one has the lowest total cost, the sum of w(e)f(e).

Three facts make the model useful:

• It generalises max flow. Add an edge t to s with capacity infinity and cost -1, give every other edge cost 0, and the minimum cost circulation pushes as much flow as possible around through t-to-s. That amount is the maximum s-t flow.
• It generalises min cost flow. To demand exactly k units from s to t, add t to s with l = c = k. Supplies and demands at many nodes become edges from and to one hub node.
• It is integral. If every bound is an integer and some circulation exists, an integer circulation exists, and an integer minimum cost circulation exists. That is what lets a lower bound of 1 mean 'this trip must be covered by one whole vehicle'.

Feasibility is not automatic, even when l(e) <= c(e) on every edge. On the triangle 0 to 1 with bounds [3, 5], 1 to 2 with [0, 2] and 2 to 0 with [0, 9], node 1 must receive at least 3 units and can pass on at most 2. Every edge is satisfiable on its own, but no circulation exists. Real models fail the same way, only with thousands of edges and no obvious culprit.

Hoffman&#x27;s theorem and the infeasibility certificate

Hoffman's circulation theorem (1960) gives the exact condition. A feasible circulation exists if and only if, for every set of nodes X, the lower bounds on edges entering X add up to no more than the capacities on edges leaving X:

sum of l(e) over edges into X <= sum of c(e) over edges out of X.

The 'only if' direction is just conservation. Whatever flows into X must flow out, at least the lower bounds flow in, and at most the capacities flow out. The 'if' direction is the max-flow min-cut theorem in disguise. It is also what makes the condition useful in practice: the set X that violates it is a certificate, a small, checkable explanation that a human can read.

The certificate comes for free from the standard reduction. Push every lower bound in advance, so edge u to v keeps capacity c - l, and v gains excess l while u loses it. Connect a super-source S to each node with positive excess and each node with negative excess to a super-sink T, then run max flow. A circulation exists exactly when the max flow saturates every S edge. If it does not, take X as the set of original nodes still reachable from S in the residual graph. That X violates Hoffman's condition, because the min cut separates it from the rest. On the triangle above, the solver returns X = {1}, lower bounds in = 3, capacity out = 2.

Return that triple from your API. 'Infeasible' gives an operator nothing to act on. 'Depot B must receive 3 vehicles and can release at most 2' tells them which constraint to relax, and that is the difference between a solver people trust and one they route around.

Minimum cost circulation by cycle cancelling

Once some circulation exists, make it cheap. The optimality condition is the same as for min cost flow: a circulation has minimum cost if and only if its residual graph has no negative-cost cycle. If such a cycle exists, pushing one unit around it keeps every node balanced, stays within the bounds because it uses residual capacity, and lowers the cost. If no such cycle exists, the difference between this circulation and any other decomposes into residual cycles, none of them negative, so nothing is cheaper.

That condition gives the simplest algorithm, cycle cancelling: find a feasible circulation, then repeatedly find a negative cycle with Bellman-Ford and push its bottleneck capacity around it. Each cancellation lowers the cost by at least one unit when costs are integers, so the loop terminates. A naive choice of cycle can take a number of rounds that grows with the costs and capacities, though. Cancelling the cycle with the minimum mean cost, found with Karp's algorithm, is Goldberg and Tarjan's strongly polynomial variant: its number of rounds depends only on the numbers of nodes and edges.

Here is the core of a tested implementation. _maxflow is a plain Dinic that returns the flow value and the BFS levels of its last phase; a node is reachable from S exactly when its level is not -1. Arcs are stored in pairs, so e ^ 1 is the reverse of e.

def solve(self):
    n = self.n; S, T = n, n + 1
    self._build(n + 2)
    excess = [0] * n
    ids = []
    for u, v, low, cap, cost in self.edges:
        ids.append(self._arc(u, v, cap - low, cost))   # pre-push the lower bound
        excess[v] += low; excess[u] -= low
    need = 0
    for v in range(n):
        if excess[v] > 0: self._arc(S, v, excess[v], 0); need += excess[v]
        elif excess[v] < 0: self._arc(v, T, -excess[v], 0)
    got, level = self._maxflow(S, T)
    if got < need:                                     # infeasible: Hoffman certificate
        X = {v for v in range(n) if level[v] >= 0}
        lin = sum(l for u, v, l, c, w in self.edges if u not in X and v in X)
        cout = sum(c for u, v, l, c, w in self.edges if u in X and v not in X)
        return None, (sorted(X), lin, cout)            # lin > cout always
    real = set()
    for e in ids: real.add(e); real.add(e ^ 1)
    while True:                                        # cancel negative cycles
        cyc = self._negative_cycle(n, real)
        if not cyc: break
        d = min(self.capr[e] for e in cyc)
        for e in cyc:
            self.capr[e] -= d; self.capr[e ^ 1] += d
    return [self.edges[i][2] + self.capr[e ^ 1] for i, e in enumerate(ids)], None

def _negative_cycle(self, n, real):
    dist = [0] * n; pred = [-1] * n                    # virtual source to every node
    for _ in range(n):
        x = -1
        for e in real:
            if self.capr[e] > 0:
                u, v = self.to[e ^ 1], self.to[e]
                if dist[u] + self.cst[e] < dist[v]:
                    dist[v] = dist[u] + self.cst[e]; pred[v] = e; x = v
        if x < 0: return None                          # a quiet pass: no negative cycle
    for _ in range(n): x = self.to[pred[x] ^ 1]        # walk back onto the cycle
    cyc, v = [], x
    while True:
        e = pred[v]; cyc.append(e); v = self.to[e ^ 1]
        if v == x: return cyc

Two details matter. Cycle search runs only over the real arcs, so it never moves flow through S or T and the lower bounds stay satisfied. And the final flow on edge e is its lower bound plus whatever its reduced arc carries. Bellman-Ford costs O(VE) per round, which is fine for models of a few thousand edges. Beyond that, use a network simplex or cost-scaling solver, as discussed under trade-offs.

Worked example: sizing a fleet

Dantzig and Fulkerson's 1954 tanker-scheduling paper posed a problem of this type: cover a timetable of trips with as few vehicles as possible. Here is a small version. Seven trips run between three cities. Driving empty (deadheading) takes 2 hours between A and B, 2 between B and C, and 3 between A and C.

Each trip becomes a start node and an end node joined by an edge with bounds [1, 1], so it must be driven exactly once. A depot node sends a pull-out edge [0, 1] to every trip start, at a cost V per vehicle, and every trip end has a free pull-in edge back to the depot. An edge from the end of Ti to the start of Tj exists when Ti's arrival time plus the travel time from Ti's destination to Tj's origin is no later than Tj's departure. Its cost is the deadhead hours. Whatever leaves the depot must return, so the flow through the depot is the fleet size.

With V = 100, the solver returns cost 202: two vehicles and two deadhead hours. Vehicle one drives T1, T3, T5, then deadheads from A to B (arriving at 16:00) to drive T7. Vehicle two drives T2, T4 and T6. Two is a provable lower bound, because T1 and T2 overlap between 07:00 and 08:00. With V = 1, the same model returns cost 3: a third vehicle drives T7, because one vehicle-day is now cheaper than two empty hours. The model did not change; one price did, and that price is now an explicit number your planners own.

To read the schedules back, decompose the circulation. Start at the depot, follow any edge with positive flow, decrement it, and continue until you return. Each walk is one vehicle's day. Integrality guarantees each walk carries a whole unit.

Operational guidance

Using circulations in production is mostly about the edges you choose and the answers you check.

• Verify every answer in linear time. Check l(e) <= f(e) <= c(e) on every edge and zero net flow at every node, and recompute the cost. The check is ten lines and catches indexing bugs that no unit test anticipated.
• Verify every infeasibility claim the same way. Recompute the certificate sums from the original edges, not from solver state, and assert lower bounds in exceed capacity out.
• Prune connection edges. All-pairs connections grow quadratically with the number of trips. Cap them with a maximum idle gap, or connect only the next few feasible trips at each location; record the cap, because it can remove the optimal answer.
• Turn hard bounds into soft ones when policy allows. Add a parallel overflow edge with a high cost. The model then always solves, and the overflow flow tells you exactly how much each constraint was violated and where.

Failure modes

The failures that show up in real deployments:

• Cancelling through the super-source. If cycle search includes the S and T arcs, flow can drain off the lower bounds and the 'optimal' answer violates them. Restrict the search to real arcs, as the code does.
• Reading the certificate from the wrong side. X is the set reachable from S, not its complement. Taking the complement returns a set that satisfies Hoffman's condition and explains nothing; the certificate check above catches it.
• Stopping Bellman-Ford early in the wrong place. The node relaxed in the last pass may hang off a negative cycle without lying on it. Walk back n predecessor steps first, or you will trace an infinite path.
• Time wrap-around. A daily rotation that runs past midnight needs a connection from late arrivals to early departures on the next day, or the model silently assumes every vehicle sleeps at the depot.

Trade-offs

Keep the simple solver as the test oracle for the fast one; the certificate code is shared.

What to do next

1. Implement the reduction and certificate above and test them against brute-force enumeration on graphs with 2 to 4 nodes and bounds up to 2.
2. Add the linear-time verifier and run it on every solver answer in production, not just in tests.
3. Model one recurring schedule you own (rotations, shifts or batch-job slots) as a circulation, and price the fleet-versus-idle trade-off explicitly.
4. Make infeasibility return the set X and both sums, and render them in the UI.
5. Read the max-flow min-cut theorem proof to see why the reachable set is always a valid certificate.
6. When models outgrow Bellman-Ford, move to a network simplex solver and keep the simple one as a test oracle.