×

zbMATH — the first resource for mathematics

The role of the augmented system in interior point methods. (English) Zbl 0943.90069
Summary: The authors present a way to use the augmented system approach in interior point methods. They elaborate on the increased freedom in determining the pivot order which makes this approach computationally very competitive. This means that with the pivot search heuristics presented here, in most of the cases they can achieve a performance not worse than the \(AD^{-1}A^T\) method, and in several cases much better. In reality, the augmented system seems to be the only safe method in case of dense columns or ‘bad’ nonzero pattern. They found that both methods are important for their usefulness. Their implementation includes both. It is also equipped with an analyzer that is able to determine which of them to use. It is based on the evaluation of the nonzero pattern of the constraint matrix. They also point out that the treatment of free variables is also more efficient in the framework of the augmented system. They report on some very favorable computational experiences achieved with their implementation of the augmented system based on these ideas.

MSC:
90C51 Interior-point methods
Software:
ALPO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arioli, M.; Duff, I.S.; Rijk, P.P.M., On the augmented system approach to sparse least-squares problems, Numerische Mathematik, 55, 667-684, (1989) · Zbl 0678.65024
[2] Birge, J.R.; Freund, R.M.; Vanderbei, R.J., Prior reduced fillin solving equations in interior point algorithms, Operations research letters, 11, 195-198, (1992) · Zbl 0767.90044
[3] Bixby, R.E., Progress in linear programming, ORSA journal on computing, 6, 1, 15-22, (1994) · Zbl 0798.90101
[4] Duff, I.; Gould, N.I.M.; Reid, J.; Scott, J.A.; Turner, K., The factorization of sparse symmetric indefinite matrices, IMA journal of numerical analysis, 11, 181-204, (1991) · Zbl 0739.65018
[5] Fourer, R.; Mehrotra, S., Solving symmetric indefinite systems in an interior point method for linear programming, Mathematical programming, 62, 15-39, (1993) · Zbl 0802.90069
[6] Gay, D.M., Electronic mail distribution of linear programming test problems, Mathematical programming society COAL newsletter, 13, 10-12, (1985)
[7] Gondzio, J., Splitting dense columns of constraint matrix in interior point methods for large scale linear programming, Optimization, 24, 285-297, (1992) · Zbl 0814.65056
[8] Gonzaga, C.G., Path following methods for linear programming, SIAM review, 34, 2, 167-227, (1992) · Zbl 0763.90063
[9] Hafsteinsson, H.; Levkovitz, R.; Mitra, G., Solving large scale linear programming problems using an interior point method on a massively parallel SIMD computer, Journal of parallel algorithms and applications, 4, 3&4, 301-316, (1994) · Zbl 1049.65537
[10] Hurd, J.K.; Murphy, F.H., Exploiting special structure in primal dual interior point methods, ORSA journal on computing, 4, 1, 38-44, (1992) · Zbl 0770.90042
[11] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., Computational experience with a primal-dual interior point method for linear programming, Linear algebra and its applications, 152, 191-222, (1991) · Zbl 0731.65049
[12] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., On implementing Mehrotra’s predictor-corrector interior point method for linear programming, SIAM journal on optimization, 2, 435-449, (1992) · Zbl 0771.90066
[13] Lustig, I.J.; Marsten, R.E.; Shanno, D.F., Interior point methods for linear programming: computational state of the art, ORSA journal on computing, 6, 1, 1-14, (1994) · Zbl 0798.90100
[14] Maros, I.; Mitra, G., Simplex algorithms, (), 1-46 · Zbl 0906.90122
[15] Marsten, R.E.; Saltzman, M.J.; Shanno, D.F.; Ballantijn, J.F.; Pierce, G.S., Implementation of a dual affine interior point algorithm for linear programming, ORSA journal on computing, 1, 287-297, (1989) · Zbl 0752.90046
[16] Mehrotra, S., Handling free variables in interior methods, ()
[17] Meszaros, Cs., Fast Cholesky factorization for interior point methods of linear programming, () · Zbl 0879.90143
[18] Mitra, G.; Levkovitz, R., Solution of large linear programs: a review of hardware, software and algorithmic issues, (), 139-171
[19] Saunders, M.A., Major Cholesky would feel proud, ORSA journal on computing, 6, 1, 23-27, (1994) · Zbl 0800.90698
[20] Stewart, G.W., Modifying pivot elements in Gaussian elimination, Mathematics of computation, 28, 537, (1974) · Zbl 0293.65015
[21] Todd, M.J., Exploiting special structure in Karmarkar’s linear programming algorithm, Mathematical programming, 41, 81-103, (1988)
[22] Turner, K., Computing projections for the karmarkar algorithm, Linear algebra and its applications, 152, 141-154, (1991) · Zbl 0729.65043
[23] Vanderbei, R.J., ALPO: another linear program optimizer, ORSA journal on computing, 3, 2, 134-146, (1993) · Zbl 0777.90031
[24] Vanderbei, R.J.; Meketon, M.S.; Freedman, B.F., A modification of Karmarkar’s linear programming algorithm, Algorithmica, 1, 395-407, (1986) · Zbl 0626.90056
[25] Vanderbei, R.J.; Carpenter, T.J., Symmetric indefinite systems for interior point methods, Mathematical programming, 58, 1-32, (1993) · Zbl 0791.90033
[26] Vanderbei, R.J., Interior-point methods: algorithms and formulations, ORSA journal on computing, 6, 1, 32-34, (1994) · Zbl 0800.90697
[27] Vanderbei, R.J., Affine scaling for linear programs with free variables, Mathematical programming, 43, 31-44, (1989) · Zbl 0825.90681
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.