THE DANTZIG-WOLFE DECOMPOSITION PRINCIPLE AND MINIMUM COST MULTICOMMODITY NETWORK FLOWS

Abstract

J. A. Tomlin published a paper on meeting required multicommodity network flows at minimum cost. He formulated this problem in both node-arc and arc-chain form. The node-arc linear program was attacked by the Dantzig-Wolfe decomposition principle by expressing the derived master program as convex combinations of the extreme points of the derived subprograms. In this note, it is shown that this problem is really a special case of the problem where one is attempting to meet minimum cost multicommodity flows without flow requirements on the individual commodities. Tomlin's algorithm is than modified to solve this more general problem. When this is done, the subprograms are homogeneous and the master program is a nonnegative combination of their independent solutions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1969
Accession Number
AD0693927

Entities

People

  • Richard D. Wollmer

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Coefficients
  • Commodities
  • Corporations
  • Decomposition
  • Elimination
  • Heuristic Methods
  • Linear Programming
  • Mathematics
  • Transportation

Readers

  • Operations Research