Abstract
Many algorithms for solving linearly constrained optimization problems maintain sets of basic variables. The calculation of the initial basis is of great importance as it determines to a large extent the amount of computation that will then be required to solve the problem. In this paper, we suggest a number of simple methods for obtaining an initial basis and perform tests to indicate how they perform on a variety of real-life problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D.M. Carstens, “Crashing techniques,” in: W. Orchard-Hays,Advanced Linear-Programming Computing Techniques (McGraw-Hill, New York, 1968) pp. 131–139.
V. Chvátal,Linear Programming (Freeman, New York and San Francisco, 1983).
A.R. Curtis and J.K. Reid, “On the automatic scaling of matrices for Gaussian elimination,”Journal of the Institute of Mathematics and its Applications 10 (1972) 118–124.
G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NY, 1963).
J.J. Dongarra and E. Grosse, “Distribution of mathematical software via electronic mail,”Communications of the ACM 30 (1987) 403–407.
I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Oxford University Press, London, 1986).
A.M. Erisman, R.G. Grimes, J.G. Lewis and W.G. Poole Jr., “A structurally stable modification of Hellerman-Rarick's P4 algorithm for reordering unsymmetric sparse matrices,”SIAM Journal on Numerical Analysis 22 (1985) 369–385.
D.M. Gay, “Electronic mail distribution of linear programming test problems,”Mathematical Programming Society COAL Newsletter (December 1985).
N.E. Gibbs, “A hybrid profile reduction algorithm,”ACM Transactions on Mathematical Software 2 (1976) 378–387.
N.E. Gibbs, W.G. Poole Jr. and P.K. Stockmeyer, “An algorithm for reducing the bandwidth and profile of a sparse matrix,”SIAM Journal on Numerical Analysis 13 (1976) 236–250.
D. Goldfarb and J.K. Reid, “A practicable steepest-edge simplex algorithm,”Mathematical Programming 12 (1977) 361–371.
Harwell Subroutine Library, “A catalogue of subroutine,” Report R9185, HMSO (London, 1988).
J.G. Lewis, “Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King algorithms,”ACM Transactions on Mathematical Software 8 (1982) 180–194.
B.A. Murtagh,Advanced Linear Programming (McGraw-Hill, New York, 1981).
B.A. Murtagh and M.A. Saunders, “MINOS 5.1 User's guide,” Report SOL 83-20R, Department of Operations Research, Stanford University (Stanford, CA, 1987).
W. Orchard-Hays,Advanced Linear-Programming Computing Techniques (McGraw-Hill, New York, 1968).
C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982).
J.K. Reid, “A sparsity exploiting variant of the Bartels-Golub decomposition for linear programming bases,”Mathematical Programming 24 (1982) 55–69.
S.W. Sloan, “An algorithm for profile and wavefront reduction of sparse matrices,”International Journal for Numerical Methods in Engineering 23 (1986) 239–251.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gould, N.I.M., Reid, J.K. New crash procedures for large systems of linear constraints. Mathematical Programming 45, 475–501 (1989). https://doi.org/10.1007/BF01589115
Issue Date:
DOI: https://doi.org/10.1007/BF01589115