Skip to main content
SpringerLink
Log in

A network simplex method

  • Published:
Mathematical Programming Submit manuscript

Abstract

Simple combinatorial modifications are given which ensure finiteness in the primal simplex method for the transshipment problem and the upper-bounded primal simplex method for the minimum cost flow problem. The modifications involve keeping “strongly feasible” bases. An efficient algorithm is given for converting any feasible basis into a strongly feasible basis. Strong feasibility is preserved by a rule for choosing the leaving basic variable at each simplex iteration. The method presented is closely related to a new perturbation technique and to previously known degeneracy modifications for shortest path problems and maximum flow problems.

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. G.B. Dantzig, “Application of the simplex method to a transportation problem”, in: T.C. Koopmans, ed.,Activity analysis of production and allocation (Wiley, New York, 1951).

    Google Scholar 

  2. G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, 1963).

    Google Scholar 

  3. G.B. Dantzig, L.R. Ford, Jr., and D.R. Fulkerson, “A primal-dual algorithm for linear programs”, in: H.W. Kuhn and A.W. Tucker, eds.,Linear inequalities and related systems, Annals of Mathematics Study 38 (Princeton University Press, Princeton, 1956).

    Google Scholar 

  4. Jack Edmonds, “Exponential growth of the simplex method for shortest path problems”, University of Waterloo, (1970) unpublished.

  5. L.R. Ford, Jr. and D.R. Fulkerson,Flows in networks (Princeton University Press, Princeton, 1962).

    Google Scholar 

  6. D.R. Fulkerson and G.B. Dantzig, “Computations of maximal flows in networks”,Naval Research Logistics Quarterly 2 (1955) 277–283.

    Google Scholar 

  7. D. Gale, “A theorem on flows in networks”,Pacific Journal of Mathematics 7 (1957) 1073–1082.

    Google Scholar 

  8. B.J. Gassner, “Cycling in the transportation problem”,Naval Research Logistics Quarterly 11 (1964) 43–58.

    Google Scholar 

  9. Fred Glover, D. Karney, and D. Klingman, “The augmented predecessor index method for locating stepping-stone paths and assigning dual prices in distribution problems”,Transportation Science 6 (1972) 171–179.

    Google Scholar 

  10. Ellis Johnson, “Networks and basic solutions”,Operations Research 14 (1966) 619–623.

    Google Scholar 

  11. Alex Orden, “The transshipment problem”,Management Science 2 (1956) 276–285.

    Google Scholar 

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

    Google Scholar 

Additional references

  1. R.S. Barr, F. Glover and D. Klingman, “The alternating basis algorithm for assignment problems”, Mathematical Programming, to appear.

  2. R.G. Bland, “New finite pivoting rules for the simplex method”, CORE Discussion Paper, Université de Louvain, Belgium (1976).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Johns Hopkins University, Baltimore, Md., USA

    W. H. Cunningham

Authors
  1. W. H. Cunningham
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The author holds a National Research Council of Canada Post-Doctorate Fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cunningham, W.H. A network simplex method. Mathematical Programming 11, 105–116 (1976). https://doi.org/10.1007/BF01580379

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation