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

摘要

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.