×

zbMATH — the first resource for mathematics

Computational experience with a primal-dual interior point method for linear programming. (English) Zbl 0731.65049
This important paper describes the heuristics and implementation details used in the code OB1, which implements a primal-dual interior point algorithm for linear programming. The algorithm is motivated in terms of the logarithmic barrier function, and the strategy for choosing the initial point and the heuristic for decreasing the barrier parameter are described. The authors discuss the main computational engine of the code, namely, the preconditioned conjugate gradient algorithm for solving the sparse linear system of equations that arises at each iteration. The preconditioner is of the incomplete Cholesky type, but special care is needed in handling columns of the constraint matrix which destroy the sparsity of the coefficient matrix. Computational comparisons with the MINOS simplex code are given for problems in the expanded netlib test set.
Reviewer: S.Wright (Argonne)

MSC:
65K05 Numerical mathematical programming methods
90C05 Linear programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, I.; Karmarkar, N.; Resende, M.G.C.; Veiga, G., An implementation of Karmarkar’s algorithm for linear programming, Math. programming, 44, 297-336, (1989) · Zbl 0682.90061
[2] Brearly, A.L.; Mitra, G.; Williams, H.P., Analysis of mathematical programming problems prior to applying the simplex method, Math. programming, 8, 54-83, (1975) · Zbl 0317.90037
[3] Choi, I.C.; Monna, C.L.; Shanno, D.F., Further development of a primal-dual interior point method, ORSA journal on computing, 2, 304-311, (1990) · Zbl 0757.90051
[4] Duff, I.S.; Erisman, A.M.; Reid, K.J., Direct methods for sparse matrices, (1986), Clarendon New York · Zbl 0604.65011
[5] Gay, D.M., Electronic mail distribution of linear programming test problems, Math. programming soc. COAL newsletter, (1985)
[6] Gill, P.E.; Murray, W.; Saunders, M.A., A single-phase dual barrier method for linear programming, () · Zbl 0815.65080
[7] Gonzaga, C.C., An algorithm for solving linear programming in O(n3L) operations, () · Zbl 1146.90038
[8] Kojima, M.; Mizuno, S.; Yoshise, A., A primal-dual interior point algorithm for linear programming, (), 29-48
[9] Liu, J.W.H., Modification of the minimum-degree algorithm by multiple elimination, ACM trans. math. software, 11, 141-153, (1985) · Zbl 0568.65015
[10] Lustig, I.J., Feasibility issues in an interior point method for linear programming, () · Zbl 0726.90050
[11] Lustig, I.J.; Mulvey, J.M.; Carpenter, T.J., The formulation of stochastic programs for interior methods, () · Zbl 0739.90048
[12] Marxen, A., Primal barrier methods for linear programming, ()
[13] Marsten, R.E.; Saltzman, M.J.; Shanno, D.F.; Pierce, G.S.; Ballintijn, J.F., Implementation of a dual affine interior point algorithm for linear programming, ORSA J. comput., 1, 287-297, (1988) · Zbl 0752.90046
[14] McShane, K.A.; Monma, C.L.; Shanno, D.F., An implementation of a primal-dual interior point method for linear programming, ORSA J. comput., 1, 70-83, (1989) · Zbl 0752.90047
[15] Megiddo, N., Pathways to the optimal set in linear programming, (), 131-158
[16] Monteiro, R.C.; Adler, I., Interior path following primal-dual algorithms. part I: linear programming, Math. programming, 44, 27-42, (1989) · Zbl 0676.90038
[17] Monteiro, R.D.C.; Adler, I.; Resende, M.G.C., A polynomial-time primal-dual affine scaling algorithm for linear and convex programming, and for power series extension, ()
[18] R.J. Vanderbei, Affine-scaling for linear programs with free variables, Math. Programming 43:31-44. · 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.