This unit continues the earlier flow unit. Flow value is now prescribed by supplies and demands; the objective is the cost of routing that flow. We develop cycle cancellation, transportation exchanges, and a primal-dual assignment algorithm.
Motivation
Two flows can deliver the same amount while using very different resources. A scheduler may route tasks through a network of processors with differing transfer costs. Conservation fixes what each node supplies or receives, so increasing source throughput is no longer the objective. We want to rearrange an already feasible flow until no cheaper rearrangement exists.
For fixed supplies, the difference between two feasible flows has zero net balance at every vertex. The appropriate improvement is therefore a cycle rather than an additional source-to-sink path. A backward residual arc still means canceling an old decision, and its cost must be the negative of that old arc's cost. Forgetting this sign destroys the interpretation of an exchange.
Potentials turn a global search for improving cycles into local inequalities. A vertex price changes each arc cost by a telescoping difference. Cycle costs stay unchanged, so nonnegative reduced costs certify that no improving circulation remains. In assignment, the same idea becomes row and column labels, with zero reduced-cost edges exposing the best matching.
Definitions
Definition 6.1.1
(Fixed-balance minimum-cost flow)
On a finite directed network, let with finite capacities. Require net outflow at vertex to be , where . Minimize . Assume a feasible flow exists unless infeasibility is being checked explicitly.
For original arc , the forward residual arc has capacity and cost ; the backward residual arc has capacity and cost . A vertex potential gives reduced residual cost
Parallel and antiparallel arcs keep their original labels. A residual directed cycle can include backward arcs. Its bottleneck is the least residual capacity, and augmenting that amount preserves every prescribed balance. A negative total residual cycle cost makes the objective strictly decrease.
A transportation model has nonnegative supplies , demands , equal total supply and demand, and variables with row sums and column sums . Its cost is . Assignment is the special case of equal numbers of rows and columns, each sum one. A perfect matching chooses exactly one edge at each row and column. In the complete assignment model, all pairings have finite costs.
Theorem/proposition
Theorem 6.1.2
(Negative cycles and potentials characterize optimality)
A feasible fixed-balance capacitated flow is minimum-cost if and only if its residual network has no negative-cost directed cycle. Equivalently, there exists a potential for which every positive-capacity residual arc has nonnegative reduced cost.
Theorem 6.1.3
(Tight matchings certify assignment optimality)
If row labels and column labels satisfy , every feasible assignment has cost at least . A perfect matching using only tight edges attains that bound and is optimal. The alternating-tree label-update algorithm below finds such a matching in finitely many steps for a finite complete cost matrix.
These certificates do not require integer costs. Integer supplies and capacities guarantee that an integral optimal flow exists (cycle cancellation from an integral feasible start preserves integrality); cost integrality supplies an additional simple bound on the number of cost-decreasing iterations. Feasibility must still be obtained, for example through a capacity-feasibility flow calculation. Potentials cannot certify a nonexistent feasible decision.
Proof sketch or proof idea
A negative residual cycle permits a positive bottleneck augmentation, preserving balances and reducing cost by bottleneck times cycle cost. An optimum cannot contain one.
For the converse, compare a current feasible flow with any competitor. A positive difference on an original arc is represented by its forward residual arc, and a negative difference by its backward residual arc with nonnegative magnitude. Capacity bounds make all these changes permissible. The resulting residual assignment is a nonnegative circulation.
Every finite nonnegative circulation decomposes into nonnegative multiples of directed cycles. Starting on a positive arc, conservation lets us continue along positive arcs until a vertex repeats. Extract the resulting cycle and subtract its smallest assigned arc amount. At least one positive arc disappears. Repeat; finitely many arcs make the process finite. The cost difference is the sum of these cycle costs times their nonnegative weights. If no cycle is negative, no competitor is cheaper.
Potentials do not alter cycle costs because their vertex differences telescope. Thus nonnegative reduced costs exclude negative cycles. Conversely, attach a temporary vertex with zero-cost outgoing arcs to every original vertex. If the residual network has no negative cycle, shortest distances from the temporary vertex are finite: repeated vertices can be removed without increasing a walk's cost, leaving one of finitely many simple paths. Their distance labels satisfy , exactly the required reduced-cost inequalities. The temporary vertex handles components unreachable from any particular original source.
Proof X-ray
How a global comparison becomes a sum of cycles
The converse never inspects competitors one by one; it rewrites their difference from the current flow. Capacity bounds make that difference a nonnegative assignment to residual arcs, and backward arcs are indispensable here: a decrease on an arc is recorded at cost . Equal balances make the difference conserve flow at every vertex, which is what lets the walk in the decomposition always continue. Finiteness ends the decomposition, since each extraction deletes an arc. The closing move is linearity: the cost difference is a nonnegative combination of cycle costs. Potentials enter only afterwards, as a shortest-path certificate that no negative cycle exists.
For assignment, multiply each label inequality by its nonnegative assignment variable and sum. Unit row and column totals leave the claimed lower bound. A tight perfect matching attains it. Notice that tightness without a perfect matching is insufficient: two rows may compete for the same tight column.
A finite primal-dual assignment algorithm
Initialize and . Optionally increase each column label by the minimum remaining reduced cost in that column; this preserves all dual inequalities and is the column reduction used below. Find a matching in the tight-edge graph. From an unmatched row, search alternating paths: travel from a row along tight edges to columns and from a matched column along its matched edge back to its row. Reaching an unmatched column gives an augmenting path; flipping its matched/unmatched edges increases the matching size by one.
If no such path exists, let be the reached rows and the reached columns. Every reached column is matched to a reached row; the unmatched root gives . At least one column is outside , because the matching is not perfect. Set
Increase by on and decrease by on . For edges from to outside , slack decreases but stays nonnegative. For edges from outside to , it increases. Other slacks do not change. Matching edges and the existing alternating tree remain tight, and at least one new tight edge leaves .
Continue the search. The new edge reaches a free column, giving augmentation, or a matched column whose matched row enlarges the tree. Before the next augmentation, reached sets only grow, so finitely many label updates suffice. There can be at most as many augmentations as rows. This proves finite termination and, through the tight-matching theorem, optimality. Missing allowed edges require a separate infeasibility treatment; they should not be represented by an unjustified arbitrary large cost.
Cycle cancellation as a transportation algorithm
A complete balanced transportation problem has an elementary feasible start: allocate as much as possible to the current row and column, exhaust one, and continue to the next. At each step at least one remaining row or column is exhausted, so this construction finishes. Zero supply or demand is simply skipped.
Treat each row-to-column shipment as an arc; a rectangular transportation exchange is a residual cycle alternating increased and decreased cells. Search for any negative residual cycle, augment to its bottleneck, and repeat. With integer supplies, demands, and an integer feasible start, each shipment stays integer. All shipments are bounded by the total shipped amount, so there are finitely many integer feasible arrays. Strict cost descent therefore terminates even for real costs. If costs are also integers, every decrease is at least one, yielding an objective-range bound. This is a finite algorithm, though it does not establish a polynomial running-time bound.
Worked examples
Worked example 6.1.4
(A transportation exchange lowers cost by five)
Supplies are , demands , and the cost matrix is
The feasible array costs eleven. Increase cells and , decrease and . The residual cycle cost is , and its bottleneck is one. The new array is , cost six.
Use transportation labels and . Their sums are at most the corresponding costs, and every positive cell of the new array is tight. The dual bound is . Thus the improvement reached an optimum, rather than merely a cheaper feasible arrangement.
Worked example 6.1.5
(A Hungarian label update creates the missing matching edge)
For
row minima give . Subtracting these and then column minima gives and reduced matrix
Match row one to column two and row three to column one. Row two is unmatched. Its alternating search reaches rows and columns . Crossing slacks are , so .
The updated labels are and , with bound five. The new tight edge from row 2 to column 1 reaches matched row 3. The augmenting path row 2–column 1–row 3–column 3 flips the old row-3 match. The resulting tight matching has cost . Labels are unrestricted in sign: the negative second column label is legal and necessary for this particular update.
Worked example 6.1.6
(A negative raw cost can have a nonnegative reduced cost)
Take two vertices , balance zero, capacities one in both directions, and costs , . At zero flow the sole two-arc cycle costs one, so adding a circulation cannot help. Choose . Reduced costs are on and on .
Thus zero flow is optimal despite a negative original arc. If the reverse cost changes to one, the cycle cost becomes minus one; sending one unit on each arc gives total cost minus one. Both residual directions then reverse, with cycle cost positive one, certifying the new minimum. The relevant obstruction is a negative cycle, not a negative individual arc.
Concept lensCombinatorial
A price update repairs a matching obstruction
Before the assignment update, all reached rows can reach only reached columns along tight edges, and there is one more reached row than reached column. The current zero-cost graph lacks enough choices for those rows. The smallest crossing slack is exactly the price change needed to expose another choice while preserving all earlier tree edges. This connects the numerical label update to the combinatorial obstruction it repairs.
Common mistakes
Maximum flow and minimum-cost fixed-balance flow use different improvement objects. An arbitrary augmenting source-to-sink path changes balances and is not a legal move in the fixed-balance model. A residual cycle preserves them.
The cost of a backward residual arc is the negative original cost, regardless of whether that original cost was positive or negative. A potential must satisfy inequalities on every positive-capacity residual arc, including backward ones. Checking only unused forward arcs can miss a cheaper reassignment.
Zero reduced-cost edges alone do not certify assignment optimality until they contain a perfect matching. Conversely, row or column labels need not be nonnegative. Their constraint is the sum inequality, and an arbitrary sign restriction can destroy dual feasibility or prevent the correct update. Integer supplies and demands guarantee an integral optimal decision and an integrality invariant of the algorithm; they do not mean that every real optimal array has only integer entries.
Summary
For fixed balances, residual cycles describe every possible improvement. Nonnegative reduced costs are equivalent to the absence of negative cycles and give a local optimality certificate. Transportation uses these cycles as shipment exchanges. Assignment specializes the same dual logic into tight edges and finite alternating-tree price updates. Integrality and running-time claims require their own stated assumptions.
Exercises
Quick check
(In the transportation example, verify all four label inequalities and identify the only unused cell. Why need its inequality not be tight?)
Solution · Answer
The label sums are , at most . The unused cell is , whose inequality is strict. Complementary products multiply each nonnegative slack by the corresponding shipment; zero shipment permits positive slack without changing equality of primal cost and dual bound.
Quick check
(For assignment costs , find a tight perfect matching and labels certifying its cost.)
Solution · Answer
Choose edges and , cost three. Labels and are feasible: their sums are , at most . The selected two edges are tight and the label total is three, proving optimality.
Quick check
(A feasible flow has residual cycle costs . If the negative cycle bottleneck is , what is the cost change? Does a zero-cost cycle prove nonuniqueness?)
Solution · Answer
Cost changes by . A positive-bottleneck zero-cost residual cycle produces a distinct equal-cost feasible flow; if the original flow was optimal, this proves nonuniqueness. Without original optimality, it only produces another flow of the same possibly suboptimal value.
Quick check
(Explain why a negative cycle in a residual component disconnected from the main supply vertices can still matter to the fixed-balance minimum-cost problem.)
Solution · Answer
A circulation has zero balance at every vertex, including supply-free vertices. A negative cycle in any component can therefore lower total cost without affecting prescribed deliveries elsewhere. A potential obtained only from one original source can miss that component; the temporary all-reaching source in the proof avoids this omission.