DC6 - Lower capacity constraints

DC6 - Lower capacity constraints

Some routes must carry a minimum flow as well as staying below an upper limit. DC6 combines these bounds with conservation, adjusts flows without cancelling too much, and proves a maximum using the correct cut bound. Compulsory flow back across a cut can reduce the greatest possible net delivery.

Feasible flows with upper and lower bounds

Could raising a pipe's minimum required flow from 2 to 3 litres per second make the network deliver less overall, even though every upper capacity stays unchanged? It can, if that compulsory flow must go back across a bottleneck. First we need to recognise a feasible starting flow when zero is no longer allowed on every arc.

An arc labelled (3,8)(3,8) may mean lower capacity 3 and upper capacity 8, rather than actual flow 3 out of capacity 8. Always read the key supplied with the network.

Lower and upper capacities

An arc with lower capacity ℓ\ell and upper capacity uu must carry an actual flow satisfying ℓ≤f≤u\ell\le f\le u, where 0≤ℓ≤u0\le\ell\le u. A feasible network flow meets every such bound and conserves flow at every intermediate node.

A zero flow is infeasible if any lower bound is positive. Assigning every arc its lower bound need not work either: different lower bounds can leave a junction unbalanced. Choose flows together, using conservation to link them. In a small network, identify the tightly constrained arcs, write the junction equations, and check all bounds after filling in the remaining flows.

Worked example 1: finding a feasible starting flow

Question. The only arcs and their bounds are 0≤fSA≤70\le f_{SA}\le7, 0≤fSB≤50\le f_{SB}\le5, 2≤fAB≤32\le f_{AB}\le3, 1≤fAT≤41\le f_{AT}\le4, 3≤fBT≤83\le f_{BT}\le8. Find one feasible starting flow and its value.

Plan. Start with the three positive lower requirements, then use conservation to determine the two source flows and check their bounds.

fAB=2,fAT=1,fBT=3try their lower boundsfSA=fAB+fAT=3conservation at AfSB=fBT−fAB=1conservation at Bv=3+1=4source outflow\begin{aligned} f_{AB}&=2,\quad f_{AT}=1,\quad f_{BT}=3 && \text{try their lower bounds}\\ f_{SA}&=f_{AB}+f_{AT}=3 && \text{conservation at }A\\ f_{SB}&=f_{BT}-f_{AB}=1 && \text{conservation at }B\\ v&=3+1=4 && \text{source outflow} \end{aligned}

Answer. One feasible flow is SA=3,SB=1,AB=2,AT=1,BT=3SA=3,SB=1,AB=2,AT=1,BT=3, with value 4.

Check. The source flows 3 and 1 lie in [0,7][0,7] and [0,5][0,5]; the remaining flows meet their stated lower bounds. The sink receives 1+3=41+3=4, agreeing with source outflow. Assigning the two source arcs their lower bounds zero would not conserve flow.

Trying lower bounds on selected arcs is a starting choice, not a guarantee. If the completed flows failed a bound, you would need to adjust that choice or prove that no choice works. Now change only the upper bound on SASA, from 7 to 2.

Worked example 2: detecting incompatible requirements

Question. Use the same network and bounds as in Worked example 1, except that SASA now has upper capacity 2. Determine whether a feasible flow exists.

Plan. Find the smallest possible outflow at AA and compare it with the largest possible inflow.

fSA=fAB+fATconservation at AfSA≥2+1=3compulsory outflowsfSA≤2changed upper bound\begin{aligned} f_{SA}&=f_{AB}+f_{AT} && \text{conservation at }A\\ f_{SA}&\ge2+1=3 && \text{compulsory outflows}\\ f_{SA}&\le2 && \text{changed upper bound} \end{aligned}

Answer. No feasible flow exists: SASA would have to carry at least 3 and at most 2.

Check. Increasing ABAB or ATAT above their lower bounds would require even more inflow at AA, so changing the initial allocation cannot repair the contradiction.

In a larger network, feasibility may require redistribution between routes. A proposed maximum is meaningless until a feasible flow is established.

Watch out

Wrong: “Every lower bound is below its upper bound, so the network is feasible.” Correct: the bounds must also permit conservation at all intermediate nodes. Valid individual intervals can be incompatible together.

Construct one starting allocation for a new complete network.

Residual adjustments within both bounds

The reverse residual capacity is now the amount you may cancel before reaching the lower bound, rather than the whole existing flow. This is the only change to the local residual rule, but it can change the final maximum.

For example, an arc currently carrying 7 with bounds 3 and 10 can gain at most 3 or lose at most 4. It cannot lose all 7, because at least 3 must remain.

Residual capacities with a lower bound

For an original arc A→BA\to B, with bounds ℓ≤f≤u\ell\le f\le u,

rA→B=u−fforward increase availablerB→A=f−ℓreverse cancellation available\begin{aligned} r_{A\to B}&=u-f && \text{forward increase available}\\ r_{B\to A}&=f-\ell && \text{reverse cancellation available} \end{aligned}

On a residual source-to-sink path, augment by the minimum residual capacity. Increase original flows on forward steps and decrease them on reverse steps. Starting from a feasible flow, these adjustments preserve conservation and both bounds.

Not in the formula booklet: learn it.

Begin with the given feasible flow rather than resetting to zero. After each augmentation recalculate both residual directions, because reaching a lower bound blocks further cancellation.

Worked example 3: cancellation stops at the lower bound

Question. The only original arcs are SA,SB,AB,AT,BTSA,SB,AB,AT,BT, each with upper capacity 4. Lower bounds are zero except ABAB, whose lower bound is 2. A feasible starting flow has SA=AB=BT=4SA=AB=BT=4, SB=AT=0SB=AT=0. Augment as far as possible along the residual path S→B→A→TS\to B\to A\to T.

Plan. Compare unused capacities on SB,ATSB,AT with the cancellable amount on ABAB.

rS→B=4−0=4rB→A=4−2=2leave the lower bound on ABrA→T=4−0=4δ=min⁡(4,2,4)=2fSB=fAT=2,fAB=4−2=2v=4+2=6\begin{aligned} r_{S\to B}&=4-0=4\\ r_{B\to A}&=4-2=2 && \text{leave the lower bound on }AB\\ r_{A\to T}&=4-0=4\\ \delta&=\min(4,2,4)=2\\ f_{SB}=f_{AT}&=2,\qquad f_{AB}=4-2=2\\ v&=4+2=6 \end{aligned}

Answer. Augment by 2. The new value is 6; ABAB must still carry 2.

Check. SASA and BTBT remain 4. At AA, 4=2+24=2+2; at BB, 2+2=42+2=4. All flows meet both bounds, and the reverse residual capacity of ABAB is now 2−2=02-2=0.

Change only the lower bound on ABAB, from 2 to 1. The same initial flow is feasible, but more can now be cancelled.

Worked example 4: relaxing one compulsory flow

Question. Use the same capacities and starting flow as in Worked example 3, but let the lower bound on ABAB be 1. Augment along S→B→A→TS\to B\to A\to T.

Plan. Recalculate the changed reverse capacity before taking the path bottleneck.

rB→A=4−1=3new cancellable amountδ=min⁡(4,3,4)=3fSB=fAT=3,fAB=4−3=1v=4+3=7\begin{aligned} r_{B\to A}&=4-1=3 && \text{new cancellable amount}\\ \delta&=\min(4,3,4)=3\\ f_{SB}=f_{AT}&=3,\qquad f_{AB}=4-3=1\\ v&=4+3=7 \end{aligned}

Answer. The augmentation is 3 and the new value is 7.

Check. The sink receives AT+BT=3+4=7AT+BT=3+4=7. At AA, 4=1+34=1+3; at BB, 3+1=43+1=4. The compulsory flow 1 remains on ABAB, so the lower bound has been respected.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account