= Lower bounds on network flow
{title2=$\ell_e\leq f_e\leq c_e$}
A prescribed minimum amount on each directed <edge> can be removed by substituting $f_e=\ell_e+x_e$. The new <capacity constraints> are $0\leq x_e\leq c_e-\ell_e$. For a <circulation with vertex demands> using net inflow $d_v$, the adjusted demand is $d'_v=d_v-(\sum_u\ell_{uv}-\sum_w\ell_{vw})$. Solving the adjusted problem and adding $\ell$ back gives a one-to-one correspondence of <feasible solutions>. In particular, removing a lower bound on $u\to v$ increases $u$'s residual demand and decreases $v$'s by that amount.
Back to article page
