Premium
A simplex algorithm for minimum‐cost network‐flow problems in infinite networks
Author(s) -
Sharkey Thomas C.,
Romeijn H.Edwin
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20221
Subject(s) - minimum cost flow problem , simplex , flow network , flow (mathematics) , duality (order theory) , mathematical optimization , class (philosophy) , simplex algorithm , computer science , countable set , maximum flow problem , dual (grammatical number) , mathematics , finite set , multi commodity flow problem , linear programming , algorithm , discrete mathematics , combinatorics , artificial intelligence , art , mathematical analysis , geometry , literature
Abstract 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. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008