×

A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem. (English) Zbl 0858.90127

Summary: The purpose of this study is to describe a data parallel primal-dual augmenting path algorithm for the dense linear many-to-one assignment problem also known as semi-assignment. This problem could for instance be described as assigning \(n\) persons to \(m(\leq n)\) job groups.
The algorithm is tailored specifically for massive SIMD parallelism and employs, in this context, a new efficient breadth-first-search augmenting path technique which is found to be faster than the shortest augmenting path search normally used in sequential algorithms for this problem. We show that the best known sequential computational complexity of \(O(mn^2)\) for dense problems, is reduced to the parallel complexity of \(O(mn)\), on a machine with \(n\) processors supporting reductions in \(O(1)\) time. The algorithm is easy to implement efficiently on commercially available massively parallel computers. A range of numerical experiments are performed on a Connection Machine CM200 and a MasPar MP-2. The tests show the good performance of the proposed algorithm.

MSC:

90C35 Programming involving graphs or networks
65Y05 Parallel numerical computation
90B80 Discrete location and assignment
90C60 Abstract computational complexity for mathematical programming problems

Software:

MPL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In AFIPS Conference proceedings, Washington D.C., 1967, Thompson Books.
[2] E. Balas, D. Miller, J. Pekny, and P. Toth. A parallel shortest path algorithm for the assignment problem. J. Assoc. Comput. Mach., 38:985–1004, 1991. · Zbl 0799.68111 · doi:10.1145/115234.115349
[3] R. Barr, F. Glover, and D. Klingman. The alternating basis algorithm for the assignment problem. Math. Programming, 13:1–13, 1977. · Zbl 0378.90097 · doi:10.1007/BF01584319
[4] R. Barr, F. Glover, and D. Klingman. A new alternating basis algorithm for semi-assignment networks. In W. White, editor, Computers and Mathematical Programming, pages 223–232. National Bureau of Standards Special Publication, U.S. Government Printing Office, Washington D.C., 1978. · Zbl 0429.90075
[5] D. P. Bertsekas. The auction algorithm: A distributed relaxation method for the assignment problem. Ann. Oper. Res., 14:105–123, 1988. · Zbl 0788.90055 · doi:10.1007/BF02186476
[6] D. P. Bertsekas. The auction algorithm for assignment and other network flow problems: A tutorial. Interfaces, 20:133–149, 1990. · doi:10.1287/inte.20.4.133
[7] D. P. Bertsekas and D. A. Castañon. The auction algorithm for the transportation problem. Ann. Oper. Res., 20:67–96, 1989. · Zbl 0705.90061 · doi:10.1007/BF02216923
[8] D. P. Bertsekas and D. A. Castañon. Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput., 17:707–732, 1991. · Zbl 0737.68036 · doi:10.1016/S0167-8191(05)80062-6
[9] D. P. Bertsekas and D. A. Castañon. Parallel asynchronous Hungarian methods for the assignment problem. ORSA J. Comput., 5:261–274, 1993. · Zbl 0789.90060 · doi:10.1287/ijoc.5.3.261
[10] G. Carpaneto, S. Martello, and P. Toth. Algorithms and codes for the assignment problem. Ann. Oper. Res., 13:193–223, 1988.
[11] D. A. Castañon. Development of advanced WTA algorithms for parallel processing. Final Report TR-457, ALPHATECH, Inc., 111 Middlesex Turnpike, Burlington, MA 01803, 1989.
[12] D. A. Castañon, B. Smith, and A. Wilson. Performance of parallel assignments algorithms on different multiprocessor architectures. Technical Report TP-1245, ALPHATECH, Inc., 111 Middlesex Turnpike, Burlington, MA 01803, 1989.
[13] P. Christy. Software to support massively parallel computing on the MasPar MP-1. In Proceedings of IEEE Compcon Spring 1990. IEEE, February 1990.
[14] W. Cunningham. A network simplex method. Math. Programming, 11:105–116, 1976. · Zbl 0352.90039 · doi:10.1007/BF01580379
[15] O. Damberg and A. Migdalas. A data parallel space dilation algorithm for the concentrator location problem. In P. M. Pardalos et. al., editors, Parallel Processing of Discrete Optimization Problems, volume 22 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 57–80. AMS, 1995.
[16] O. Damberg, S. Storøy, and T. Sørevik. A data parallel primal-dual algorithm for the dense linear many-to-one assignment problem. Report LiTH-MAT-R-1994–15. Department of Mathematics, Linköping Institute of Technology, S-581 83 Linköping, Sweden, 1994. · Zbl 0858.90127
[17] A. Gupta and V. Kumar. Performance properties of large scale parallel systems. J. Parallel Distrib. Systems, 19:234–244, 1993. · doi:10.1006/jpdc.1993.1107
[18] John L. Gustafson. Reevaluating Amdahl’s law. Comm. ACM, 31:532–533, 1986. · doi:10.1145/42411.42415
[19] R. Jonker and A. Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 38:325–340, 1987. · Zbl 0607.90056 · doi:10.1007/BF02278710
[20] D. N. Kempa, J. L. Kennington, and H. A. Zaki. Performance characteristics of the Jacobi and the Gauss-Seidel versions of the auction algorithm on the Alliant FX/8. ORSA J. Comput., 3:92–106, 1991. · Zbl 0808.90096 · doi:10.1287/ijoc.3.2.92
[21] J. Kennington and Z. Wang. A shortest augmenting path algorithm for the semi-assignment problem. Oper. Res., 40:178–187, 1992. · Zbl 0751.90050 · doi:10.1287/opre.40.1.178
[22] J. L. Kennington and Z. Wang. An empirical analysis of the dense assignment problem: Sequential and parallel implementations. ORSA J. Comput., 3: 299–306, 1991. · Zbl 0775.90286 · doi:10.1287/ijoc.3.4.299
[23] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976. · Zbl 0413.90040
[24] MasPar Computer Corporation, Sunnyvale, CA. MasPar Parallel Application Language (MPL). Reference Manual. Software Version 3.2, May 1993.
[25] D. L. Miller, J. F. Pekny, and G. L. Thompson. Solution of large dense transportation problems using a parallel primal algorithm. Oper. Res. Lett., 9:319–324, 1990. · Zbl 0711.90054 · doi:10.1016/0167-6377(90)90026-2
[26] C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982. · Zbl 0503.90060
[27] L. Prechelt. Measurement of MasPar MP-1216A communication operations. Technical Report 01/93, Institut für Programmstrukturen und Datenorganisation, Fakultät für Informatik, Universität Karlsruhe, 1993.
[28] R. T. Rockafellar. Network flows and monotropic optimization. John Wiley & Sons, New York, 1984. · Zbl 0596.90055
[29] T. Sørevik. Average case complexity analysis of algorithms for the linear assignment problem. In Proceedings of NOAS ’93, NTH, Trondheim, Norway, 1993.
[30] S. Storøy and T. Sørevik. An SIMD, fine-grained, parallel algorithm for the dense linear assignment problem. Report 72, Department of Informatics, University of Bergen, Bergen, Norway, 1992.
[31] S. Storøy and T. Sørevik. Massively parallel augmenting path algorithms for the assignment problem. Report, Department of Informatics, University of Bergen, Bergen, Norway, 1994. · Zbl 0881.90090
[32] Thinking Machines Corporation. CM Fortran Language Reference Manual. Version 2.1. Cambridge, MA, January 1994.
[33] Z. Wang. The Shortest Augmenting Path Algorithm for Bipartite Network Problems. PhD thesis, Southern Methodist University, Dallas, TX, 1990.
[34] J. M. Wein and S. A. Zenios. On the massively parallel solution of the assignment problem. J. Parallel Distrib. Comput., 13:228–236, 1991. · doi:10.1016/0743-7315(91)90092-N
[35] S. A. Zenios. Data parallel computing for network-structured optimization problems. Comput. Optim. Appl., 3:199–242, 1994. · Zbl 0803.90122 · doi:10.1007/BF01299446
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.