Skip to main content
SpringerLink
Log in

Auction algorithms for network flow problems: A tutorial introduction

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  1. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, “Network flows,” Sloan W.P. No. 2059–88. M.I.T., Cambridge, MA, 1989 also in Handbooks in Operations Research and Management Science. Vol. 1 Optimization G.L. Nemhauser, A.H.G. Rinnooy-Kan, and M.J. Todd (eds.), North-Holland:Amsterdam, 1989, pp. 211–369.

    Google Scholar 

  2. R.K. Ahuja and J.B. Orlin, “A fast and simple algorthm for the maximum flow problem,” working paper, M.I.T., Cambridge, MA, 1986 (also in Oper. Res., vol. 37, 1989, pp. 748–759).

    Google Scholar 

  3. J.A. Ajevedo, M.E.S. Costa, J.J.S. Madeira, and E.V. Martins, “An algorithm for the ranking of shortest paths,” working paper, Universidade de Coimbra, Coimbra, Portugal, 1991.

    Google Scholar 

  4. J.A. Ajevedo, J.J.S. Madeira, E.V. Martins, and F.M. Pires, “A computational improvement for a shortest paths ranking algorithm,” working paper, Universidade de Coimbra, Coimbra, Portugal, 1991.

    Google Scholar 

  5. D.P. Bertsekas, “The auction algorithm for shortest paths,” SIAM J. on Optimization, vol. 1, 1991, pp. 425–447.

    Google Scholar 

  6. D.P. Bertsekas, “The auction algorithm: A distributed relaxation method for the assignment problem,” Annals of Oper. Res., vol. 14, 1988, pp. 105–123.

    Google Scholar 

  7. D.P. Bertsekas, “A distributed algorithm for the assignment problem,” working paper, Lab. for Information and Decision Systems, M.I.T., Cambridge, MA, March 1979.

    Google Scholar 

  8. D.P. Bertsekas, “A distributed asynchronous relaxation algorithm for the assignment problem,” in Proc. 24th IEEE Conf. Dec. and Contr., 1985, pp. 1703–1704.

  9. D.P. Bertsekas, “Distributed asynchronous relaxation methods for linear network flow problems,” Lab. for Information and Decision Systems, M.I.T., Report P-1606, Cambridge, MA, November 1986.

    Google Scholar 

  10. D.P. Bertsekas, “Distributed relaxation methods for linear network flow problems,” in Proc. of 25th IEEE Conf. Dec. and Contr., 1986, pp. 2101–2106.

  11. D.P. Bertsekas Linear Network Optimization: Algorithms and Codes, M.I.T. Press, Cambridge, MA, 1991.

    Google Scholar 

  12. D.P. Bertsekas, “A new algorithm for the assignment problem,” Math. Programming, vol. 21, 1981, pp. 152–171.

    Google Scholar 

  13. D.P. Bertsekas and D.A. Castañon, “The auction algorithm for minimum cost network flow Problem,” Laboratory for Information and Decision Systems, M.I.T., Cambridge, MA, November, Report LIDS-P-1925, 1989.

    Google Scholar 

  14. D.P. Bertsekas and D.A. Castañon, “The auction algorithm for transportation problems,” Annals of Oper. Res., vol. 20, pp. 67–96.

  15. D.P. Bertsekas and D.A. Castañon, “A forward/reverse auction, algorithm for the asymmetric assignment problem,” Alphatech Inc. Report, Burlington, MA, April, 1992, J. of Computational Optimization and its Applications (to appear).

  16. D.P.Bertsekas and D.A.Castañon “A generic auction algorithm for the minimum cost network flow problem,” Alphatech Inc. Report, Burlington, MA, Sept., 1991.

  17. D.P. Bertsekas and D.A. Castañon, “Parallel synchronous and asynchronous implementations of the auction algorithm,” Alphatech Inc. Report, Burlington, MA, Nov. 1989, (also in Parallel Computing, vol. 17, 1991, pp. 707–732).

  18. D.P. Bertsekas, D.A. Castañon, and H. Tsaknakis, “Reverse auction and the solution of inequality constrained assignment problems,” unpublished report, 1991, SIAM J. on Optimization (to appear).

  19. D.P. Bertsekas and J. Eckstein, “Distributed asynchronous relaxation methods for linear network flow problems,” Proc. of IFAC '87, Munich, Germany, July, 1987.

  20. D.P. Bertsekas and J. Eckstein, “Dual coordinate step methods for linear network flow problems,” Math. Progr., Series B, vol. 42, 1988, pp. 203–243.

    Google Scholar 

  21. D.P. Bertsekas and S.K. Mitter, “Descent numerical methods for optimization problems with nondifferentiable cost functions,” SIAM J. on Control vol. 11, pp. 637–652.

  22. D.P. Bertsekas, S. Pallottino, and M.G. Scutella', “Polynomial auction algorithms for shortest paths,” Lab. for Information and Decision Systems, Report p. 2107, M.I.T. 1992, submitted for publication.

  23. D.P. Bertsekas and J.N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall: Englewood Cliffs, NJ, 1989.

    Google Scholar 

  24. D.A. Castañon, “Reverse auction algorithms for assignment problems,” DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1992.

  25. D. Castañon, B. Smith, and A. Wilson, “Performance of parallel assignment algorithms on different multiprocessor architectures,” Alphatech Inc. Report, Burlington, MA, 1989.

  26. J. Cheriyan and S.N. Maheshwari, “Analysis of preflow push algorithms for maximum network flow,” SIAM J. Comput., vol. 18, 1989, pp. 1057–1086.

    Google Scholar 

  27. G.B. Dantzig, Linear Programming and Extensions, Princeton Univ. Press: Princeton, NJ, 1963.

    Google Scholar 

  28. S.E. Dreyfus, “An appraisal of some shortest path algorithms,” Oper. Res., vol. 17, 1969, pp. 395–412.

    Google Scholar 

  29. L.R. FordJr. and D.R. Fulkerson, Flows in Networks, Princeton Univ. Press: Princeton, NJ, 1962.

    Google Scholar 

  30. A.V. Goldberg, “Efficient graph algorithms for sequential and parallel computers,” Laboratory for Computer Science, M.I.T., Cambridge, MA., Tech., Report TR-374, 1987.

    Google Scholar 

  31. A.V. Goldberg, “A new max-flow algorithm,” Laboratory for Computer Science, M.I.T., Cambridge, MA, Tech. Mem. MIT/LCS/TM-291, 1985.

    Google Scholar 

  32. A.V. Goldberg and R.E. Tarjan “A new approach to the maximum flow problem,” in Proc. 18th ACM STOC, 1986, pp. 136–146.

  33. A.V. Goldberg and R.E. Tarjan “Solving minimum cost flow problems by successive approximation” Math. of Oper. Res., vol. 15, 1990, pp. 430–466.

    Google Scholar 

  34. R. Jonker and A. Volegnant, “A shortest augnmenting path algorithm for dense and sparse linear assignment problems,” Computing, vol. 38, 1987, pp. 325–340.

    Google Scholar 

  35. D. Kempa, J. Kennington, and H. Zaki, “Performance characteristics of the Jacobi and Gauss-Seidel versions of the auction algorithm on the alliant FX/8,” Dept. of Mech. and Ind. Eng., Univ. of Illinois, Champaign-Urbana, IL, Report OR-89–008, 1989.

    Google Scholar 

  36. H.W. Kuhn, “The Hungarian method for the assignment problem,” Nav. Res. Log. Q., vol. 2, 1955, pp. 83–97.

    Google Scholar 

  37. E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Reinhart, and Winston: New York, 1976.

    Google Scholar 

  38. X. Li and S.A. Zenios, “Data parallel solutions of min-cost network flow problems using ∈-relaxations,” Dept. of Decision Sciences, The Wharton School, Univ. of Pennsylvania, Philadelphia, PA, Report, 1991–05–20, 1991.

    Google Scholar 

  39. D.G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley: Reading, MA, 1984.

    Google Scholar 

  40. E.V. Martins, “An algorithm for ranking paths that may contain cycles,” European J. of Oper. Res., vol. 18, 1984, pp. 123–130.

    Google Scholar 

  41. G. Mazzoni, S. Pallotino, and M.G. Scutella', “The maximum flow problem: A max-preflow approach,” European J. of Oper. Res., vol. 53, 1991.

  42. G.J. Minty, “A Comment on the ShortestRoute Problem,” Opertions Research, vol. 5, p. 724, 1957.

  43. S. Pallottino and M.G. Scutella', “Strongly polynomial algorithms for shortest paths”, Dipartimento di Informatica Report TR-19/91, University of Pisa, Italy, 1991.

    Google Scholar 

  44. C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall:Englewood Cliffs, NJ, 1982.

    Google Scholar 

  45. C. Phillips and S.A. Zenios, “Experiences with large scale network optimization on the Connection Machine,” Dept. of Decision Sciences, The Wharton School, Univ. of Pennsylvania, Philadelphia, PA, Report 88–11–05, Nov. 1988.

    Google Scholar 

  46. L. Polymenakos, “Analysis of parallel asynchronous schemes for the auction shortest path algorithm,” MS thesis, EECS Dept., M.I.T., Cambridge, MA., Jan. 1991.

  47. L. Polymenakos and D.P. Bertsekas, “Parallel shortest path auction algorithms,” Lab. for Information and Decision Systems, Unpublished Report, M.I.T., Cambridge, MA, April 1992.

    Google Scholar 

  48. R.T. Rockafellar, Network Flows and Monotropic Programming, Wiley-Interscience: New York, 1984.

    Google Scholar 

  49. B.L. Schwartz, “A computational analysis of the auction algorithm,” unpublished manuscript.

  50. J. Wein and S.A. Zenios, “Massively parallel auction algorithms for the assignment problem,” Proc. of 3rd Symposium on the Frontiers of Massively Parallel Computation, MD., 1990.

  51. J. Wein and S.A. Zenios, “On the massively parallel solution of the assignment problem,” J. of Parallel and Distributed Computing, vol. 13, 1991, pp. 228–236.

    Google Scholar 

  52. H. Zaki, “A comparison of two algorithms for the assignment problem,” Dept. of Mechanical and Industrial Engineering, Univ. of Illinois, Urbana, IL., Report ORL 90–002, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory For Information and Decision Systems, Massachusetts Institute of Technology, 02139, Cambridge, MA, USA

    Dimitri P. Bertsekas

Authors
  1. Dimitri P. Bertsekas
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bertsekas, D.P. Auction algorithms for network flow problems: A tutorial introduction. Comput Optim Applic 1, 7–66 (1992). https://doi.org/10.1007/BF00247653

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00247653

Keywords

Search

Navigation