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.