Abstract
This paper reports on thedevelopment of a very efficient method for partitioning the networksimplex basis subtree in which dual values must be updated duringa pivot. The partitioning procedure may be concurrently executedby multiple processes. The resulting rapid decomposition of thesubtree allows an arbitrary number of processes to be utilized inthe actual dual update. This approach alleviates a primary limitationof the most efficient parallel network simplex implementationpublished to date. The new code performs at least as well as theprevious implementation on medium-scale problems and reduces averagesolution time by over 34% on large-scale problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, Applications, Prentice-Hall: Englewood Cliffs, NJ, 1993.
J. Aronson, "A survey of dynamic network flows," Annals of Operations Research, vol. 20. pp 1–66, 1989.
E. Balas, D. Miller, J. Pekny, and P Toth, "A parallel shortest path algorithm for the assignment problem," Management Science Report MSRR 552, Carnegie Mellon University, Pittsburgh, Pennsylvanau, 1989.
R.S. Barr, F. Glover, and D. Klingman, "Enhancements of spanning tree labeling procedures for network optimization," INFOR, vol. 17. pp 16–34, 1979.
R. Barr and B. Hickman, "Reporting computational experiments with parallel algorithms: Issues, measures, and experts' opinion," ORSA Journal on Computing, vol. 5. pp 2–18, 1993.
R. Barr and B. Hickman, "Parallel simplex for large pure network problems: Computational testing and sources of speedup," Operations Research, vol. 42, no. 1. pp 65–80, 1994.
D. Bertsekas, Linear Network Optimization, MIT Press: Cambridge, MA, 1991.
D. Bertsekas and D. Castanon, "Parallel asynchronous primal-dual methods for the minimum cost flow problem," LIDS Report P-1998, Massachusetts Institute of Technology, Cambridge, MA, 1990.
L. Ford and D. Fulkerson, "A primal-dual algorithm for the capacitated Hitchcock problem," Naval Research Logistics Quarterly, vol. 4. pp 47–54, 1957.
F. Glover, D. Klingman, and N. Phillips, "A modelling/solution approach for optimal deployment of a weapons arsenal," Annals of Operations Research, vol. 20. pp 159–177, 1989.
F. Glover, D. Klingman, and N. Phillips, Network Models in Optimization and their Application in Practice, John Wiley: New York, 1992.
B. Hickman, Parallel Algorithms for Pure Network Problems and Related Applications, unpublished dissertation, Southern Methodist University, Dallas, TX, 1991.
C. Hoare, "Monitors: An operating system structuring concept," Communications of the ACM, vol. 17, pp 549–557, 1974.
J. Kennington and R. Helgason, Algorithms for Network Programming, John Wiley: New York, 1980.
D. Klingman and J. Mote, "Computational analysis of large-scale pure networks," presented at the ORSA/TIMS Joint National Meeting, New Orleans, 1987.
D. Klingman, A. Napier, and J. Stutz, "NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost network flow problems," Management Science, vol. 20. pp 814–821, 1974.
X. Li and S. Zenios, "Data-level parallel solution of min-cost network flow problems using ε-relaxations," European Journal of Operational Research, vol. 79. pp 474–488, 1994.
D. Miller, J. Pekny, and G. Thompson, "Solution of large dense transportation problems using a parallel primal Algorithm," Operations Research Letters, vol. 9. pp 319–324, 1990.
J. Mulvey, "Pivot strategies for primal-simplex network codes," Journal of the ACM, vol. 25. pp 266–270, 1978.
K. Murty, Network Programming, Prentice-Hall: Englewood Cliffs, NJ, 1992.
S. Nielsen and S. Zenios, "Proximal minimizations with D-functions and the massively parallel solution of linear network programs," Report 91-06-05, Department of Decision Sciences, University of Pennsylvanau, Philadelphau, 1991.
S. Nielsen and S. Zenios, "Solving linear stochastic programs using massively parallel proximal algorithms," Report92-01-05, Department of Decision Sciences, University of Pennsylvanau, Philadelphau, 1992.
A. Osterhaug, Guide to Parallel Programming on Sequent Computer Systems, Prentice-Hall: Englewood Cliffs, NJ, 1992.
J. Peters, "The network simplex method on a multiprocessor," Networks, vol. 20. pp 845–859, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hickman, B.L., Scott, D. A Subtree-Partitioning Algorithm for Inducing Parallelism in Network Simplex Dual Updates. Computational Optimization and Applications 7, 183–197 (1997). https://doi.org/10.1023/A:1008647026576
Issue Date:
DOI: https://doi.org/10.1023/A:1008647026576