network simplex method

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 … Read more