[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Pivot rules for linear programming: A survey on recent theoretical developments

  • Part I: Surveys
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed.

In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K.M. Anstreicher and T. Terlaky, A monotonic build-up simplex algorithm, Report 91-82. Faculty of Technical Mathematics and Informatics, Delft University of Technology, The Netherlands (1990), to appear in Oper. Res.

    Google Scholar 

  2. I. Adler and N. Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension, J. ACM 32(1985)891–895.

    Article  Google Scholar 

  3. D. Avis and V. Chvátal, Notes on Bland's rule, Math. Progr. Study 8(1978)24–34.

    Google Scholar 

  4. D. Avis and K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discr. Comp. Geom. 8(1992)295–313.

    Article  Google Scholar 

  5. R.E. Bixby, Implementing the simplex method: The initial basis, Report TR90-32, Department of Mathematical Sciences, Rice University, TX, USA (1991).

    Google Scholar 

  6. R.E. Bixby, The simplex method: It keeps getting better, Lecture at the14th Int. Symp. on Mathematical Programming, Amsterdam, The Netherlands (1991).

    Google Scholar 

  7. R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, Very large-scale linear programming: A case study in combining interior point and simplex methods, Oper. Res. 40(1992)885–897.

    Article  Google Scholar 

  8. R.G. Bland, New finite pivoting rules for the simplex method, Math. Oper. Res. 2(1977)103–107.

    Article  Google Scholar 

  9. R.G. Bland, A combinatorial abstraction of linear programming. J. Combin. Theory (Ser. B) 23(1977)33–57.

    Article  Google Scholar 

  10. K.H. Borgwardt,The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, Vol. 1 (Springer, 1987).

  11. E.A. Boyd, Resolving degeneracy in combinatorial linear programes: Steepest edge, steepest ascent and closest ascent, Report, Department of Mathematical Sciences, Rice University, TX, USA (1992).

    Google Scholar 

  12. N. Cameron, Stationarity in the simplex method. J. Austral. Math. Soc. 43(1987)137–142.

    Article  Google Scholar 

  13. Y.Y. Chang, Least index resolution of degeneracy in linear complementarity problems, Technical Report 79-14, Department of Operations Research, Stanford University, Stanford, CA, USA (1979).

    Google Scholar 

  14. Y.Y. Chang and R.W. Cottle, Least index resolution of degeneracy in quadratic programming, Math. Progr. 18(1980)127–137.

    Article  Google Scholar 

  15. S.Y. Chang and K.G. Murty, The steepest descent gravitational method for linear programming, Discr. Appl. Math. 25(1989)211–239.

    Article  Google Scholar 

  16. S.S. Chiu and Y. Ye, Simplex method and Karmarkar's algorithm: A unifying structure, Technical Report, Engineering Economic Systems Department, Stanford University, Stanford, CA, USA (1985).

    Google Scholar 

  17. M. Cirina, Remarks on a recent simplex pivoting rule, Math. Oper. Res. 49(1985)187–199.

    Google Scholar 

  18. J. Clausen, A note on Edmonds-Fukuda's pivoting rule for the simplex method, Eur. J. Oper. Res. 29(1987)378–383.

    Article  Google Scholar 

  19. R.W. Cottle, The principal pivoting method revisited, Math. Progr. Ser. B, 48(1990)369–385.

    Article  Google Scholar 

  20. G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).

    Google Scholar 

  21. H.A. Eiselt and C.-L. Sandblom, External pivoting in the simplex algorithm, Statistica Neerlandica 39(1985)327–341.

    Article  Google Scholar 

  22. J. Folkman and J. Lawrence, Oriented matroids, J. Combin. Theory (Ser. B) 25(1978)199–236.

    Article  Google Scholar 

  23. J.J.H. Forrest and J.A. Tomlin, Implementing the simplex method for the optimization subroutine library, IBM Sys. J. 31(1992)11–25.

    Article  Google Scholar 

  24. K. Fukuda, Oriented matroid programming, Ph.D. Thesis, Waterloo University, Waterloo, Ontario, Canada (1982).

    Google Scholar 

  25. K. Fukuda and T. Matsui, On the finiteness of the criss-cross method, Eur. J. Oper. Res. 52(1991)119–124.

    Article  Google Scholar 

  26. K. Fukuda and M. Namiki, Two extremal behaviors of the criss-cross method for linear complementarity problems, Research Report B-241, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan (1991).

    Google Scholar 

  27. K. Fukuda and T. Terlaky, A general algorithmic framework for quadratic programming and a generalization of Edmonds-Fukuda's rule as a finite version of the Van de Panne-Whinston method, Preprint, Eötvös University, Budapest (1989).

    Google Scholar 

  28. K. Fukuda and T. Terlaky, Linear complementarity and oriented matroids, J. Oper. Res. Soc. Japan 35(1992)45–61.

    Google Scholar 

  29. T. Gal, Degeneracy graphs — Theory and application: A state-of-the-art survey, Report No. 142, Fern Universität Hagen, Germany (1989).

    Google Scholar 

  30. T. Gal and F. Geue, The use of the TNP-rule to solve various degeneracy problems, Report No. 149a, Fern Universität Hagen, Germany (1990).

    Google Scholar 

  31. S. Gass and Th. Saaty, The computational algorithm for the parametric objective function, Naval Res. Log. Quarterly 2(1955)39–45.

    Article  Google Scholar 

  32. F. Geue, Eine neue Pivotauswahlregel und die durch sie induzierten Teilgraphen des positiven Entartungsgraphen, Report No. 141, Fern Universität Hagen, Germany (1989).

    Google Scholar 

  33. P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, A practical anti-cycling procedure for linearly constrained optimization, Math. Progr. 45(1989)437–474.

    Article  Google Scholar 

  34. D. Goldfarb, Worst case complexity of the shadow vertex simplex algorithm, Report, Department of Industrial Engineering and Operations Research, Columbia University, New York, USA (1983).

    Google Scholar 

  35. D. Goldfarb and J.J.H. Forrest, Steepest edge simplex algorithm for linear programming, Math. Progr. 57(1992)341–374.

    Article  Google Scholar 

  36. M. Haimovitz, The simplex method is very good! — On the expected number of pivot steps and related properties of random linear programs, Report, Columbia University, New York, USA (1983).

    Google Scholar 

  37. P.M.J. Harris, Pivot selection methods for the Devex LP code, Math. Progr. 5(1973)1–28.

    Article  Google Scholar 

  38. B. Hattersly and J. Wilson, A dual approach to primal degeneracy, Math. Progr. 42(1988)135–176.

    Article  Google Scholar 

  39. D. den Hertog, C. Roos and T. Terlaky, The linear complementarity problem, sufficient matrices and the criss-cross method, Lin. Alg. Appl. 187(1993)1–14.

    Article  Google Scholar 

  40. D. den Hertog, C. Roos and T. Terlaky, The inverse barrier method for linear programming, Report No. 91-27, Faculty of Technical Mathematics and Informatics, Delft University of Technology, The Netherlands (1991).

    Google Scholar 

  41. D. Jensen, Coloring and duality: Combinatorial augmentation methods, Ph.D. Thesis, School of OR and IE, Cornell University, Ithaca, NY, USA (1985).

    Google Scholar 

  42. J.E. Kalan, Machine inspired enhancements of the simplex algorithm, Technical Report CS75001-R, Computer Science Department, Virginia Polytechnical University, Blacksburg, VA, USA (1976).

    Google Scholar 

  43. N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4(1984)373–395.

    Article  Google Scholar 

  44. L.G. Khachian, Polynomial algorithms in linear programming, Zhurnal Vichislitelnoj Matematiki i Matematischeskoi Fiziki 20(1980)51–68 [in Russian transl: USSR Comp. Math. Math. Phys. 20(1980)53–72.

    Google Scholar 

  45. E. Klafszky and T. Terlaky, Remarks on the feasibility problems of oriented matroids, Ann. Univ. Sci. Budapestiensis de Rolando Eötvös Nominatae, Sectio Computatorica, 7(1987)155–157.

    Google Scholar 

  46. E. Klafszky and T. Terlaky, Variants of the Hungarian method for solving linear programming problems. Math. Oper. und Stat., ser. Optimization 20(1989)79–91.

    Google Scholar 

  47. E. Klafszky and T. Terlaky, Some generalizations of the criss-cross method for quadratic programming. Math. Oper. und Stat., ser. Optimization 24(1992)127–139.

    Google Scholar 

  48. E. Klafszky and T. Terlaky, Some generalizations of the criss-cross method for the linear complementarity problem of oriented matroids, Combinatorica 9(1989)189–198.

    Article  Google Scholar 

  49. E. Klee and G.J. Minty, How good is the simplex algorithm? in:Inequalities — III, ed. O. Shisha (Academic Press, New York, 1972) pp. 159–175.

    Google Scholar 

  50. V. Klee and P. Kleinshcmidt, Thed-step conjecture and its relatives, Math. Oper. Res. 12(1987)718–755.

    Article  Google Scholar 

  51. E. Klotz, Dynamic pricing criteria in linear programming, Technical Report SOL. No. 88-15, Systems Optimization Laboratory, Stanford University, Stanford, CA, USA (1988).

    Google Scholar 

  52. K.O. Kortanek and J. Zhu, New purification algorithms for linear programming, Naval Res. Log. Quarterly 35(1988)571–583.

    Article  Google Scholar 

  53. H.P. Künzi and H. Tzschach, The duoplex-algorithm, Numer. Mathematik 7(1965)222–225.

    Article  Google Scholar 

  54. C.E. Lemke, Bimatrix equilibrium points and mathematical programming, Manag. Sci. 11(1965)681–689.

    Article  Google Scholar 

  55. I. Lustig, The equivalence of Dantzig's self-dual parametric algorithm for linear programs to Lemke's algorithm for linear complementarity problems applied to linear programming, Technical Report SOL 87-4, Department of Operations Research, Stanford University, Stanford, CA, USA (1987).

    Google Scholar 

  56. T.L. Magnanti and J.B. Orlin, Parametric linear programming and anti-cycling pivoting rules, Math. Progr. 41(1988)317–325.

    Article  Google Scholar 

  57. N. Megiddo, On finding primal- and dual-optimal bases, ORSA J. Comp. 3(1991)63–65.

    Google Scholar 

  58. N. Megiddo, Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex-algorithm, RJ 6327 (61996), IBM Almaden Research Center, San Jose, CA, USA (1988).

    Google Scholar 

  59. K.G. Murty, A note on a Bard type scheme for solving the complementarity problem, Opsearch 11(1974)123–130.

    Google Scholar 

  60. K.G. Murty,Linear and Combinatorial Programming (Krieger, Malabar, USA, 1976).

    Google Scholar 

  61. K.G. Murty, Computational complexity of parametric linear programming, Math. Progr. 19(1980)213–219.

    Article  Google Scholar 

  62. K.G. Murty, The gravitational method of linear programming, Opsearch 23(1986)206–214.

    Google Scholar 

  63. K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming, Sigma Series in Applied Mathematics, Vol. 3 (Heldermann, Berlin, 1988).

    Google Scholar 

  64. K.G. Murty, A new interior variant of the gradient projection method for linear programming, Technical Report No. 85-18, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI 48109-2117, USA (1985).

    Google Scholar 

  65. M. Namiki and T. Matsui, Some modifications of the criss-cross method, Research Report, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan (1990).

    Google Scholar 

  66. P.-Q. Pan, Practical finite pivoting rules for the simplex method, OR Spektrum 12(1988)219–225.

    Article  Google Scholar 

  67. K. Paparrizos, Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples, Opsearch 26(1989)77–95.

    Google Scholar 

  68. K. Paparrizos, An exterior point simplex algorithm. Lecture at theEURO-TIMS Conf., Belgrade, Jugoslavia (1989).

  69. K. Paparrizos, A simplex algorithm with a new monotonicity property, Working Paper (1991).

  70. K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Progr. 51(1991)45–54.

    Article  Google Scholar 

  71. C. Roos, A pivoting rule for the simplex method which is related to Karmarkar's potential function, Manuscript, Faculty of Technical Mathematics and Informatics, Delft University of Technology, The Netherlands (1986).

    Google Scholar 

  72. C. Roos, An exponential example for Terlaky's pivoting rule for the criss-cross simplex method, Math. Progr. 46(1990)78–94.

    Article  Google Scholar 

  73. D.M. Ryan and M.R. Osborne, On the solution of highly degenerate linear programmes, Math. Progr. 41(1988)385–392.

    Article  Google Scholar 

  74. A. Schrijver,Theory of Linear and Integer Programming (J. Wiley, 1987).

  75. A. Sehti and G. Thompson, The pivot-and-probe algorithm for solving a linear problem, Math. Progr. 29(1984)219–233.

    Article  Google Scholar 

  76. R.E. Stone and C.A. Tovey, The simplex and projective scaling algorithms as iteratively reweighted least squares methods, SIAM Rev. 33(1991)220–237.

    Article  Google Scholar 

  77. A. Tamura, private communication (1991).

  78. A. Tamura, H. Takehara, K. Fukuda, S. Fujishige and M. Kojima, A dual interior primal simplex method for linear programming. J. Oper. Res. Soc. Japan 31(1988)413–430.

    Google Scholar 

  79. T. Terlaky, A finite criss-cross method for oriented matroids, J. Combin. Theory (Ser. B) 42(1987)319–327.

    Article  Google Scholar 

  80. T. Terlaky, A convergent criss-cross method, Math. Oper. und Stat., ser. Optimization 16(1985)683–690.

    Google Scholar 

  81. T. Terlaky, A new algorithm for quadratic programming, Eur. J. Oper. Res. 32(1987)294–301.

    Article  Google Scholar 

  82. M.J. Todd, Complementarity in oriented matroids, SIAM J. Alg. Discr. Math. 5(1984)467–485.

    Article  Google Scholar 

  83. M.J. Todd, Linear and quadratic programming in oriented matroids, J. Combin. Theory (Ser. B) 39(1985)105–133.

    Article  Google Scholar 

  84. M.J. Todd, A. Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm, Oper. Res. 38(1990)1006–1018.

    Article  Google Scholar 

  85. M.J. Todd, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems, Math. Progr. 35(1986)173–192.

    Article  Google Scholar 

  86. A. Tucker, A note on convergence of the Ford-Fulkerson flow algorithm, Math. Oper. Res. 2(1977)143–144.

    Article  Google Scholar 

  87. Zh. Wang, A conformal elimination-free algorithm for oriented matroid programming, Chin. Ann. Math. 8(B1)(1987).

  88. Zh. Wang, A modified version of the Edmonds-Fukuda algorithm for LP problems in the general form, Asia-Pacific J. Oper. Res. (1989).

  89. Zh. Wang, A general deterministic pivot method for oriented matroid programming, Chin. Ann. Math. (1990).

  90. Y. Ye and J.A. Kaliski, Further results on build-up approaches for linear programming, Lecture at theORSA/TIMS Meeting, Anaheim, CA, USA (1991).

  91. N. Zadeh, What is the worst case behavior of the simplex algorithm?, Technical Report No. 27, Department of Operations Research, Stanford University, Stanford, CA, USA (1980).

    Google Scholar 

  92. S. Zhang, On anti-cycling pivoting rules for the simplex method, Oper. Res. Lett. 10(1991)189–192.

    Article  Google Scholar 

  93. G.M. Ziegler, Linear programming in oriented matroids, Technical Report No. 195, Institut für Mathematik, Universität Augsburg, Germany (1990).

    Google Scholar 

  94. S. Zionts, The criss-cross method for solving linear programming problems, Manag. Sci. 15(1969)426–445.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Technical Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA, Delft, The Netherlands

    Tamás Terlaky

  2. Department of Econometrics, University of Groningen, P.O. Box 800, 9700 AV, Groningen, The Netherlands

    Shuzhong Zhang

Authors
  1. Tamás Terlaky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shuzhong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2115.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Terlaky, T., Zhang, S. Pivot rules for linear programming: A survey on recent theoretical developments. Ann Oper Res 46, 203–233 (1993). https://doi.org/10.1007/BF02096264

Download citation

  • Issue Date:

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

Keywords

Search

Navigation