Directed cycle Created 2026-10-07 Updated 2026-10-14
A closed directed path whose vertices are distinct except for the common start and endpoint is a directed cycle. In a residual network, augmenting around a directed cycle preserves flow balance. A negative total cost on such a cycle gives an improving displacement for a minimum-cost flow.
Divergence of a flow Created 2026-09-24 Updated 2026-10-18
The divergence of a flow at a vertex is net outward flow. For original nonnegative edge amounts and their signed net record, respectively,
Positive divergence of a flow means net supply, negative divergence of a flow means net demand, and zero is flow conservation. This is the same sign convention as flow balance.
In the running example, the divergences of a flow at are . Adding the four divergences of a flow gives zero: every edge contributes positively at one endpoint and negatively at the other. In a finite flow network, this cancellation explains why net supply at equals net demand at .
Feasible flow 2026-10-14
A feasible flow satisfies every flow balance and every capacity interval of a network problem. Feasibility is distinct from optimality: capacitated flow optimality conditions additionally certify that no allowed balanced flow displacement reduces the cost. With only one independent graph cycle, every balanced flow is determined by a single cycle parameter, and its feasible set is the intersection of the induced parameter intervals.
For a connected capacitated minimum-cost flow network, a spanning tree supplies basic flow variables. Every non-tree edge is fixed at its lower or upper bound. Flow balance determines the tree flows; these must also obey capacity constraints. An entering edge creates one cycle, and adjusting flow on that cycle preserves balance until a bound is hit and an edge leaves the tree.
Write flow balance using the positive-inflow convention
Remove the lower bounds on network flow by writing , where only is nonzero. Then , and its required flow balance is
In the order , the lower-bound contribution is , so
The resulting flow network edge capacities are
Add a new source with an edge of flow network edge capacity , and a new sink with edges and of flow network edge capacities and . A feasible flow saturating these new edges is equivalent to a solution for : ordinary flow conservation in the enlarged flow network produces exactly the residual supplies and demands above. All source and sink edges must be saturated, requiring flow value .
Figure 1.
Extended flow network after removing the lower bound; labels show final flow divided by flow network edge capacity
. The auxiliary edges are blue. The displayed flow saturates the auxiliary source and sink edges, certifying that all adjusted demands are met. The original edge regains its four-unit lower bound only after this auxiliary problem is solved. Details.
Start the Edmonds–Karp algorithm at zero flow. Repeated breadth-first search in the residual network permits the following shortest augmenting paths; when paths tie, choose the one through first.
StepAugmenting pathAdded flowTotal flow value
The first augmenting path has three edges. Once is saturated, the next shortest possibilities have four edges, so steps and respect the breadth-first search rule. Each augmentation adds the usual backward edges to the residual network, though these particular augmentations need only forward edges. Now is saturated, so no further augmenting path exists. The cut of a flow network with source side has cut capacity , proving that the obtained flow is a maximum flow.
The original-edge values for are in the order . Restore the lower bound to obtain
All original capacity constraints hold, and meets its lower bound. The net inflows at are respectively
The original network therefore admits a feasible circulation with vertex demands.
For any feasible circulation with vertex demands, sum its defining flow balance over all vertices:
Every directed edge contributes exactly once to the first sum, at its head , and exactly once to the second, at its tail . The two sums therefore contain exactly the same terms. They cancel, giving
This is global flow conservation: internal transport cannot create or destroy the total amount. Lower bounds on network flow and capacity constraints restrict which flows are feasible but do not affect the cancellation. The condition is necessary, not sufficient: insufficient flow network edge capacities can still prevent satisfying balanced demands.
For a directed graph, the uncapacitated minimum-cost flow problem is
Positive is external supply and negative is demand; summing the flow balances requires . There are no finite upper arc capacities. Let be the oriented incidence matrix with tail and head . For free dual potentials , the Lagrangian is
Its infimum over nonnegative flows is exactly when every network reduced cost is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes subject to these inequalities. For a primal feasible flow and dual feasible potentials,
This derives weak duality and the complementary slackness condition . A feasible pair satisfying it has equal objectives and certifies optimality.
A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances , and take . The shortest-path inequality proves dual feasibility, with tightness on the shortest-path tree.
For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This gives
The remaining arcs have zero flow. The total initial cost is . This is a basic feasible solution, though degenerate because the tree flow on is zero.
Normalize . Tree tightness gives
The non-tree reduced costs are
The negative reduced cost on identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending along increases the flows on by and decreases those on by ; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits to the minimum of the four decreasing flows, namely . Choose arc to leave among the tied limiting arcs.
After this one pivot the nonzero flows are
and every other arc flow is zero. The objective decreases by , giving cost .
For the new tree, tight potentials normalized at vertex 1 are
All tree reduced costs are zero. For the non-tree arcs they are , respectively, so the potentials are dual feasible. Their dual objective is
matching the primal cost. Complementary slackness therefore proves
This is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.
In a minimum-cost flow problem, a directed graph has arc flows , unit costs , lower and upper capacities , and net supplies summing to zero. The linear program minimizes subject to the flow balances and .
Give each graph vertex a network dual potential . With the outgoing-minus-incoming oriented incidence matrix , the optimization Lagrangian is
Minimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,
For every other feasible flow , these conditions give . This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.
Put . The four flow balances determine
Intersecting the four capacity intervals gives . In particular,
is a feasible flow. Write . Its cost along the feasible interval is
Hence is optimal precisely when . A network dual potential certificate is
The three interior arcs have zero network reduced costs and , which has the required nonnegative sign at its lower capacity.
For the network simplex algorithm, start with the network simplex tree basis consisting of arcs , and fix nonbasic arc at its lower bound 2. These are exactly the potentials just found. If , no improving pivot is needed. If , arc enters and its fundamental graph cycle increases all four flows by the same amount. At the remaining upper capacities are , so the simplex ratio test allows an increase of 2. Arc reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs , with potentials
Now only the nonbasic arc has a possibly nonzero network reduced cost, namely . It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer is
When , both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.
To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities are
There are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on and both give the identical flow at . Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only satisfy all capacities.
Label the vertices (left), (upper middle), (lower middle), (upper right), (lower right). Use the flow balance convention outgoing minus incoming equals supply. The printed initial flows, in the order , are
They obey all capacity constraints and the flow balances . The four strictly interior edges form a spanning tree. The remaining edges are at a bound: at zero, and at their upper bounds. Thus this is already a feasible network simplex tree basis; no artificial feasibility phase is needed. Its total cost is .
For a tree, choose network dual potentials with and zero network reduced cost on each tree edge. Initially
The nonbasic lower-bound edge has network reduced cost . Increase its flow and adjust around the graph cycle , reversing and . The available step is , so leaves at zero. This gives
The tree is now , and the potentials are .
Now is at its upper bound but has network reduced cost , so decreasing it improves cost. Its reverse residual network edge enters along the cycle . The forward edges increase; decrease. The step is
Thus leaves at its upper bound, and
The new tree has potentials .
The upper-bound edge now has network reduced cost . Enter its reverse direction along , decreasing and and increasing . The step is , so leaves at zero. The resulting flow is
The tree is , with potentials . The nonbasic edges have network reduced costs at its upper bound, at its lower bound, and at its lower bound. All have the correct signs, so there is no improving network simplex pivot. The next part proves these signs certify optimality.
Figure 1.
Optimal network flow of total cost 220, with zero-flow edges dashed
. Details.
For a minimum-cost flow with bounds , the capacitated flow optimality conditions consist of primal feasibility and network dual potentials whose network reduced costs obey
For a zero-capacity edge both bounds coincide and no sign restriction is needed; all capacities here are positive. These are the bound form of complementary slackness. To derive necessity directly, construct the residual network: a possible increase has original cost and a possible decrease has reverse cost . An optimal flow cannot admit a negative-cost directed cycle, since a positive step around it preserves flow balance and lowers cost. If there is no such cycle, connect a new source by zero-cost edges to every vertex and let be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge , . Taking makes every residual network reduced cost nonnegative, exactly the displayed sign conditions: both directions exist for an interior edge.
Conversely, for any other feasible flow , equal flow balances give
Each summand is nonnegative at a lower or upper bound, and zero at an interior edge. Hence the sign conditions suffice for optimality as well.
For the final flow, use in the order . All four tree edges have zero network reduced cost, while have costs . More explicitly, every feasible flow satisfies
Our flow attains equality. This gives a direct cost certificate of 220. The strict signs also force , at any optimum; flow balance then fixes all remaining edges, so this flow is unique.
On the dashed spanning tree, the nonzero flows are
with and all non-tree flows zero. The tree balances give supply four at vertex , demands one at and , and demand two at . Its cost is .
Choose and make the tree network reduced costs zero. The resulting network dual potentials are
For the non-tree edges, in the order , the network reduced costs are
Only has negative network reduced cost, so it enters the basis.
Adding this edge to the tree creates the graph cycle . Increasing its flow by adds on and subtracts on . These signed changes preserve every flow balance. The simplex ratio test allows , and the objective decreases by because the cycle's signed cost is .
Take and remove from the basis. The other tied edge remains a zero-flow basic edge; this is a legitimate degenerate tree basis and requires no extra pivot. The new flow is
Its cost is . For the new tree, choose
Every network reduced cost is nonnegative: the new non-tree costs for are . All positive-flow edges have zero network reduced cost, and the dual objective is . Thus complementary slackness gives
Figure 1.
Optimal network flow of cost 23, with vertex dual potentials
. Details.
Uncapacitated minimum-cost flow Created 2026-10-06 Updated 2026-10-14
An uncapacitated minimum-cost flow has nonnegative edge flows without finite upper capacities. The flow balances prescribe net supply at each vertex. For the oriented incidence matrix convention with tail and head , vertex network dual potentials have network reduced costs . Nonnegative network reduced costs and complementary slackness certify a feasible optimum. A feasible negative-cost directed cycle makes the problem unbounded below.