Thomas C. Sharkey, H. Edwin Romeijn
A simplex algorithm for minimum-cost network-flow problems in infinite networks
We study minimum-cost network-flow problems in networks with a countably infinite number of
nodes and arcs and integral flow data. This problem class contains many nonstationary planning
problems over time where no natural finite planning horizon exists. We use an intuitive natural
dual problem and show that weak and strong duality hold. Using recent results regarding the
structure of basic solutions to infinite-dimensional network-flow problems we extend the
well-known finite-dimensional network simplex method to the infinite-dimensional case. In
addition, we study a class of infinite network-flow problems whose flow balance constraints are
inequalities and show that the simplex method can be implemented in such a way that each pivot
takes only a finite amount of time.