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.