The equal flow problem (Q1108179)

The authors present a new algorithm for the solution of a network problem with equal side constraints. The solution technique is motivated by the desire to exploit the special structure of the side constraints and to maintain as much of the characteristics of pure network problems as possible. The algorithm uses the Lagrangean relaxation to obtain a lower bound and decomposition by right-hand-side allocation to obtain upper bounds. The Lagrangean dual serves not only to provide a lower bound to assist in termination criteria for the upper bound, but also allows an initial allocation of equal flows for the upper bound.