We provide a simplex algorithm for a structured class of uncapacitated countably-infinite network flow problems. Previous efforts required explicit capacities on arcs with uniformity properties that facilitate duality arguments. By contrast, this paper takes a ``primal'' approach by devising a simplex method that provably converges to optimal value using arguments based on convergence of spanning trees and nonnegativity of reduced costs. This allows for removal of explicit capacity bounds. The method also converges, on a subsequence, to an extremal optimal solution. Our method is tailored to our problem setting --- acyclic networks with nodes of only nonnegative supplies (or, alternatively, only demands). The necessary structure can be found in a variety of applied settings not amenable to existing methods including nonstationary infinite-horizon dynamic programming. A finite implementation of our simplex algorithm is provided for the infinite horizon dynamic lot sizing problem under linear costs.
Article
View A simplex method for uncapacitated pure-supply infinite network flow problems