The Equal Flow Problem.
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Pagination or Media Count:
This paper presents a new algorithm to solve a network problem with equal flow wide constraints. The proposed 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. Our solution technique for the equal flow problem consists of solving two sequences of pure network problems. One sequence yields tighter lower bounds on the optimal value by considering the Lagrangean relaxation of the equal flow problem in which the side constraints are dualized. The second sequence yields upper bounds on the optimal value for the problem and maintains a feasible solution at all times. This sequence is obtained by considering a reformulation of the equal flow problem based on parametric changes in the requirements vector. The procedure has the added attractive feature that it provides a feasible solution which is known to be within a percentage of the optimal at all times. As such, the algorithm terminates when a solution with a prespecified tolerance on the objective function value is obtained. On NETGEN problems, using the first 150 arcs to form 75 equal flow side constraints, we found that the new algorithm is approximately 3 times faster than existing techniques and requires only 50 of the storage.
- Operations Research