×

The auction algorithm: A distributed relaxation method for the assignment problem. (English) Zbl 0788.90055

Summary: We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi-like relaxation method for solving a dual problem. Its (sequential) worst-case complexity, for a particular implementation that uses scaling, is \(O(N\;A\;\log(NC))\), where \(N\) is the number of persons, \(A\) is the number of pairs of persons and objects that can be assigned to each other, and \(C\) is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.

MSC:

90C10 Integer programming
65Y05 Parallel numerical computation
65K99 Numerical methods for mathematical programming, optimization and variational techniques
68Q25 Analysis of algorithms and problem complexity
91B26 Auctions, bargaining, bidding and selling, and other market models

Software:

RELAX4; NETGEN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Ahuja andJ.B. Orlin, ”An Improved Algorithm for Computing the Min Cycle Mean”, Unpublished Manuscript, Nov. 1987.
[2] M.L. Balinski, Signature methods for the assignment problem,Oper. Res. 33 (1985) 527–537. · Zbl 0583.90064 · doi:10.1287/opre.33.3.527
[3] M.L. Balinski, A competitive (dual) simplex method for the assignment problem,Math. Progr. 34 (1986) 125–141. · Zbl 0596.90064 · doi:10.1007/BF01580579
[4] R. Barr, F. Glover andD. Klingman, The alternating basis algorithm for assignment problems,Math. progr. 13 (1977) 1–13. · Zbl 0378.90097 · doi:10.1007/BF01584319
[5] G.M. Baudet, Asynchronous iterative methods for multiprocessors,J. ACM 15 (1978) 226–244. · Zbl 0372.68015 · doi:10.1145/322063.322067
[6] D.P. Bertsekas, A distributed algorithm for the assignment problem,Laboratory for Information and Decision Systems Working Paper (M.I.T., March 1979).
[7] D.P. Bertsekas, A new algorithm for the assignment problem,Math. Progr. 21 (1981) 152–171. · Zbl 0461.90069 · doi:10.1007/BF01584237
[8] D.P. Bertsekas, A Distributed Asynchronous Relaxation Algorithm for the Assignment Problem,Proc. 24th IEEE Conf. Decision and Control (Ft Lauderdale, Fla., Dec. 1985) pp. 1703–1704.
[9] D.P. Bertsekas, A unified framework for primal-dual methods in minimum cost network flow problems,Math. Progr. 32 (1985) 125–145. · Zbl 0567.90023 · doi:10.1007/BF01586087
[10] D.P. Bertsekas, Distributed asynchronous computation of fixed points,Math. Progr. 27 (1983) 107–120. · Zbl 0521.90089 · doi:10.1007/BF02591967
[11] D.P. Bertsekas,Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems, LIDS Report P-1606 (M.I.T., Sept. 1986, revised Nov. 1986).
[12] D.P. Bertsekas, Distributed relaxation methods for linear network flow problems, in:Proc. 25th IEEE Conf. Decision and Control, Athens, Greece (1986) pp. 2101–2106.
[13] D.P. Bertsekas andD. Castanon, The Auction Algorithm for Transportation Problems, unpublished manuscript (Nov. 1987).
[14] D.P. Bertsekas andJ. Eckstein, Distributed asynchronous relaxation methods for linear network flows problems,Proc. IFAC ’87, Munich, Germany (July 1987).
[15] D.P. Bertsekas andD. El Baz, Distributed asynchronous relaxation methods for convex network flow problems,SIAM J. Control Optim. 25 (1987) 74–85. · Zbl 0624.90028 · doi:10.1137/0325006
[16] D.P. Bertsekas andP. Tseng, Relaxation methods for minimum cost ordinary and generalized network flow problems, LIDS Report P-1462, M.I.T., May 1985,Oper. Res. to appear. · Zbl 0662.90027
[17] D.P. Bertsekas andP. Tseng, RELAX: A Code for Linear Network Flow Problems, inFORTRAN Codes for Network Optimization, (B. Simeone, ed.), Vol to be published by theAnnals of Operations Research.
[18] D.P. Bertsekas, P.A. Hosein andP. Tseng, Relaxation methods for network flow problems,SIAM J. Control Optim. 25 (1987) 1219–1243. · Zbl 0641.90036 · doi:10.1137/0325067
[19] D.P. Bertsekas, andJ.N. Tsitsiklis,Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Englewood Cliffs, N.J., 1988) to appear. · Zbl 0743.65107
[20] D.P. Bertsekas, J.N. Tsitsiklis andM. Athans,Convergence Theories of Distributed Asynchronous Computation: A Survey, LIDS Report P-1412, M.I.T., Oct. 1984; also in:Stochastic programming, eds.F. Archetti, G. Di Pillo, andM. Lucertini, (Springer-Verlag, N.Y., 1986) pp. 107–120.
[21] R.G. Bland andD.L. Jensen,On the Computational Behaviour of a Polynomial-Time Network Flow Algorithm, Tech. Report 661 (School of Operations Research and Industrial Engineering, Cornell University, June 1985).
[22] D. Chazan andW. Miranker, Chaotic relaxation,Linear Algebra Appl. 2 (1969) 199–222. · Zbl 0225.65043 · doi:10.1016/0024-3795(69)90028-7
[23] V.P. Crawford andE.M. Knoer, Job matching with heterogeneous firms and workers,Econometrica 49 (1981) 437–450. · Zbl 1202.91141 · doi:10.2307/1913320
[24] E. Dinic andM. Kronrod, An algorithm for the solution of the solution of the assignment problem,Soviet Math. Dokl. 10 (1969). · Zbl 0213.44801
[25] J. Edmonds andR.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems,J. ACM 19 (1972) 248–264. · Zbl 0318.90024 · doi:10.1145/321694.321699
[26] M. Engquist, A successive shortest path algorithm for the assignment problem,INFOR 20 (1982) 370–384. · Zbl 0506.90085
[27] H.N. Gabow andR.E. Tarjan, Faster scaling algorithms for graph matching, Revised Abstract, 1987.
[28] F. Glover, R. Glover andD. Klingman,Threshold Assignment Algorithm, Center for Business Decision Analysis report CBDA 107 (Graduate School of Business, Univ. of Texas at Austin, Sept. 1982).
[29] A.V. Goldberg, Solving minimum-cost flow problems by successive approximations, extended abstract, submitted toSTOC 87 (Nov. 1986).
[30] A. V. Goldberg,Efficient Graph Algorithms for Sequential and Parallel Computers, Tech. Report TR-374, Laboratory for Computer Science, M.I.T., Feb. 1987.
[31] A.V. Goldberg, andR.E. Tarjan, Solving minimum cost flow problems by successive approximation, in:Proc. 19th ACM STOC, May 1987.
[32] D. Goldfarb, Efficient dual simplex methods for the assignment problem,Math. Progr. 33 (1985) 187–203. · Zbl 0578.90051 · doi:10.1007/BF01582245
[33] M. Hung, A polynomial simplex method for the assignment problem,Oper. Res. 31 (1983) 595–600. · Zbl 0519.90056 · doi:10.1287/opre.31.3.595
[34] M. Hung andW. Rom, Solving the assignment problem by relaxation,Oper. Res. 28 (1980) 969–982. · Zbl 0441.90062 · doi:10.1287/opre.28.4.969
[35] J. Kennington andR. Helgason,Algorithms for Network Programming (Wiley, New York, 1980).
[36] D. Klingman, A. Napier andJ. Stutz, NETGEN – A program for generating large scale (un)capacitated assignment, transportation, and minimum cost flow network problems,Management Sci. 20 (1974) 814–822. · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814
[37] H.W. Kuhn, The Hungarian method for the assignment problem,Naval Res. Logistics Quarter. 2 (1955) 83–97. · Zbl 0143.41905 · doi:10.1002/nav.3800020109
[38] L.F. McGinnis, Implementation and testing of a primal-dual algorithm for the assignment problem,Oper. Res. 31 (1983) 277–291. · Zbl 0507.90055 · doi:10.1287/opre.31.2.277
[39] J.B. Orlin,Genuinely Polynomial Simplex and Non-Simplex Algorithms for the Minimum Cost Flow Problem, Working Paper No. 1615–84 (Sloan School of Management, M.I.T., Dec. 1984).
[40] C.H. Papadimitriou andK. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, N.J. 1982). · Zbl 0503.90060
[41] H. Rock, Scaling techniques for minimal cost network flows, in:Discrete Structures and Algorithms, ed.V. Page Carl Hansen, Munich, 1980.
[42] R.T. Rockafellar,Network Flows and Monotropic programming (J. Wiley, New York, 1984). · Zbl 0596.90055
[43] A.E. Roth, The economics of matching: stability and incentives,Math. Oper. Res. 7 (1982) 617–628. · Zbl 0496.90008 · doi:10.1287/moor.7.4.617
[44] L.S. Shapley andM. Shubik, The assignment game I: the core,Intern. J. Game Theory 1 (1972) 117–130. · Zbl 0236.90078
[45] E. Tardos, A strongly polynomial minimum cost circulation algorithm,Combinatorica 5 (1985) 247–255. · Zbl 0596.90030 · doi:10.1007/BF02579369
[46] A. Weintraub andF. Barahona,A Dual Algorithm for the Assignment Problem, Publ. No. 79/02/C (Departmento de Industrias, Universidad de Chile-Sede Occidente, Santiago, Chile, 1979).
[47] S.A. Zenios andJ.M. Mulvey, Relaxation techniques for strictly convex network problems,Ann. Oper. Res. 5 (1985/86), 517–538.
[48] S.A. Zenios andR.A. Lasken,Nonlinear Network Optimization on a Massively Parallel Connection Machine, Report 87-08-03 (Decision Science Department, The Wharton School, Univ. of Pennsylvania, Aug. 1987).
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.