Pivoting rules for the revised simplex algorithm
DOI:
https://doi.org/10.2298/YJOR140228016PKeywords:
linear programming, revised simplex method, pricing, pivoting rulesAbstract
Pricing is a significant step in the simplex algorithm where an improving nonbasic variable is selected in order to enter the basis. This step is crucial and can dictate the total execution time. In this paper, we perform a computational study in which the pricing operation is computed with eight different pivoting rules: (i) Bland’s Rule, (ii) Dantzig’s Rule, (iii) Greatest Increment Method, (iv) Least Recently Considered Method, (v) Partial Pricing Rule, (vi) Queue Rule, (vii) Stack Rule, and (viii) Steepest Edge Rule; and incorporate them with the revised simplex algorithm. All pivoting rules have been implemented in MATLAB. The test sets used in the computational study are a set of randomly generated optimal sparse and dense LPs and a set of benchmark LPs (Netliboptimal, Kennington, Netlib-infeasible).References
Bazaraa, M.S., Jarvis, J.J., Sherali, H.D., "Linear Programming and Network Flows", John Wiley & Sons, Inc., 1990.
Benichou, M., Gautier, J., Hentges, G., Ribiere, G., "The efficient solution of large-scale linear programming problems", Mathematical Programming, 13(1977) 280-322.
Bland, R.G., "New finite pivoting rules for the simplex method", Mathematics of Operations Research, 2(2)(1977) 103-107.
Carolan, W.J., Hill, J.E., Kennington, J.L., Niemi, S., Wichmann, S.J., "An Empirical Evaluation of the KORBX Algorithms for Military Airlift Applications", Operations Research, 38(2)(1990) 240-248.
Clausen, J., "A note on Edmonds-Fukuda's pivoting rule for the simplex method", European Journal of Operational Research, 29 (1987) 378-383.
Dantzig, G.B., "Linear programming and extensions", Princeton University Press, New Jersey, 1963.
Forrest, J.J., Goldfarb, D., "Steepest-edge simplex algorithms for linear programming", Mathematical Programming, 57(1-3)(1992) 341-374.
Fukuda, K., "Oriented matroid programming", Ph.D. Thesis, Waterloo University, Waterloo, Ontario, Canada, 1982.
Gärtner, B., "Randomized optimization by Simplex-type methods", PhD thesis, Freien Universität, Berlin, 1995.
Gay, D.M., "Electronic mail distribution of linear programming test problems", Mathematical Programming, Society COAL Newsletter 13(1985) 10-12.
Goldfarb, D., Reid, J.K., "A Practicable Steepest-Edge Simplex Algorithm", Mathematical Programming, 12(3)(1977) 361-371.
Harris, P.M.J., "Pivot selection methods for the Devex LP code", Mathematical Programming, 5 (1973) 1-28.
Klee, V., Minty, G.J., "How good is the simplex algorithm", in: Shisha, O. (ed.) Inequalities- III. Academic Press, New York and London, 1972.
Maros, I., Khaliq, M.H., "Advances in design and implementation of optimization software", European Journal of Operational Research, 140(2) (1999) 322-337.
Murty, K.G., "Anoteona Bard type scheme for solving the complementarity problem", Opsearch, 11 (1974) 123-130.
Papadimitriou, C.H., Steiglitz, K., "Combinatorial Optimization: Algorithms and Complexity", Prentice-Hall, Inc., 1982.
Samaras, N., Sifaleras, A., Triantafyllidis, C., "A primal-dual exterior point algorithm for linear programming problems", Yugoslav Journal of Operations Research, 19 (1)(2009) 123-132.
Sifaleras, A., "Minimum cost network flows: Problems, algorithms, and software", Yugoslav Journal of Operations Research, 23 (1)(2013) 3-17.
Świetanowski, A., "A new steepest edge approximation for the simplex method for linear programming", Computational Optimization and Application, 10 (3)(1998) 271-281.
Thomadakis, M.E., "Implementation and Evaluation of Primal and Dual Simplex Methods with Different Pivot-Selection Techniques in the LPBench Environment", A Research Report. Texas A&M University, 1994.
Vanderbei, R.J., "Linear Programming: Foundations and Extensions (2nd ed.)", Kluwer Academic Publishers, Whitmore, 2001.
Wang, Z., "A modified version of the Edmonds-Fukuda algorithm for LP problems in the general form", Asia-Pacific Journal of Operational Research, 8(1)(1991) 55-61.
Zadeh, N., "What is the worst case behavior of the simplex algorithm?", Technical report, Stanford University, 1980.
Zhang, S., "On anti-cycling pivoting rules for the simplex method", Operations Research Letters 10(4)(1991) 189-192.
Ziegler, G.M., "Linear programming in oriented matroids", Technical Report No. 195, University of Augsburg, Germany, 1990.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
