A Generalized Upper Bounding Algorithm for Multicommodity Network Flow Problems

Authors

James K. Hartman
Leon S. Lasdon

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