A Steepest Feasible Direction Method for Linear Programming. Derivation and Embedding In the Simplex Method

• Autorzy: Biressaw C. Wolde , Torbjörn Larsson
• Języki publikacji: EN

Abstrakty

EN

A feasible direction method for linear programming has been proposed. The method is embedded in the framework of the simplex method, even though it works with non-edge feasible directions. The direction used is the steepest in the space of all variables or an approximation thereof, and it is found by solving a strictly convex quadratic program in the space of the nonbasic variables. Further, this program guarantees the feasibility of the direction even in the case of degeneracy. To remain within the simplex framework, the direction is represented by an auxiliary, or external, nonbasic column, which is a nonnegative linear combination of original nonbasic columns. We have made an experimental evaluation of the suggested method on both nondegenerate and highly degenerate problem instances. The overall results are very promising for continued research along this line, especially concerning various computational strategies that can be applied when the method is implemented. (original abstract)

Słowa kluczowe

EN

Operations research; Linear programming; Organizational research methods

PL

Badania operacyjne; Programowanie liniowe; Metody badania organizacji

• Czasopismo: Operations Research and Decisions
• Rocznik: 2024
• Tom: 34
• Numer: nr 2
• Strony: 163--182

Twórcy

autor

Biressaw C. Wolde

• Linköping University, Sweden

autor

Torbjörn Larsson

• Linköping University, Sweden

Bibliografia

• [1] Arsham, H. A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs. Applied Mathematics and Computation 188, 1 (2007), 596-611.
• [2] Bazaraa, M. S., Sherali, H. D., and Shetty, C. M. Nonlinear Programming: Theory and Algorithms. 3rd edition, John Wiley & Sons, 2006.
• [3] Beasley, J. E. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society 41, 11 (1990), 1069-1072.
• [4] Bertsekas, D. P. Projected Newton methods for optimization problems with simple constraints. SIAM Journal on Control and Optimization 20, 2 (1982), 221-246.
• [5] Borgwardt, K. H., and Huhn, P. A lower bound on the average number of pivot-steps for solving linear programs valid for all variants of the simplex-algorithm. Mathematical Methods of Operations Research 49 (1999), 175-210.
• [6] Eiselt, H. A., and Sandblom, C.-L. External pivoting in the simplex algorithm. Statistica Neerlandica 39, 4 (1985), 327-341.
• [7] Eiselt, H. A., and Sandblom, C.-L. Experiments with external pivoting. Computers and Operations Research 17, 4 (1990), 325-332.
• [8] Fathi, Y., and Murty, K. G. Computational behavior of a feasible direction method for linear programming. European Journal of Operational Research 40, 3 (1989), 322-328.
• [9] Forrest, J. J., and Goldfarb, D. Steepest-edge simplex algorithms for linear programming. Mathematical Programming 57, 1-3 (1992), 341-374.
• [10] Fukuda, K., and Terlaky, T. On the existence of a short admissible pivot sequence for feasibility and linear optimization problems. Pure Mathematics and Applications 10, 4 (1999), 431-447.
• [11] Goldfarb, D., and Reid, J. K. A practicable steepest-edge simplex algorithm. Mathematical Programming 12 (1977), 361-371.
• [12] Gondzio, J. Another simplex-type method for large scale linear programming. Control and Cybernetics 25, 4 (1996), 739-760.
• [13] Harris, P. M. J. Pivot selection methods of the Devex LP code. Mathematical Programming 5, 1 (1973), 1-28.
• [14] Klee, V., and Minty, G. J. How good is the simplex algorithm? In Inequalities III (1972), O. Shisha, Ed., Academic Press, pp. 159-175.
• [15] Larsson, T. On scaling linear programs-some experimental results. Optimization 27, 4 (1993), 355-373.
• [16] Maros, I. Computational Techniques of the Simplex Method. Kluwer Academic Publishers, 2003.
• [17] Mitra, G., Tamiz, M., and Yadegar, J. Experimental investigation of an interior search method within a simplex framework. Communications of the ACM 31, 12 (1988), 1474-1482.
• [18] Murty, K. G. Linear Programming. 2nd edition. Wiley, 1983.
• [19] Murty, K. G., and Fathi, Y. A feasible direction method for linear programming. Operations Research Letters 3, 3 (1984), 121-127.
• [20] Wolde, B. C., and Larsson, T. A steepest feasible direction extension of the simplex method. In Operations Research Proceedings 2019, Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Dresden, Germany, September 4-6, 2019 (Cham, 2020), J. S. Neufeld, U. Buscher, R. Lasch, D. Möst, and J. Schönberger, Eds., Springer, pp. 113-121.

Identyfikatory

DOI

10.37190/ord240210