On the elimination of negative cost arcs in flow problems

The idea of eliminating negative cost arcs by setting flows at upper bounds appears in Shapiro [3] and Johnson [2]. We show that their procedure is the same as that obtained by transforming to a transportation problem, eliminating negative arcs by adding(mini dii) to each transportation cost dii, and then transforming back to a minimum cost flow problem. In [ 5 ] , the author showed that any flow problem with upper and lower bounds and a possibly infeasible starting solution could be transformed to an ordinary minimum cost flow problem with zero initial flow, zero lower bounds, and one violated s t constraint. This was accomplished by setting the flow in each arc at the feasible value closest to the initial value and then aggregating violated constraints to form an ordinary minimum cost flow problem. Negative cost arcs in the resulting ordinary problem can be eliminated [2] [3] by setting the flow in each negative cost arc at its upper bound (if one exists). We show that this method of eliminating negative cost arcs yields the same resultant network as the procedure TNT" , where T is Wagner's transformation to a transportation problem, andN changes transportation cost dii to dii mini {dii}.