Accession Number:

ADA073795

Title:

A Simple Alternative to the Out-of-Kilter Algorithm.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s):

Report Date:

1979-05-31

Pagination or Media Count:

40.0

Abstract:

It is shown that any problem solvable by the Out-of-Kilter method may be simplified to an ordinary minimum cost flow problem meaning a problem with zero lower bounds. To perform the simplification, one considers the equivalent problem of optimally augmenting the original flows and then eliminates the lower bounds from this problem. In linear programming terms, as many as Abs. val A constraints are eliminated without adding new variables, where Abs. val. A is the number of arcs. The following procedure is suggested to replace the Out-of-Kilter method Transform to a minimum cost flow problem, eliminate negative cycles if any, then efficiently augment along a sequence of shortest paths.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE