Accession Number:

AD0726884

Title:

A Generalized Upper Bounding Algorithm for Multi-commodity Network Flow Problems

Descriptive Note:

Technical memo.

Corporate Author:

CASE WESTERN RESERVE UNIV CLEVELAND OH DEPT OF OPERATIONS RESEARCH

Personal Author(s):

Report Date:

1970-06-01

Pagination or Media Count:

41.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE