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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1970
Accession Number
AD0726884

Entities

People

  • James K. Hartman
  • Leon S. Lasdon

Organizations

  • Case Western Reserve University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Additives (Chemicals)
  • Algorithms
  • Coefficients
  • Commodities
  • Computations
  • Equations
  • Iterations
  • Linear Programming
  • Operations Research
  • Schools
  • Security
  • Simplex Method
  • Specialization
  • Universities

Readers

  • Operations Research