On the use of dense matrix techniques within sparse simplex. (English) Zbl 0784.90047

Summary: We discuss some instances where dense matrix techniques can be utilized within a sparse simplex linear programming solver. The main emphasis is on the use of the Schur complement matrix as a part of the basis matrix representation. This approach enables to represent the basis matrix as an easily invertible sparse matrix and one or more dense Schur complement matrices. We describe our variant of this method which uses updating of the QR factorization of the Schur complement matrix. We also discuss some implementation issues of the LP software package which is based on this approach.


90C05 Linear programming
Full Text: DOI


[1] L. Aittoniemi, Basis representation in large-scale linear programming software,Operations Research Proceedings 1988 (Springer, Berlin-Heidelberg-New York, 1989). · Zbl 0648.90052
[2] M. Benichou, J.M. Gauthier, G. Hentges and G. Ribi√®re, The efficient solution of large-scale linear programming problems-Some algorithmic techniques and computational results, Math. Progr. 13(1977)280–322. · Zbl 0384.90084
[3] J. Bischop and A. Meeraus, Matrix augmentation and partitioning in the updating of the basis inverse, Math. Progr. 13(1977)241–254. · Zbl 0372.90083
[4] T.F. Coleman,Large Sparse Numerical Optimization (Springer, Berlin-Heidelberg-Tokyo, 1984). · Zbl 0536.65047
[5] R.W. Cottle, Manifestations of the Schur complement, Lin. Alg. Appl. 8(1974)189–211. · Zbl 0284.15005
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, 1963).
[7] I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Clarendon Press, Oxford, 1989). · Zbl 0666.65024
[8] R. Fletcher and F.P.J. Matthews, Stable modification of explicit LU factors for simplex updates, Math. Progr. 30(1984)267–284. · Zbl 0574.65057
[9] J.J.H Forrest and J.A. Tomlin, Updated triangular factors of the basis to maintain sparsity in the product form simplex method, Math. Progr. 2(1972)263–278. · Zbl 0288.90048
[10] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, A practical anti-cycling procedure for linearly constrained optimization, Math. Progr. 45(1989)437–474. · Zbl 0688.90038
[11] G.H. Golub and C.F. Van Loan,Matrix Computations (Oxford Academic, London, 1986). · Zbl 1118.65316
[12] J. Gondzio, On exploiting original problem data in the inverse representation of linear programming bases, Report ZTSW-1-A1214/90, System Research Institute, Polish Academy of Sciences (1990), to appear in ORSA J. Comput. · Zbl 0806.90083
[13] J. Gondzio, Stable algorithm for updating dense LU factorization after row or column exchange and row and column addition or deletion, Optimization 23(1992)7–26. · Zbl 0814.65029
[14] F. Gustavson, Finding the block lower triangular form of a sparse matrix, in:Sparse Matrix Computations, eds. J.R. Bunch and D.J. Rose (Academic Press, New York, 1976) pp. 275–289. · Zbl 0344.65012
[15] E. Hellerman and D. Rarick, Reinversion with the preassigned pivot procedure, Math. Progr. 1(1971)195–216. · Zbl 0246.65022
[16] R.V. Helgason and J.L. Kennington, Spike swapping in basis reinversion, Naval Res. Log. Quarterly 27(1980)697–701. · Zbl 0447.90059
[17] R.V. Helgason and J.L. Kennington, A note on splitting the bump in an elimination factorization, Naval Res. Log. Quarterly 29(1982))169–178. · Zbl 0539.90070
[18] J.J. Judice, G. Mitra and M. Tamiz, A program to reorder and solve sparse unsymmetric linear systems using an envelope method, Technical Report/04/87, Dept. of Math. & Stats, Brunel University, UK.
[19] I.J. Lustig, An analysis of an available set of linear programming test problems, Comp. Oper. Res. 16(1989)173–184. · Zbl 0661.90056
[20] G. Mitra and M. Tamiz, Alternative methods for representing the inverse of linear programming basis matrices,13th Int. Symp. on Mathematical Programming, Tokyo (1988). · Zbl 0786.90041
[21] U.H. Suhl and L.M. Suhl, Computing sparse LU factorization for large-scale linear programming bases, ORSA J. Comput. 2(1990)325–335. · Zbl 0755.90059
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.