A mandatory shipment changes what can be undone. If a route carries five units but a contract requires at least three, the reverse residual route can cancel only two. This distinction joins two earlier ideas: the lower-bound feasibility transformation and the cost-improving cycles of a fixed-balance network. We derive an optimality test and a numerical lower bound that can be checked without trusting the algorithm that produced a proposed flow.
Model and residual moves
Let be a finite directed graph without self-loops, with separately labeled parallel and opposite arcs permitted. Each arc has finite real cost and bounds . A feasible flow satisfies and prescribed outflow minus inflow at every vertex. Assume a feasible flow exists; consequently . Its cost is .
Definition 18.1.1
(Residual network with mandatory flow)
For each original arc , retain its label in both residual directions. Its forward residual arc has capacity and cost ; its backward residual arc has capacity and cost . Include a residual arc only when its capacity is strictly positive. A potential assigns the original arc the reduced cost .
Sending along a positive-capacity residual cycle increases the corresponding original flows on forward arcs and decreases them on backward arcs. For no larger than its bottleneck, the bounds remain valid; at every vertex the added residual inflow equals the added residual outflow, so the prescribed balances remain unchanged. The objective change is times the sum of residual costs, including the negative signs on backward arcs. A simple cycle using both directions of the same original arc merely cancels itself and cannot have negative cost.
Optimality and a checkable lower bound
Theorem 18.1.2
(Bounded-flow optimality and prices)
For a feasible flow , the following are equivalent:
- has minimum cost among all feasible flows.
- Its positive-capacity residual network has no negative-cost directed cycle.
- A potential exists for which every positive-capacity residual arc has nonnegative reduced cost. Equivalently, for each original arc with reduced cost ,
- implies ;
- implies .
For any potential, whether or not is optimal, every feasible flow has cost at least
A feasible flow attaining is optimal.
Concept lensStructural
The bound as a relaxation of the balances
Let be the vertex–arc matrix, so that is the outflow minus inflow at . Since , the bound is
The balance equations move into the objective with multipliers , and only the box constraints remain, which separate arc by arc. Every feasible makes the added term zero, which is the lower bound again. The theorem adds that the best multipliers close the gap: some has equal to the minimum cost.
Proof
(Cycle decomposition, shortest-path prices and a weak-duality identity)
A negative residual cycle can be augmented by its positive bottleneck, producing a feasible flow of strictly lower cost; thus an optimum has none. Conversely, let be any other feasible flow. Represent by that much flow on the forward residual arc and by on the backward arc. Bounds ensure these residual arcs exist and have enough capacity. Equal balances make this nonnegative residual assignment a circulation. Decompose it into weighted directed cycles: follow positive arcs until a vertex repeats, subtract the smallest assignment on that cycle, and repeat. Conservation is preserved and at least one positive arc disappears each time. The cost difference is the sum of cycle costs times their nonnegative weights. With no negative cycle it is nonnegative.
If a potential makes all residual reduced costs nonnegative, the potential differences telescope around each cycle, so every cycle has nonnegative cost. Conversely, when no negative cycle exists, add a temporary source with zero-cost arcs to every vertex. Shortest-path distances are finite: any repeated cycle can be removed from a walk without increasing cost, leaving a simple path. The distance inequality gives nonnegative reduced cost for every residual arc. For a backward arc its reduced cost is , yielding the two original-arc implications. Fixed arcs have neither residual direction and impose no sign restriction.
Finally, for any feasible , the balance equations imply
Each is at least its minimum over , proving the bound. If equality holds for a feasible , no feasible flow can cost less. In particular, the sign conditions make a minimizer of over each interval, so the optimality prices yield equality.
Proof X-ray
What each bound contributes
Lower bounds enter the proof at one point: writing as a residual assignment. A decrease is carried by the backward arc, and it fits because keeps it at most the backward capacity ; an increase fits under for the same reason. That is why the residual network must use rather than . The passage from no negative cycle to prices needs only finiteness: walks can be shortened to simple paths, so the shortest distances exist. The final identity needs equal balances, and the interval minimum then reads off the sign conditions. A positive reduced cost favors the lower endpoint, a negative one the upper endpoint, an interior flow has both residual directions and forces zero, and a fixed arc imposes nothing. Omitting the potential term changes the value of the bound, so the remaining sum is not in general a valid lower bound.
Worked examples
Worked example 18.1.3
(A contract blocks a tempting cancellation)
There are arcs , , , all with upper bound ; their lower bounds are and costs are . Let , , . Conservation forces the flows to be , and the bounds give . The cost is , so is optimal with cost .
This conclusion also has a certificate that does not require enumerating . Set . The original reduced costs are . Hence
Common mistake
(Canceling below the contract minimum)
At the first route is at its lower bound, so its backward residual capacity is . If we incorrectly used capacity , we would invent a negative residual cycle of cost . It would decrease below the contract minimum and is not a legal move.
Worked example 18.1.4
(Augmenting to the other endpoint)
Keep the network and bounds, but change costs to . At , the residual cycle has cost and bottleneck : the backward capacity of is . Augmenting once gives at cost , down from . With , the reduced costs are and . Thus the new flow is optimal. The positive reduced cost on is consistent with its zero lower bound; it does not require every original arc to have zero reduced cost.
Counterexample mode
One sign check is not enough
On the second example, at choose . All original costs are positive, but the backward residual arcs have negative costs. Testing only original forward arcs would falsely certify optimality; the negative cycle above gives an explicit cheaper feasible flow.
The third example isolates the boundary case in which an arc has no residual direction at all.
Worked example 18.1.5
(A fixed arc may carry any reduced cost)
Take arcs with and cost , and , with bounds and cost . Let , , . Conservation at gives and at gives , so is the only feasible flow; its cost is .
Both flows on and are interior, so a certificate needs . With this forces and then , and the fixed arc has . Then
so the certificate is exact even though a positive reduced cost sits at an upper bound. If instead the first arc had bounds , the same sign would violate the condition ; indeed, rerouting all three units through then costs .
Algorithm and limitations
A cycle-cancellation method starts from a feasible flow, searches the entire residual network for a negative cycle, augments to its bottleneck, and repeats. If the bounds, balances and starting flow are integral, each bottleneck and each later flow is integral. Finite capacities then leave finitely many integral feasible flows; every negative-cycle augmentation strictly decreases cost, even for real costs. Hence this integral-start version terminates, and the theorem certifies its result. A feasible integral start exists when integer data pass the lower-bound feasibility test. This finite-state proof does not assert a polynomial running time, and it does not prove finite termination for an arbitrary real-valued start.
A potential can be shifted by the same constant at all vertices without changing reduced costs or , because total balance is zero. A price certificate needs to cover every residual component, not merely vertices reachable from one supply node. Numerical implementations must account for rounding separately; exact strict signs and exact equality are used here.
Exercises and solutions
Quick check
(In the first example, set . Compute its cost and the cost change from augmenting the residual cycle to its bottleneck.)
Solution · Answer
The flow is and costs . The cycle cost is ; its bottleneck is because the backward residual capacity is . Cost decreases by to .
Quick check
(Suppose , , . Which endpoint minimizes ? If this potential certifies a feasible flow as optimal, what must that flow do on the arc?)
Solution · Answer
The minimum is at . Equality in the certificate requires . Equivalently, under this certificate a negative reduced cost forbids a positive forward residual capacity.
Quick check
(An arc has and . Must its reduced cost vanish in an optimal certificate? What is its contribution to the interval minimum?)
Solution · Answer
No. Neither direction has positive residual capacity. The interval consists only of , and the minimum is .
Quick check
(In the second example, replace by . Recompute and explain why it agrees with the previous value.)
Solution · Answer
Reduced costs remain . The balance contribution is , and the interval contributions sum to zero. Thus ; adding a constant changes by that constant times .