×

Criss-cross methods: A fresh view on pivot algorithms. (English) Zbl 0887.90113

Summary: Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution. The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms. The origins and the history of criss-cross methods are also touched upon.

MSC:

90C05 Linear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adler and N. Megiddo, A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension,Journal of the Association of Computing Machinery 32 (1985) 891–895. · Zbl 0634.65044
[2] D. Avis and V. Chvátal, Notes on Bland’s rule,Mathematical Programming Study 8 (1978) 24–34. · Zbl 0403.65025 · doi:10.1007/BFb0121192
[3] D. Avis and K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra,Discrete and Computational Geometry 8 (1992) 295–313. · Zbl 0752.68082 · doi:10.1007/BF02293050
[4] J. Beasley, ed.,Advances in Linear and Integer Programming (Oxford University Press, Oxford, UK, 1996). · Zbl 0869.00020
[5] R.E. Bixby, The simplex method: It keeps getting better, Lecture at the 14th International Symposium on Mathematical Programming, Amsterdam, The Netherlands, 1991.
[6] A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler,Oriented Matroids (Cambridge University Press, Cambridge, MA, 1993).
[7] R.G. Bland, New finite pivoting rules for the simplex method,Mathematics of Operations Research 2 (1977) 103–107. · Zbl 0408.90050 · doi:10.1287/moor.2.2.103
[8] R.G. Bland, A combinatorial abstraction of linear programming,Journal of Combinatorial Theory, Series B 23 (1977) 33–57. · Zbl 0375.90046 · doi:10.1016/0095-8956(77)90055-7
[9] R.G. Bland and M. Las Vergnas, Orientability of matroids,Journal of Combinatorial Theory, Series B 24 (1978) 94–123. · Zbl 0374.05016 · doi:10.1016/0095-8956(78)90080-1
[10] K.H. Borgwardt,The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, Vol. 1 (Springer, Berlin, 1987). · Zbl 0604.90092
[11] K. Cameron and J. Edmonds, Existentially polytime theorems, in:Proceedings of the DIMACS Workshop in Polyhedral Combinatorics, 1993. · Zbl 0726.68062
[12] Y.Y. Chang, Least index resolution of degeneracy in linear complementarity problems, Technical Report 79-14, Department of Operations Research, Stanford University, Stanford, CA, 1979.
[13] A. Charnes, Optimality and degeneracy in linear programming,Econometrica 20 (1952) 160–170. · Zbl 0049.37903 · doi:10.2307/1907845
[14] H.-D. Chen, P.M. Pardalos and M.A. Saunders, The simplex algorithm with a new primal and dual pivot rule,Operations Research Letters 16 (1994) 121–127. · Zbl 0812.90115 · doi:10.1016/0167-6377(94)90023-X
[15] V. Chvátal,Linear Programming (W.H. Freeman and Company, San Francisco, 1983).
[16] J. Clausen, A note on Edmonds-Fukuda pivoting rule for the simplex method,European Journal of Operations Research 29 (1987) 378–383. · Zbl 0631.90040 · doi:10.1016/0377-2217(87)90251-7
[17] R.W. Cottle, Symmetric dual quadratic programs,Quarterly of Applied Mathematics 21 (1963) 237–243. · Zbl 0127.36802
[18] R.W. Cottle and G.B. Dantzig, Complementary pivot theory of mathematical programming,Linear Algebra and Its Applications 1 (1968) 103–125. · Zbl 0155.28403 · doi:10.1016/0024-3795(68)90052-9
[19] R.W. Cottle, J.-S. Pang and V. Venkateswaran, Sufficient matrices and the linear complementarity problem.Linear Algebra and Its Applications 114/115 (1987) 235–249. · Zbl 0674.90092
[20] R.W. Cottle, J.-S. Pang and R.E. Stone,The Linear Complementarity Problem (Academic Press, New York, 1992). · Zbl 0757.90078
[21] G.B. Dantzig, Programming in a linear structure,Comptroller, USAF Washington, DC (February 1948).
[22] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[23] G.B. Dantzig, Linear programming: The story about how it began, in: A.H.G. Rinnoy Kan, L.K. Lenstra and A. Schrijver, eds.,History of Mathematical Programming (CWI, North-Holland, Amsterdam, 1991). 19–31.
[24] G.B. Dantzig, A. Orden and P. Wolfe, The generalized simplex method for minimizing a linear form under linear inequality restraints,Pacific Journal of Mathematics 5 (1955) 183–195. · Zbl 0064.39402 · doi:10.2140/pjm.1955.5.183
[25] J. Edmonds, Exact pivoting, Presentation, ECCO VII, 1994.
[26] J. Edmonds, A Helly method for linear programming, presentation, CO94, Amsterdam, 1994.
[27] J. Edmonds and K. Fukuda, NP easy and LP theory, Cours postgrade en Recherche Opérationnelle, École Polytechnique Fédérale de Lausanne, Lausanne, 1994.
[28] J. Folkman and J. Lawrence, Oriented matroids,Journal of Combinatorial Theory, Series B 25 (1978) 199–236. · Zbl 0382.05020 · doi:10.1016/0095-8956(78)90039-4
[29] K. Fukuda, Oriented matroid programming, Ph.D. Thesis, Waterloo University, Waterloo, Ontario, Canada, 1982.
[30] K. Fukuda, H.-J. Lüthi and M. Namiki, The existence of a short sequence of admissible pivots to an optimal basis in LP and LCP,ITOR, to appear. · Zbl 0907.90206
[31] K. Fukuda and H.-J. Lüthi, Combinatorial maximum improvement algorithm for LP and LCP, Presented at Franco-Japanese Days, Brest, France, 1995.
[32] K. Fukuda and T. Matsui, On the finiteness of the criss-cross method,European Journal of Operations Research 52 (1991) 119–124. · Zbl 0747.90062 · doi:10.1016/0377-2217(91)90343-T
[33] K. Fukuda and M. Namiki, On extremal behaviors of Murty’s least index method,Mathematical Programming 64 (1994) 365–370. · Zbl 0805.90105 · doi:10.1007/BF01582581
[34] K. Fukuda and M. Namiki, Finding all common basis in two matroids,Discrete Applied Mathematics 56 (1995) 231–243. · Zbl 0823.05020 · doi:10.1016/0166-218X(94)00088-U
[35] K. Fukuda, M. Namiki and A. Tamura, EP theorems and linear complementarity problems, Technical Report, Institute for Operations Research, ETH-Zentrum, CH-8092 Zürich, Switzerland, 1996. · Zbl 0908.90251
[36] K. Fukuda and T. Terlaky, Linear complementarity and oriented matroids,Journal of the Operational Research Society of Japan 35 (1992) 45–61. · Zbl 0773.90077
[37] D. Goldfarb, Worst case complexity of the shadow vertex simplex algorithm, Technical Report, Department of Industrial Engineering and Operations Research, Columbia University, 1983.
[38] D. Den Hertog, C. Roos and T. Terlaky, The linear complementarity problem, sufficient matrices and the criss-cross method,Linear Algebra and Its Applications 187 (1993) 1–14. · Zbl 0778.65044 · doi:10.1016/0024-3795(93)90124-7
[39] T. Illés. Á. Szirmai and T. Terlaky, A finite criss-Cross method for hyperbolic programming, Report No. 96-103, Faculteit der Technische Wiskunde en Informatica, Technische Universiteit Delft, The Netherlands, 1996; also in:European Journal of Operations Research, to appear. · Zbl 0953.90055
[40] D. Jensen, Coloring and duality: Combinatorial augmentation methods, Ph.D. Thesis, School of OR and IE, Cornell University, Ithaca, NY, 1985.
[41] G. Kalai and D. Kleitman, A quasi-polynomial bound for the diameter of graphs of polyhedra,Bull. Amer. Math. Soc. 26 (1992) 315–316. · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9
[42] N. Karmarkar, A new polynomial-time algorithm for linear programming,Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[43] L.G. Khachian, Polynomial algorithms in linear programming,Zhurnal Vichislitelnoj Matematiki i Matematischeskoi Fiziki 20 (1980) 51–68 (in Russian); English translation in:USSR Computational Mathematics and Mathematical Physics 20 (1980) 53–72.
[44] 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. · Zbl 0814.49029
[45] 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. · Zbl 0693.05020 · doi:10.1007/BF02124679
[46] V. Klee and G.J. Minty, How good is the simplex algorithm? in: O. Shisha, ed.,Inequalities - III (Academic Press, New York, 1972) 159–175. · Zbl 0297.90047
[47] V. Klee and P. Kleinschmidt, Thed-step conjecture and its relatives,Mathematics of Operations Research 12 (1987) 718–755. · Zbl 0632.52007 · doi:10.1287/moor.12.4.718
[48] M. Kojima, N. Megiddo, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science Vol. 538 (Springer, Berlin, 1991). · Zbl 0745.90069
[49] C.E. Lemke and J.T. Howson Jr, Equilibrium points of bimatrix games,SIAM Journal 12 (1964) 413–423. · Zbl 0128.14804
[50] C.E. Lemke, On complementary pivot theory, in: G.B. Dantzig and A.F. Veinott, eds.,Mathematics of Decision Sciences, Part 1 (AMS, Providence, RI, 1968) 95–114. · Zbl 0208.45502
[51] T.M. Liebling, On the number of iterations of the simplex method, in: R. Henn, H.P. Künzi and H. Schubert, eds.,Methods of Operations Research XVII (Verlag Anton, 1972) 248–264.
[52] 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, California, 1987.
[53] A. Mandel, Topology of oriented matroids, Ph.D. Thesis, Waterloo University, Waterloo, Ontario, 1982.
[54] W. Morris Jr and M.J. Todd, Symmetry and positive definiteness in oriented matroids, Technical Report No. 631, Cornell University, School of Operations Research and Industrial Engineering, Ithaca, NY, 1984. · Zbl 0649.05023
[55] K.G. Murty, A note on a Bard type scheme for solving the complementarity problem,Opsearch 11 (2–3) (1974) 123–130.
[56] K.G. Murty,Linear and Combinatorial Programming (Krieger Publishing Company, Malabar, FL, 1976). · Zbl 0334.90032
[57] K.G. Murty, Computational complexity of parametric linear programming,Mathematical Programming 19 (1980) 213–219. · Zbl 0443.90102 · doi:10.1007/BF01581642
[58] M. Namiki and T. Matsui, Some modifications of the criss-cross method, Research Report, Department of Information Sciences, Tokyo Institute of Technology, Tokyo, 1990.
[59] K. Paparrizos, Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples,Opsearch 26 (2) (1989) 77–95. · Zbl 0674.90063
[60] C. Roos, An exponential example for Terlaky’s pivoting rule for the criss-cross simplex method,Mathematical Programming 46 (1990) 78–94. · Zbl 0696.90035 · doi:10.1007/BF01585729
[61] C. Roos, T. Terlaky and J.-Ph. Vial,Theory and Algorithms for Linear Optimization: An Interior Point Approach (John Wiley & Sons, New York, 1997).
[62] J.E. Strum,Introduction to Linear Programming (Holden-Day, San Francisco, CA, 1972).
[63] T. Terlaky, Egy új, véges criss-cross módszer programozási feladatok megoldására,Alkalmazott Matematikai Lapok 10 (1984) 289–296 (in Hungarian, English title: A new, finite criss-cross method for solving linear programming problems).
[64] T. Terlaky, A convergent criss-cross method,Math. Oper. und Stat. ser. Optimization 16 (5) (1985) 683–690. · Zbl 0581.90052
[65] T. Terlaky, A finite criss-cross method for oriented matroids,Journal of Combinatorial Theory, Series B 42 (3) (1987) 319–327. · Zbl 0588.05010 · doi:10.1016/0095-8956(87)90049-9
[66] T. Terlaky, ed.,Interior Point Methods of Mathematical Programming (Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996). · Zbl 0866.00024
[67] T. Terlaky and S. Zhang, Pirvot rules for linear programming: A survey on recent theoretical developments,Annals of Operations Research 46 (1993) 203–233. · Zbl 0793.90034 · doi:10.1007/BF02096264
[68] M.J. Todd, Complementarity in oriented matroids,SIAM Journal on Algebraic and Discrete Mathematics 5 (1984) 467–485. · Zbl 0556.05016 · doi:10.1137/0605046
[69] M.J. Todd, Linear and quadratic programming in oriented matroids,Journal of Combinatorial Theory, Series B 39 (1985) 105–133. · Zbl 0555.05026 · doi:10.1016/0095-8956(85)90042-5
[70] M.J. Todd, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems,Mathematical Programming 35 (1986) 173–192. · Zbl 0613.90094 · doi:10.1007/BF01580646
[71] A. Tucker, A note on convergence of the Ford-Fulkerson flow algorithm,Mathematics of Operations Research 2 (2) (1977) 143–144. · Zbl 0397.90093 · doi:10.1287/moor.2.2.143
[72] H. Väliaho, A new proof of the finiteness of the criss-cross method,Math. Oper. und Stat. ser. Optimization 25 (1992) 391–400. · Zbl 0817.90074
[73] H. Väliaho,P *-matrices are just sufficient,Linear Algebra and Its Applications 239 (1996) 103–108. · Zbl 0851.15015
[74] Zh. Wang, A conformal elimination free algorithm for oriented matroid programming,Chinese Annals of Mathematics 8 (B1) (1987).
[75] Zh. Wang, A modified version of the Edmonds-Fukuda algorithm for LP in the general form,Asia-Pacific Journal of Operations Research 8 (1) (1991). · Zbl 0746.90035
[76] Zh. Wang, A general deterministic pivot method for oriented matroid programming,Chinese Annals of Mathematics B 13 (2) (1992). · Zbl 0765.90077
[77] Zh. Wang and T. Terlaky, A general scheme for solving linear complementarity problems in the setting of oriented matroids, in: H.P. Yap, T.H. Ku, E.K. Lloyd and Zh. Wang, eds.,Combinatorics and Graph Theory, Proceedings of the Spring School and International Conference on Combinatorics: SSIC’92, China (World Scientific, Singapore, 1993) 244–255. · Zbl 0835.90105
[78] S.J. Wright,Primal-Dual Interior Point Methods (SIAM Publications, Philadelphia, PA, 1996). · Zbl 0863.65031
[79] N. Zadeh, What is the worst case behavior of the simplex algorithm? Technical Report No. 27, Department of Operations Research, Stanford University, Stanford, CA, 1980. · Zbl 1172.90442
[80] S. Zhang, On anti-cycling pivoting rules for the simplex method,Operations Research Letters 10 (1991) 189–192. · Zbl 0813.90083 · doi:10.1016/0167-6377(91)90058-W
[81] S. Zhang, New variants of finite criss-cross pivot algorithms for linear programming, Technical Report, Econometric Institute, Erasmus University Rotterdam, 9707/A, 1997.
[82] S. Zionts, The criss-cross method for solving linear programming problems,Management Science 15 (7) (1969) 426–445. · Zbl 1231.90294 · doi:10.1287/mnsc.15.7.426
[83] S. Zionts, Some empirical test of the criss-cross method,Management Science 19 (1972) 406–410. · Zbl 0247.90034 · doi:10.1287/mnsc.19.4.406
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.