Maximum flow problems under special nonnegative lower bounds on arc flows

Some special cases of the Maximum Flow Problem under nonnegative lower bounds on arc flows are investigated. Assuming that at least one of these bounds is strictly positive, a class of problems has been identified for which a single phase algorithm suffices to prove optimality. This situation contrasts with the two phases algorithm which is commonly used in the literature to solve these problems. In spite of having the same overall complexity of the two phases algorithm, the single phase one appears to be, computationally speaking, more attractive.