Theorem 6.11 (Circulation Feasibility Conditions). A circulation problem with nonnegative lower bounds on arc flows is feasible if and only if for every set Sof nodes
Theorem 6.12. The feasible flow problem stated in (6.2) has a feasible solution if and only if for every subset So, an algorithm to check feasibility works like this:
Can start with zero flow, look at infeasible arcs (xij < lij)
Increase xij to lij by finding an augmenting path from j to i.
Continue until
1. All xij lij
2. Can't find the augmenting path you need which implies the problem is infeasible because theorem 6.11 is violated.
