Paper Info
Title
A simplex algorithm for minimum-cost network-flow problems in infinite networks
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
Year
DOI
Venue
2008
10.1002/net.v52:1
Networks
Keywords
Field
DocType
network flow,simplex algorithm,duality
Flow network,Infinite-dimensional optimization,Combinatorics,Mathematical optimization,Network simplex algorithm,Simplex algorithm,Time horizon,Countable set,Duality (optimization),Strong duality,Mathematics
Journal
Volume
Issue
ISSN
52
1
0028-3045
Citations 
PageRank 
References 
9
0.63
11
Authors
2
Name
Order
Citations
PageRank
Thomas C. Sharkey110111.80
H. Edwin Romeijn276983.88