A Simple Alternative to the Out-of-Kilter Algorithm.
STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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.
- Theoretical Mathematics