Skip to main content
SpringerLink
Log in

A polynomial time primal network simplex algorithm for minimum cost flows

  • Published:
Mathematical Programming Submit manuscript

Abstract

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n 2m lognC, n 2m2 logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm 2 logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).

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

Similar content being viewed by others

References

  1. R.K. Ahuja, T.L. Magnanti and J.B. Orlin,Network Flows: Theory, Algorithms and Applications (Prentice Hall, Englewood Cliffs, NJ, 1993).

    Google Scholar 

  2. R.K. Ahuja, A.V. Goldberg, J.B. Orlin and R.E. Tarjan, Finding minimum-cost flows by double scaling,Mathematical Programming 53 (1992) 243–266.

    Article  MATH  MathSciNet  Google Scholar 

  3. A.V. Goldberg and R.E. Tarjan, Solving minimum cost flow problem by successive approximation,Mathematics of Operations Research 15 (1990) 430–466.

    MATH  MathSciNet  Google Scholar 

  4. J.B. Orlin, A faster strongly polynomial minimum cost flow algorithm,Operations Research 41 (1993) 338–350.

    MATH  MathSciNet  Google Scholar 

  5. N. Zadeh, A bad network problem for the simplex method and other minimum cost flow algorithms,Mathematical Programming 5 (1973) 255–266.

    Article  MATH  MathSciNet  Google Scholar 

  6. R.E. Tarjan, Efficiency of the primal network simplex algorithm for the minimum-cost circulation problem,Mathematics of Operations Research 16 (1991) 272–291.

    MATH  MathSciNet  Google Scholar 

  7. R.K. Ahuja and J.B. Orlin, The scaling network simplex algorithm,Operations Research 40, Supplement 1 (1992) S5-S13.

    MathSciNet  Google Scholar 

  8. M. Akgul, A genuinely polynomial primal simplex algorithm for the assignment problem,Discrete Applied Mathematics 45 (1993) 93–115.

    Article  MathSciNet  Google Scholar 

  9. M.S. Hung, A polynomial simplex method for the assignment problem,Operations Research 31 (1983) 595–600.

    MATH  MathSciNet  Google Scholar 

  10. J.B. Orlin, On the simplex algorithm for networks and generalized networks,Mathematical Programming Study 24 (1985) 166–178.

    MATH  MathSciNet  Google Scholar 

  11. P.T. Sokkalingam, P. Sharma and R.K. Ahuja, A new primal simplex algorithm for network flow problem, Unpublished manuscript, 1993; Presented at NETFLOW’93 at San Miniato, Italy.

  12. M. Akgul, Shortest path and simplex method, Research Report, Department of Computer Science and Operations Research, North Carolina State University, Raleigh, NC, 1985.

    Google Scholar 

  13. R. Dial, F. Glover, D. Karney and D. Klingman, A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees,Networks 9 (1979) 215–248.

    MATH  MathSciNet  Google Scholar 

  14. D. Goldfarb, J. Hao and S. Kai, Efficient shortest path simplex algorithms,Operations Research 38 (1990) 624–628.

    MATH  MathSciNet  Google Scholar 

  15. A.V. Goldberg, M.D. Grigoriadis and R.E. Tarjan, Use of dynamic trees in a network simplex algorithm for the maximum flow problem,Mathematical Programming 50 (1991) 277–290.

    Article  MATH  MathSciNet  Google Scholar 

  16. D. Goldfarb and J. Hao, A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2m) time,Mathematical Programming 47 (1990) 353–365.

    Article  MATH  MathSciNet  Google Scholar 

  17. D. Goldfarb and J. Hao, On strongly polynomial variants of the network simplex algorithm for the maximum flow problem,Operations Research Letters 10 (1991) 383–387.

    Article  MATH  MathSciNet  Google Scholar 

  18. J.B. Orlin, Genuinely polynomial simplex and nonsimplex algorithms for the minimum cost flow problem, Technical Report No. 1615-84, Sloan School of Management, MIT, Cambridge, MA, 1984.

    Google Scholar 

  19. S.A. Plotkin and E. Tardos, Improved dual network simplex, in:Proceedings of the 1st ACM - SIAM Symposium on Discrete Algorithms (1990) 367–376.

  20. J.B. Orlin, S.A. Plotkin and E. Tardos, Polynomial dual network simplex algorithms,Mathematical Programming 60 (1993) 255–276.

    Article  MathSciNet  Google Scholar 

  21. R. Armstrong and Z. Jin, A strongly polynomial dual network simplex algorithm,Mathematical Programming 78 (1997) 131–148.

    Article  MathSciNet  Google Scholar 

  22. D. Goldfarb and J. Hao, Polynomial simplex algorithms for the minimum cost network flow problem,Algorithmica 8 (1992) 145–160.

    Article  MathSciNet  Google Scholar 

  23. R.E. Tarjan, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm,Mathematical Programming 78 (1997) 169–177.

    Article  MathSciNet  Google Scholar 

  24. R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network flows, in: G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, eds.,Handbooks in Operations Research and Management Science, Vol. 1: Optimization (North-Holland, Amsterdam, 1989) 211–369.

    Google Scholar 

  25. É. Tardos, A strongly polynomial minimum cost circulation algorithm,Combinatorica 5 (1985) 247–255.

    Article  MATH  MathSciNet  Google Scholar 

  26. É. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs,Operations Research 34 (1986) 250–256.

    Article  MATH  MathSciNet  Google Scholar 

  27. M. Dyer and A. Frieze, Random walks, totally unimodular matrices and a randomised dual simplex algorithm,Mathematical Programming 64 (1994) 1–16.

    Article  MathSciNet  Google Scholar 

  28. W.H. Cunningham, A network simplex method,Mathematical Programming 11 (1976) 105–116.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sloan School of Management, MIT, 02139, Cambridge, MA, USA

    James B. Orlin

Authors
  1. James B. Orlin
    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

Orlin, J.B. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming 78, 109–129 (1997). https://doi.org/10.1007/BF02614365

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation