×

A basis-defiency-allowing variation of the simplex method for linear programming. (English) Zbl 0941.90055

Summary: As one of the most important and fundamental concepts in the simplex methodology, basis is restricted to being a square matrix of the order exactly equal to the number of rows of the coefficient matrix. Such inflexibility might have been the source of too many zero steps taken by the simplex method in solving real-world linear programming problems, which are usually highly degenerate. To dodge this difficulty, we first generalize the basis to allow the deficient case, characterized as one that has columns fewer than rows of the coefficient matrix. Variations of the primal and dual simplex procedures are then made, and used to form a two-phase method based on such a basis, the number of whose columns varies dynamically in the solution process. Generally speaking, the more degenerate a problem to be handled is, the fewer columns the basis will have; so, this renders the possibility of efficiently solving highly degenerate problems, We also provide a valuable insight into the distinctive and favorable behavior of the proposed method by reporting our computational experiments.

MSC:

90C05 Linear programming

Software:

SCICONIC; DEVEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dantzig, G. B., Programming in a linear structure, Comptroller (1948), USAF: USAF Washington, D.C
[2] Econometrica, 17, 3,4, 200-211 (1949) · Zbl 0037.37305
[3] Hoffman, A. J., Cycling in the simplex algorithm, (Report No. 2974 (1953), Nat. Bur. Standards: Nat. Bur. Standards Washington, D.C)
[4] Beale, E. M.L., Cycling in the dual simplex algorithm, Naval Research Logistics Quarterly, 2, 269-275 (1955) · Zbl 0068.13704
[5] Charnes, A., Optimality and degeneracy in linear programming, Econometrica, 20, 160-170 (1952) · Zbl 0049.37903
[6] Dantzig, G. B.; Orden, A.; Wolfe, P., The generalized simplex method for minimizing a linear form under linear inequality restraints, Pacific Journal of Mathematics, 5, 183-195 (1955) · Zbl 0064.39402
[7] Bland, R. G., New finite pivoting rules for the simplex method, Mathematics of Operations Research, 2, 103-107 (1977) · Zbl 0408.90050
[8] Harris, P. M.J., Pivot selection methods of the Devex LP code, Mathematical Programming Study, 4, 30-57 (1975) · Zbl 0395.90046
[9] Benichou, M.; Gauthier, J. M.; Hentges, G.; Ribiere, G., The efficient solution of linear programming problems—Some algorithmic techniques and computational results, Mathematical Programming, 13, 280-322 (1977) · Zbl 0384.90084
[10] Scicon, Sciconic/VM User Guide (1986), Scicon Limited: Scicon Limited Milton Keynes
[11] Hattersley, B.; Wilson, J., A dual approach to primal degeneracy, Mathematical Programming, 42, 135-145 (1988) · Zbl 0643.90053
[12] Gill, P. E.; Murray, W.; Saunders, M. A.; Wright, M. H., A practical anti-cycling procedure for linearly constrained optimization, Mathematical Programming, 45, 437-474 (1989) · Zbl 0688.90038
[13] Pan, P.-Q., Practical finite pivoting rules for the simplex method, Spektrum, 1, 219-225 (1990) · Zbl 0714.90063
[14] Pan, P.-Q., A dual projective simplex method for linear programming, Computers Math. Applic., 35, 6, 119-135 (1998) · Zbl 0907.90208
[15] Forrest, J. J.H.; Goldfarb, D., Steepest-edge simplex algorithms for linear programming, Mathematical Programming, 57, 341-374 (1992) · Zbl 0787.90047
[16] Gay, D. M., Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Newsletter, 13, 10-12 (1985)
[17] Bazaraa, M.; Jarvis, J. J., Linear Programming and Network Flows (1977), John Wiley & Sons: John Wiley & Sons New York · Zbl 1060.90688
[18] Chvatal, V., Linear Programming (1983), Freeman and Company: Freeman and Company San Francisco, CA · Zbl 0318.05002
[19] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[20] Fang, S.-C.; Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms (1993), Prentice Hall
[21] Gass, S. I., Linear Programming: Methods and Applications (1985), McGraw-Hill: McGraw-Hill New York · Zbl 0594.90052
[22] Goldfarb, D.; Reid, J. K., A practicable steepest-edge simplex algorithm, Mathematical Programming, 12, 361-371 (1977) · Zbl 0443.90058
[23] Goldfarb, D.; Todd, M. J., Linear programming, in optimization, (Nemhauser, G. L.; Kan, A. H.G. Rinnooy, Handbook in Operations Research and Management Science, Volume 1 (1989)), 73-170
[24] Golub, G. H.; Van Loan, C. F., Matrix Computations (1983), John Hopkins University Press: John Hopkins University Press Baltimore, MD · Zbl 0559.65011
[25] Greenberg, H.-J., Pivot selection tactics, (Greenberg, H. J., Design and Implementation of Optimization Software (1978), Sijthoff and Noordhoff), 109-143
[26] Luemberger, D., Introduction to Linear and Nonlinear Programming (1973), Addison-Wesley: Addison-Wesley Reading, MA
[27] Murty, K., Linear and Combinatorial Programming (1976), John Wiley & Sons: John Wiley & Sons New York · Zbl 0334.90032
[28] Orchard-Hayes, W., Background development and extensions of the revised simplex method, (Rand Report RM 1433 (1954), The Rand Corporation: The Rand Corporation Santa Monica, CA)
[29] Pan, P.-Q., A simplex-like method with bisection for linear programming, Optimization, 5, 717-743 (1991) · Zbl 0739.90043
[30] Pan, P.-Q., Ratio-test-free pivoting rules for a dual Phase-1 method, (Xiao, S.-T; Wu, F., Proceedings of the Third Conference of Chinese SIAM (1994), Tsinghua University Press: Tsinghua University Press Beijing), 245-249
[31] Pan, P.-Q., Achieving primal feasibility under the dual pivoting rule, Journal of Information & Optimization Sciences, 15, 3, 405-413 (1994)
[32] Pan, P.-Q., Composite phase-1 methods without measuring infeasibility, (Yue, M.-Y., Theory of Optimization and its Applications (1994), Xidian University Press: Xidian University Press Xian), 359-364
[33] Pan, P.-Q., New non-monotone procedures for achieving dual feasibility, Journal of Nanjing University, Mathematics Biquarterly, 12, 2, 155-162 (1995) · Zbl 0844.90055
[34] Pan, P.-Q., A modified bisection simplex method for linear programming, Journal of Computational Mathematics, 14, 3, 249-255 (1996) · Zbl 0856.65068
[35] Pan, P.-Q., The most-obtuse-angle row pivot rule for achieving dual feasibility: A computational study, European Journal of Operations Research, 101, 1, 167-176 (1997) · Zbl 0921.90119
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.