An Efficient Procedure for Implementing a Dual Simplex Network Flow Algorithm
- 1 March 1977
- journal article
- research article
- Published by Taylor & Francis in A I I E Transactions
- Vol. 9 (1) , 63-68
- https://doi.org/10.1080/05695557708975122
Abstract
This paper shows that for linear programming formulations of network flow problems, the nonzero components of rows of the basis inverse are identical. A simple algorithm for identifying these nonzero components is given along with a suggested data structure for implementation. The algorithm requires only one bit of storage for each node plus one additional bit. Finally we indicate how these ideas may be used in the development of a dual simplex code for network flow problems.Keywords
This publication has 8 references indexed in Scilit:
- A New Branch-and-Bound Algorithm for the Fixed-Charge Transportation ProblemManagement Science, 1976
- Real World Applications of Network Related Problems and Breakthroughs in Solving Them EfficientlyACM Transactions on Mathematical Software, 1975
- Efficient computational devices for the capacitated transportation problemNaval Research Logistics Quarterly, 1974
- A Computation Study on Start Procedures, Basis Change Criteria, and Solution Algorithms for Transportation ProblemsManagement Science, 1974
- Implementation and computational comparisons of primal, dual and primal‐dual computer codes for minimum cost network flow problemsNetworks, 1974
- Benefit-Cost Analysis of Coding Techniques for the Primal Transportation AlgorithmJournal of the ACM, 1973
- Networks and Basic SolutionsOperations Research, 1966
- PROGRAMMING IN NETWORKS AND GRAPHSPublished by Defense Technical Information Center (DTIC) ,1965