DISTRIBUTED ASYNCHRONOUS RELAXATION ALGORITHM FOR THE ASSIGNMENT PROBLEM.
Research output : Contribution to journal › Conference article › peer-review
Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained nonlinear optimization problems or systems of nonlinear equations. For problems with linear arc costs, relaxation methods have outperformed by a substantial margin the classical primal simplex and primal-dual methods on standard benchmark problems. However in these methods it is sometimes necessary to change the prices of several nodes as a group in addition to carrying out pure relaxation steps. As a result global node price information is needed occasionally, and distributed implementation becomes somewhat complicated. A distributed algorithm for solving the classical linear cost assignment problem is described. It uses exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local (neighbor) node price information. The algorithm can be implemented in an asynchronous (chaotic) manner, and seems quite efficient for problems with a small arc cost range.
ASJC Scopus subject areas
- Control and Systems Engineering
- Modeling and Simulation
- Control and Optimization
Other files and links
- Link to publication in Scopus
Fingerprint
- Assignment Problem Mathematics 100%
- Relaxation Engineering & Materials Science 80%
- Relaxation Method Mathematics 52%
- Costs Mathematics 47%
- Vertex of a graph Mathematics 36%
- Arc of a curve Mathematics 36%
- Primal-dual Method Mathematics 30%
- Network Flow Problem Mathematics 29%
T1 - DISTRIBUTED ASYNCHRONOUS RELAXATION ALGORITHM FOR THE ASSIGNMENT PROBLEM.
AU - Bertsekas, Dimitri P.
N2 - Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained nonlinear optimization problems or systems of nonlinear equations. For problems with linear arc costs, relaxation methods have outperformed by a substantial margin the classical primal simplex and primal-dual methods on standard benchmark problems. However in these methods it is sometimes necessary to change the prices of several nodes as a group in addition to carrying out pure relaxation steps. As a result global node price information is needed occasionally, and distributed implementation becomes somewhat complicated. A distributed algorithm for solving the classical linear cost assignment problem is described. It uses exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local (neighbor) node price information. The algorithm can be implemented in an asynchronous (chaotic) manner, and seems quite efficient for problems with a small arc cost range.
AB - Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained nonlinear optimization problems or systems of nonlinear equations. For problems with linear arc costs, relaxation methods have outperformed by a substantial margin the classical primal simplex and primal-dual methods on standard benchmark problems. However in these methods it is sometimes necessary to change the prices of several nodes as a group in addition to carrying out pure relaxation steps. As a result global node price information is needed occasionally, and distributed implementation becomes somewhat complicated. A distributed algorithm for solving the classical linear cost assignment problem is described. It uses exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local (neighbor) node price information. The algorithm can be implemented in an asynchronous (chaotic) manner, and seems quite efficient for problems with a small arc cost range.
UR - http://www.scopus.com/inward/record.url?scp=0022290407&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022290407&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:0022290407
SN - 0191-2216
JO - Proceedings of the IEEE Conference on Decision and Control
JF - Proceedings of the IEEE Conference on Decision and Control
The auction algorithm: A distributed relaxation method for the assignment problem
- Published: December 1988
- Volume 14 , pages 105–123, ( 1988 )
Cite this article
- D. P. Bertsekas 1
1880 Accesses
384 Citations
9 Altmetric
Explore all metrics
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(NAlog(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.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
Optimal classification trees.
The Big-M method with the numerical infinite M
Distributed accelerated gradient methods with restart under quadratic growth condition
R. Ahuja and J.B. Orlin , “An Improved Algorithm for Computing the Min Cycle Mean”, Unpublished Manuscript, Nov. 1987.
M.L. Balinski , Signature methods for the assignment problem, Oper. Res. 33 (1985) 527–537.
Google Scholar
M.L. Balinski , A competitive (dual) simplex method for the assignment problem, Math. Progr. 34 (1986) 125–141.
Article Google Scholar
R. Barr, F. Glover and D. Klingman , The alternating basis algorithm for assignment problems, Math. progr. 13 (1977) 1–13.
G.M. Baudet , Asynchronous iterative methods for multiprocessors, J. ACM 15 (1978) 226–244.
D.P. Bertsekas , A distributed algorithm for the assignment problem, Laboratory for Information and Decision Systems Working Paper (M.I.T., March 1979).
D.P. Bertsekas , A new algorithm for the assignment problem, Math. Progr. 21 (1981) 152–171.
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.
D.P. Bertsekas , A unified framework for primal-dual methods in minimum cost network flow problems, Math. Progr. 32 (1985) 125–145.
D.P. Bertsekas , Distributed asynchronous computation of fixed points, Math. Progr. 27 (1983) 107–120.
D.P. Bertsekas , Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems , LIDS Report P-1606 (M.I.T., Sept. 1986, revised Nov. 1986).
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.
D.P. Bertsekas and D. Castanon , The Auction Algorithm for Transportation Problems, unpublished manuscript (Nov. 1987).
D.P. Bertsekas and J. Eckstein , Distributed asynchronous relaxation methods for linear network flows problems, Proc. IFAC '87 , Munich, Germany (July 1987).
D.P. Bertsekas and D. El Baz , Distributed asynchronous relaxation methods for convex network flow problems, SIAM J. Control Optim. 25 (1987) 74–85.
D.P. Bertsekas and P. 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.
D.P. Bertsekas and P. Tseng , RELAX: A Code for Linear Network Flow Problems, in FORTRAN Codes for Network Optimization , (B. Simeone, ed.), Vol to be published by the Annals of Operations Research .
D.P. Bertsekas, P.A. Hosein and P. Tseng , Relaxation methods for network flow problems, SIAM J. Control Optim. 25 (1987) 1219–1243.
D.P. Bertsekas , and J.N. Tsitsiklis , Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Englewood Cliffs, N.J., 1988) to appear.
D.P. Bertsekas, J.N. Tsitsiklis and M. 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 , and M. Lucertini , (Springer-Verlag, N.Y., 1986) pp. 107–120.
R.G. Bland and D.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).
D. Chazan and W. Miranker , Chaotic relaxation, Linear Algebra Appl. 2 (1969) 199–222.
V.P. Crawford and E.M. Knoer , Job matching with heterogeneous firms and workers, Econometrica 49 (1981) 437–450.
E. Dinic and M. Kronrod , An algorithm for the solution of the solution of the assignment problem, Soviet Math. Dokl. 10 (1969).
J. Edmonds and R.M. Karp , Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM 19 (1972) 248–264.
M. Engquist , A successive shortest path algorithm for the assignment problem, INFOR 20 (1982) 370–384.
H.N. Gabow and R.E. Tarjan , Faster scaling algorithms for graph matching, Revised Abstract, 1987.
F. Glover, R. Glover and D. Klingman , Threshold Assignment Algorithm , Center for Business Decision Analysis report CBDA 107 (Graduate School of Business, Univ. of Texas at Austin, Sept. 1982).
A.V. Goldberg , Solving minimum-cost flow problems by successive approximations, extended abstract, submitted to STOC 87 (Nov. 1986) .
A. V. Goldberg , Efficient Graph Algorithms for Sequential and Parallel Computers , Tech. Report TR-374, Laboratory for Computer Science, M.I.T., Feb. 1987.
A.V. Goldberg , and R.E. Tarjan , Solving minimum cost flow problems by successive approximation, in: Proc. 19th ACM STOC , May 1987.
D. Goldfarb , Efficient dual simplex methods for the assignment problem, Math. Progr. 33 (1985) 187–203.
M. Hung , A polynomial simplex method for the assignment problem, Oper. Res. 31 (1983) 595–600.
M. Hung and W. Rom , Solving the assignment problem by relaxation, Oper. Res. 28 (1980) 969–982.
J. Kennington and R. Helgason , Algorithms for Network Programming (Wiley, New York, 1980).
D. Klingman, A. Napier and J. Stutz , NETGEN — A program for generating large scale (un)capacitated assignment, transportation, and minimum cost flow network problems, Management Sci. 20 (1974) 814–822.
H.W. Kuhn , The Hungarian method for the assignment problem, Naval Res. Logistics Quarter. 2 (1955) 83–97.
L.F. McGinnis , Implementation and testing of a primal-dual algorithm for the assignment problem, Oper. Res. 31 (1983) 277–291.
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).
C.H. Papadimitriou and K. Steiglitz , Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, N.J. 1982).
H. Rock , Scaling techniques for minimal cost network flows, in: Discrete Structures and Algorithms , ed. V. Page Carl Hansen, Munich, 1980.
R.T. Rockafellar , Network Flows and Monotropic programming (J. Wiley, New York, 1984).
A.E. Roth , The economics of matching: stability and incentives, Math. Oper. Res. 7 (1982) 617–628.
L.S. Shapley and M. Shubik , The assignment game I: the core, Intern. J. Game Theory 1 (1972) 117–130.
E. Tardos , A strongly polynomial minimum cost circulation algorithm, Combinatorica 5 (1985) 247–255.
A. Weintraub and F. Barahona , A Dual Algorithm for the Assignment Problem , Publ. No. 79/02/C (Departmento de Industrias, Universidad de Chile-Sede Occidente, Santiago, Chile, 1979).
S.A. Zenios and J.M. Mulvey , Relaxation techniques for strictly convex network problems, Ann. Oper. Res. 5 (1985/86), 517–538.
S.A. Zenios and R.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).
Download references
Author information
Authors and affiliations.
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 02139, Cambridge, Mass.
D. P. Bertsekas
You can also search for this author in PubMed Google Scholar
Additional information
Work supported by Grant NSF-ECS-8217668. Thanks are due to J. Kennington and L. Hatay of Southern Methodist Univ. for contributing some of their computational experience.
Rights and permissions
Reprints and permissions
About this article
Bertsekas, D.P. The auction algorithm: A distributed relaxation method for the assignment problem. Ann Oper Res 14 , 105–123 (1988). https://doi.org/10.1007/BF02186476
Download citation
Issue Date : December 1988
DOI : https://doi.org/10.1007/BF02186476
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Computational Result
- Assignment Problem
- Dual Problem
- Case Complexity
- Parallel Machine
- Find a journal
- Publish with us
- Track your research
A distributed auction algorithm for the assignment problem
Ieee account.
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
Help | Advanced Search
Computer Science > Information Theory
Title: a distributed, asynchronous and incremental algorithm for nonconvex optimization: an admm based approach.
Abstract: The alternating direction method of multipliers (ADMM) has been popular for solving many signal processing problems, convex or nonconvex. In this paper, we study an asynchronous implementation of the ADMM for solving a nonconvex nonsmooth optimization problem, whose objective is the sum of a number of component functions. The proposed algorithm allows the problem to be solved in a distributed, asynchronous and incremental manner. First, the component functions can be distributed to different computing nodes, who perform the updates asynchronously without coordinating with each other. Two sources of asynchrony are covered by our algorithm: one is caused by the heterogeneity of the computational nodes, and the other arises from unreliable communication links. Second, the algorithm can be viewed as implementing an incremental algorithm where at each step the (possibly delayed) gradients of only a subset of component functions are update d. We show that when certain bounds are put on the level of asynchrony, the proposed algorithm converges to the set of stationary solutions (resp. optimal solutions) for the nonconvex (resp. convex) problem. To the best of our knowledge, the proposed ADMM implementation can tolerate the highest degree of asynchrony, among all known asynchronous variants of the ADMM. Moreover, it is the first ADMM implementation that can deal with nonconvexity and asynchrony at the same time.
Submission history
Access paper:.
- Other Formats
References & Citations
- Google Scholar
- Semantic Scholar
DBLP - CS Bibliography
Bibtex formatted citation.
Bibliographic and Citation Tools
Code, data and media associated with this article, recommenders and search tools.
- Institution
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .
IMAGES
VIDEO
COMMENTS
Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained non-linear optimization problems or systems of nonlinear equations. In their pure form they modify the dual variables (node prices) one at a time using only local node information while aiming to improve the dual cost. They are particularly well ...
A distributed algorithm for solving the classical linear cost assignment problem that employs exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local node price information. Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained ...
A distributed algorithm for solving the classical linear cost assignment problem is described. It uses exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local (neighbor) node price information.
assignment problem by replacing single sources and single sinks of the transportation problem with multiple persons and objects respectively in the assignment problem. By applying the auction algorithm to this assignment problem, one can derive a generic form of the e-relaxation method of [30], [31].)
The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice, and is also naturally well suited for parallel computation. The algorithm represents a significant departure from the cost improvement idea ...
A Distributed Asynchronous Relaxation Algorithm for the Assignment Problem; D.P. Bertsekas The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem LIDS Report P-1653 (March 1987) D.P. Bertsekas A Unified Framework for Primal-Dual Methods in Minimum Cost Network Flow Problems.
The algorithm operates like an auction whereby unassigned persons bid simultaneously f objects r thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. Thealgorithm can also be inter-preted as a Jacobi - like relaxation method f rsolving a dual problem.
A class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation using the notion ofε-complementary slackness is reviewed, and two specific methods, theε-relaxation algorithm for the minimum-cost flow problem, and the auction algorithms for the assignment problem are presented.
Bertsekas, D. P. 1985, "A distributed asynchronous relaxation algorithm for the assignment problem," Proceedings 24th IEEE Conference on Decision and Control, pp. 1703-1704. Google Scholar Bertsekas, D. P. 1986a, "Distributed asynchronous relaxation methods for linear network flow problems," LIDS Report P-1606, Massachusetts Institute of ...
The with the alternatives for some classes of problems. An example corresponding algorithm was first proposed in Sept. 1986 and is the max-flow problem for which an O(N3) worst case published in [3]. Special cases of this algorithm for the complexity is proved (see Section 5). When applied to this assignment problem date to 1979; see [4], [6].
f We consider distributed solutionof the classical linear minimum = x(i,j)E A Si,( Pi - Pj) - ZiE N SiPi (5 a) cost network flow problem. We formulatedual a problem which is where unconstrained, piecewise linear,and involves a dual variable for each node. We propose a dual algorithm that resembles a Gauss-Seidel Cl ijC Pi - Pj) = min { (ai ...
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 ...
objects respectively in the assignment problem. By applying the auction algo-rithm to this assignment problem, one can derive a generic form of the (-relaxation .method of [II], [12].) The conceptually useful interpretation as a Jacobi-like relaxation method is also nontrivial to obtain starting from the general network flow framework.
A Distributed Algorithm for the Assignment Problem Dimitri P. Bertsekas March 1979y Abstract This paper describes a new algorithm for solving the classical assign-ment problem. The algorithm is of a primal-dual nature and in some ways resembles the Hungarian and subgradient methods, but is substantially di erent in other respects.
D. P. Bertsekas, A distributed algorithm for the assignment problem, Laboratory for Information and Decision Systems Working Paper, Massachusetts Institute of Technology, Cambridge, MA, 1979, March ... D. P. Bertsekas, A distributed asynchronous relaxation algorithm for the assignment problem, Proc. 24th IEEE Conf. Decision and Control, 1985 ...
A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives Recent progress in solving quadratic assignment problems QAPs from the QAPLIB Quadratic Assignment Problem Library test set has come from mixed-integer linear or quadratic programming models that are solved in a branch-and-bound ...
Published 2022. Computer Science. TLDR. This paper describes a new algorithm for solving the classical assignment problem that is well suited for distributed operation whereby each node participates in the computation on the basis of limited local information about the topology of the network and the data of the problem. Expand.
The assignment problem constitutes one of the fundamental problems in the context of linear programming. Besides its theoretical significance, its frequent appearance in the areas of distributed control and facility allocation, where the problems¿ size and the cost for global computation and information can be highly prohibitive, gives rise to the need for local solutions that dynamically ...
In this paper we discuss the parallel implementation of the auction algorithm for the classical assignment problem. We show that the algorithm admits a totally asynchronous implementation and we consider several implementations on a shared memory machine, with varying degrees of synchronization. We also discuss and explore computationally the ...
The structure of the dual allows the successful application of a distributed asynchronous method whereby relaxation iterations are carried out in parallel by several processors in arbitrary order and with arbitrarily large interprocessor communication delays. We consider the solution of the single commodity strictly convex network flow problem in a distributed asynchronous computation environment.
The alternating direction method of multipliers (ADMM) has been popular for solving many signal processing problems, convex or nonconvex. In this paper, we study an asynchronous implementation of the ADMM for solving a nonconvex nonsmooth optimization problem, whose objective is the sum of a number of component functions. The proposed algorithm allows the problem to be solved in a distributed ...
This paper introduces a novel variation of the assignment problem, wherein there are multiple DMs and each DM knows only a part of the weight matrix and/or controls a subset of the assets. Abstract : Task-asset assignment is a fundamental problem paradigm in a wide variety of applications. Typical problem setting involves a single decision maker (DM) who has complete knowledge of the weight ...