A Generalized Upper Bounding Algorithm for Multi-commodity Network Flow Problems
CASE WESTERN RESERVE UNIV CLEVELAND OH DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
An algorithm for solving min cost or max flow multicommodity flow problems is described. It is a specialization of the simplex method, which takes advantage of the special structure of the multicommodity problem. The only non- graph or non-additive operations in a cycle involve the inverse of a working basis, whose dimension is the number of currently saturated arcs. Efficient relations for updating this inverse are derived.
- Operations Research