Research Reports from the Department of Operations
Document Type
Report
Publication Date
6-1-1970
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.
Keywords
Operations research, Linear programming, Algorithms, Mathematical optimization, Graph theory
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 193
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Hartman, James K. and Lasdon, Leon S., "A Generalized Upper Bounding Algorithm for Multicommodity Network Flow Problems" (1970). Research Reports from the Department of Operations. 225.
https://commons.case.edu/wsom-ops-reports/225