A route may have both a minimum commitment and a maximum capacity. A distribution contract might require at least two units on one route, while another route can carry at most three. These are constraints on the decision itself. Giving a route a favorable cost does not enforce its minimum, and giving it an expensive cost does not enforce its maximum.
The earlier allowed-route criterion treats a permitted route as able to carry the entire shipment. Here we retain finite capacities and add lower bounds. The main question remains elementary to state: can all node balances and all route commitments hold simultaneously? We will obtain either a feasible flow or an explicit group of nodes whose commitments are incompatible.
Motivation
Suppose a route from to must carry at least three units. It is tempting to put those three units on the route, reduce its capacity by three, and solve the remaining network unchanged. But the reserved shipment has already sent three units out of and into . Unless the prescribed balances account for it, the remaining flow must compensate for that change.
The useful transformation therefore changes two things together: each route's remaining capacity, and each node's remaining balance. Once this is done, the problem becomes an ordinary maximum-flow feasibility test. Its cuts then translate back into a precise statement about the original lower and upper bounds.
Definitions
Let be a finite directed graph without self-loops; separately labeled parallel or oppositely directed arcs are permitted. For each arc , specify finite real bounds . At each node , specify a real balance . Our convention is outflow minus inflow:
Thus means net supply and means net demand. Summing all node equations cancels every arc, so is necessary. We assume this equality below. A circulation is the special case at every node; it need not be the zero flow.
Definition 16.1.1
(Boundary notation and the remaining problem)
For , let be the arcs leaving and the arcs entering it. Internal arcs belong to neither boundary. Write , and use the same summation convention for bounds or flows on an arc set.
Set , , and
Then the original problem is equivalent to with net outflow . Also .
The equivalence is a substitution into every equation, in both directions: subtracting sends a feasible to a feasible ; adding sends a feasible back to a feasible . Lower bounds by themselves need not obey the node balances. The vector records exactly what they leave unfinished.
Theorem/proposition
Theorem 16.1.2
(Feasibility with lower and upper bounds)
Under the finite-graph, finite-bound and zero-total-balance assumptions above, a feasible exists if and only if, for every ,
Equivalently, every satisfies the two-sided boundary condition
If all are integers and these conditions hold, at least one feasible flow is integral.
Condition (1) says that the required net export from a group cannot exceed its maximum possible outward shipment minus its unavoidable inward shipment. It does not count internal commitments: those move material within the group. For a circulation it becomes : whatever must enter a group must be able to leave it.
The lower inequality in (2) follows by applying (1) to and using . Thus it is useful for interpretation, but does not require a second independent family of tests.
Proof sketch or proof idea
Proof
(Necessity by summation; sufficiency by an auxiliary maximum flow)
Necessity. Sum the balance equations over . Internal flows cancel, leaving
Sufficiency. Perform the lower-bound substitution. Add two new vertices . Keep each original arc with capacity and lower bound zero. Add an arc of capacity when , and an arc of capacity when . No new arc is needed when . Define
A flow of value saturates all arcs leaving and all arcs entering . Conservation at each old vertex then says that its original-arc net outflow is . Conversely any feasible extends to such a flow by saturating these added arcs. Their directions are important: a node needing positive remaining net export receives material from , which it then sends through the original graph.
Every – cut has source side for some . Its capacity is
But summing the definition of gives
Therefore (1) is exactly . Every cut in (3) has capacity at least .
Here is the existence argument behind the max-flow step, including real capacities. The auxiliary feasible-flow set is nonempty, closed and bounded, so a maximum-value flow exists. At a maximum there is no residual – path: augmenting by the positive minimum residual capacity on such a finite path would increase its value. Let be the residual-reachable set from . Since , it is a cut source side. Every auxiliary-graph arc leaving is saturated, and every auxiliary-graph arc entering carries zero flow; otherwise a residual arc would leave . This includes the added source and sink arcs. Summing conservation over proves that flow value equals cut capacity. The cut bound gives value at least , while total capacity out of is . Hence value is exactly , and adding gives the desired .
For integer data all auxiliary capacities are nonnegative integers. Start with zero auxiliary flow and augment along residual paths. Every positive bottleneck is an integer, so every flow stays integral and its value rises by at least one. After at most augmentations there is no further path, or value has already been reached. The residual-cut argument shows that under (1) the stopping value must be . The recovered is integral. This bound measures capacity units; it is not a polynomial bound in the binary input length. For arbitrary real data the compactness argument proves existence but does not assert finite termination of an arbitrary augmenting-path rule.
Proof X-ray
Three different obligations in one reduction
Subtracting lower bounds is an exact algebraic equivalence, not an appeal to a flow theorem. The cut calculation then shows that every possible obstruction in the auxiliary graph has an interpretation in the original graph. Maximum-flow existence turns the absence of such an obstruction into feasibility. Integrality needs its own argument about integer bottlenecks; it does not follow merely from the real-data existence proof.
If the maximum auxiliary value is , its residual cut yields a set with
This is a numerical infeasibility certificate: the group's required net export exceeds its permitted maximum by that amount. Increasing one route capacity by this amount removes this particular obstruction only if that route leaves the group; other cuts must still be respected. A displayed repaired flow gives a stronger conclusion than removing one failed inequality.
Worked examples
Worked example 16.1.3
(Reserve commitments, then solve the remaining balances)
Take vertices , balances , and the following labeled arcs:
| Arc | Lower bound | Upper bound | Remaining capacity |
|---|---|---|---|
| 2 | 4 | 2 | |
| 1 | 4 | 3 | |
| 0 | 2 | 2 | |
| 0 | 1 | 1 |
The lower-bound shipment has net outflows , so , not the original balance vector. Thus . Add and with capacity one each, and with capacity two. Send one unit along and one along .
On the original arcs this gives in table order, hence . Node has net outflow ; node has ; node has . Every route bound holds. The two units required on are already present even though that arc received no remaining flow.
At this , the backward residual capacity for is , not two. Canceling any positive amount would violate its mandatory shipment. The backward capacity for is .
Worked example 16.1.4
(Mandatory inflow can make a circulation impossible)
Let the only arcs be with bounds and with bounds , and require zero balance at both nodes. Each interval is individually nonempty, but has mandatory inflow three and possible outflow at most two. Condition (1) reads , which is false.
The lower-bound net outflows are , so and . The auxiliary graph has and , each of capacity three. Only two units can travel from to . The cut with source side has capacity two, and (4) reports shortage one. Raising the upper bound on to three permits , which directly certifies the repair.
Worked example 16.1.5
(Transportation quotas and a complete cost calculation)
Two origins have supplies ; two destinations have demands . All four routes exist. Their lower bounds, upper bounds and unit costs are
Subtracting leaves origin supplies and destination demands ; the remaining route capacities are . The remaining shipment obeys these bounds and balances. Adding back gives .
To prove that this is also minimum cost, solve the four balance equations. With every balanced plan has
The four route intervals reduce to . Its cost is , minimized at with value . Equivalently, the reserved lower-bound shipment costs and the optimal remaining shipment costs . Omitting the constant eight would preserve the minimizing decision but report the wrong original objective value. Feasibility alone would not prove the cost claim; the one-parameter argument does.
Proposition 16.1.6
(Capacitated transportation criterion)
Let be finite origin and destination sets, with nonnegative supplies and demands , balanced totals , and finite bounds on allowed routes. Put origin balance and destination balance on the route graph. Applying (1) to a set containing origins and destinations gives the exact feasibility criterion
Proof
(Reading the boundary of an origin–destination group)
Every vertex set of the route graph has the form with and , and the balances sum to , so the feasibility theorem applies. The balance of is . Every route runs from an origin to a destination, so a route leaves exactly when it runs from to , and enters exactly when it runs from to . Condition (1) for therefore reads
which rearranges to (5). Since (5) for all is (1) for all , it is necessary and sufficient.
Here, for example, sums upper bounds of allowed routes with those endpoints; a forbidden route is absent, or equivalently has both bounds zero. This formula includes the destinations inside the group and the route capacities across its boundary. Neighbor sets alone no longer contain enough information.
Concept lensCombinatorial
From a neighbor obstruction to a capacity obstruction
With zero lower bounds and capacity , the total shipment, on every allowed route, choose in (5). No route leaves for , and we recover . Any gives a weaker inequality because . For every other , at least one allowed route crosses from to ; its capacity makes (5) automatic, since and . Thus the earlier neighbor criterion is recovered. Finite route capacities and mandatory incoming shipments are precisely the information that its simpler formula suppresses.
Common mistakes
Counterexample mode
Every neighbor test can pass while capacities fail
Let supplies and demands both be , with all four routes allowed and all lower bounds zero. Give each route into destination one capacity , and each route into destination two capacity two. Every nonempty origin group has both destinations as neighbors, so every uncapacitated neighbor inequality holds. Yet destination one can receive at most one unit, below its demand two.
In (5), take and . The inequality would require . In the graph criterion the group has required net export two but outward capacity one. The obstruction is capacity, not absence of a route.
Common mistake
(Residual arcs that cancel mandatory flow)
In a lower-bounded residual graph, the forward capacity is and the backward capacity is . A backward arc removes only flow above the minimum commitment. Opposite original arcs remain separately labeled; a backward residual arc is not permission to overwrite the other original arc.
Common mistake
(Overreading the integrality and certificate statements)
An integral feasible flow exists under integral data, but fractional feasible flows can coexist with it. Likewise, a small unsatisfied balance from a numerical algorithm is not an exact infeasibility certificate. The cut and its arithmetic must actually violate (1). Infinite bounds require a separate justified finite replacement or a different existence argument; the compactness proof here uses finite bounds explicitly.
Summary
Subtract route lower bounds and subtract their net outflows from the required balances. Solve the resulting zero-lower-bound problem by saturating the auxiliary source arcs. Every failed saturation has a cut certificate . For integer data, integer augmentation provides an integral feasible representative. These are feasibility conclusions; a cost objective still needs an optimality argument.
Exercises
Quick check
(There are two arcs with bounds and with bounds . Required balances are . Compute , describe every feasible flow using one parameter, and calculate both residual capacities for each arc at .)
Solution · Answer
The lower-bound net outflows are , already equal to the required balances, so and the auxiliary problem needs no source or sink arcs. Write . Balance requires , and both bounds give exactly . At the forward and backward residual capacities on are and ; on they are and .
Quick check
(For the three-node network in the first worked example, a proposed transformation keeps balance after subtracting lower bounds. Explain why adding the lower bounds back to a feasible solution of that incorrect remaining problem would fail. State the correct auxiliary arcs and exhibit a saturating flow.)
Solution · Answer
The lower-bound net outflows are . Adding them to the incorrect remaining balances would yield , rather than . The correct remaining balances are . Add and with capacity one, and with capacity two. Sending one unit on each of and saturates them and recovers original flows .
Quick check
(A zero-balance network has only with bounds , with , and with . Give a violated cut inequality, compute the auxiliary maximum value, and exhibit a repair by changing only the upper bound on as little as possible.)
Solution · Answer
For , the right-hand side of (1) is , below . The lower-bound net outflows are , so and . In the auxiliary graph all – paths must use , whose remaining capacity is two. Sending two units on attains that bound, so maximum value is two. Increasing the upper bound on to three is necessary by the violated cut, and sufficient because the original circulation then obeys every bound. An increase of one is therefore minimal.
Quick check
(In the transportation cost example, increase only the lower bound on route from one to two. Determine all feasible plans and the minimum cost. Explain why imposing the quota by changing its cost instead would not be an equivalent model.)
Solution · Answer
Every balanced plan is still . The new quota requires , while the original upper bounds require . Thus the unique plan is and costs . A finite favorable cost can encourage a route but does not remove feasible plans with ; changing an objective is not the same as imposing a constraint.
Quick check
(Two separately labeled parallel arcs lead from to , each with bounds , and balances are . Give an integral feasible flow and a fractional feasible flow. Which integrality assertion does the theorem establish? If the second arc's lower bound becomes , is the integer-data conclusion applicable, and does an integral feasible flow still exist in this particular example?)
Solution · Answer
The arc-flow vectors and are respectively integral and fractional feasible flows. The theorem establishes existence of an integral representative, not integrality of every feasible point. After the second lower bound becomes , not all data are integers, so that sufficient hypothesis is unavailable. Nevertheless is an integral feasible flow here. Failure of a theorem's sufficient hypothesis is not a proof that its conclusion fails.