Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Avis and V. Chvátal, Notes on Bland's rule, Math. Progr. Study 8 (1978) 24.
E.M.L. Beale, Cycling in the dual simplex algorithm, Naval Res. Log. Quarterly 2 (1955) 269.
R.G. Bland, New finite pivoting rules for the simplex method, Math. Oper. Res. 2 (1977) 103.
J. Clausen, A note on Edmonds-Fukuda pivoting rule for the simplex method, Eur. J. Oper. Res. 29 (1987) 378.
G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
K. Fukuda, Oriented matroid programming, Ph.D. Thesis, Waterloo University, Waterloo, Ontario, Canada (1982).
D. Goldfarb, Worst case complexity of the shadow vertex simplex algorithm, Columbia University, Department of Industrial Engineering and Operations Research (1983).
M. Iri, A new method of solving transportation network problems, J. Oper. Res. Soc. Japan 3 (1960) 27.
R.G. Jeroslow, The simplex algorithm with the pivot rule of maximizing criterion improvement, Discr. Math. 4 (1973) 367.
W.S. Jewell, Optimal flow through networks, Interim Technical Report No. 8, Operations Research Centre, M.I.T., Cambridge, MA (1985).
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.
H.W. Kuhn, The Hungarian method for the assignment problem, Naval Res. Log. Quarterly 3 (1955) 253.
C.E. Lemke, The dual method of solving the linear programming problem, Naval Res. Log. Quarterly 1 (1955) 36.
K.G. Murty, Computational complexity of programming, Math. Progr. 19 (1980) 213.
K. Paparrizos, Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples, Opsearch 26 (1989) 77.
K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Progr. 51 (1991) 45.
C. Roos, An exponential example for Terlaky's pivoting rule for the criss-cross simplex method, Math. Progr. 46 (1990) 78.
T. Terlaky, A convergent criss-cross method, Math. Oper. Stat. Ser. Optim. 16 (1985) 683.
S. Zhang, On anti-cycling pivoting rules of the simplex method, Oper. Res. Lett. 10 (1991) 189.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Paparrizos, K. An exterior point simplex algorithm for (general) linear programming problems. Ann Oper Res 46, 497–508 (1993). https://doi.org/10.1007/BF02023111
Issue Date:
DOI: https://doi.org/10.1007/BF02023111