×
Paparrizos, Konstantinos

An exterior point simplex algorithm for (general) linear programming problems. (English) Zbl 0786.90043

Ann. Oper. Res. 46-47, No. 1-4, 497-508 (1993).
Summary: We present an exterior point simplex type algorithm that possesses a new monotonic property. A dual feasible basic solution is required to start with. Intermediate solutions are neither primal nor dual feasible. Cycling-free pivoting rules and an exponentional example are presented.

Cited in 10 Documents

MSC:

90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

degeneracy; cycling-free pivoting rules; exterior point simplex type algorithm
PDF BibTeX XML Cite
\textit{K. Paparrizos}, Ann. Oper. Res. 46--47, No. 1--4, 497--508 (1993; Zbl 0786.90043)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] D. Avis and V. Chvátal, Notes on Bland’s rule, Math. Progr. Study 8 (1978) 24. · Zbl 0403.65025
[2] E.M.L. Beale, Cycling in the dual simplex algorithm, Naval Res. Log. Quarterly 2 (1955) 269. · Zbl 0068.13704
[3] R.G. Bland, New finite pivoting rules for the simplex method, Math. Oper. Res. 2 (1977) 103. · Zbl 0408.90050
[4] J. Clausen, A note on Edmonds-Fukuda pivoting rule for the simplex method, Eur. J. Oper. Res. 29 (1987) 378. · Zbl 0631.90040
[5] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[6] K. Fukuda, Oriented matroid programming, Ph.D. Thesis, Waterloo University, Waterloo, Ontario, Canada (1982).
[7] D. Goldfarb, Worst case complexity of the shadow vertex simplex algorithm, Columbia University, Department of Industrial Engineering and Operations Research (1983).
[8] M. Iri, A new method of solving transportation network problems, J. Oper. Res. Soc. Japan 3 (1960) 27. · Zbl 0215.29704
[9] R.G. Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discr. Math. 4 (1973) 367. · Zbl 0254.90027
[10] W.S. Jewell, Optimal flow through networks, Interim Technical Report No. 8, Operations Research Centre, M.I.T., Cambridge, MA (1985). · Zbl 0109.38203
[11] V. Klee and G.J. Minty, How good is the simplex algorithm?, in:Inequalities- III, ed. O. Shisha (Academic Press, New York, 1972) p. 159. · Zbl 0297.90047
[12] H.W. Kuhn, The Hungarian method for the assignment problem, Naval Res. Log. Quarterly 3 (1955) 253. · Zbl 0143.41905
[13] C.E. Lemke, The dual method of solving the linear programming problem, Naval Res. Log. Quarterly 1 (1955) 36. · Zbl 0128.39605
[14] K.G. Murty, Computational complexity of programming, Math. Progr. 19 (1980) 213. · Zbl 0443.90102
[15] K. Paparrizos, Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples, Opsearch 26 (1989) 77. · Zbl 0674.90063
[16] K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Progr. 51 (1991) 45. · Zbl 0734.90055
[17] C. Roos, An exponential example for Terlaky’s pivoting rule for the criss-cross simplex method, Math. Progr. 46 (1990) 78. · Zbl 0696.90035
[18] T. Terlaky, A convergent criss-cross method, Math. Oper. Stat. Ser. Optim. 16 (1985) 683. · Zbl 0581.90052
[19] S. Zhang, On anti-cycling pivoting rules of the simplex method, Oper. Res. Lett. 10 (1991) 189. · Zbl 0813.90083
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.