×

zbMATH — the first resource for mathematics

Computational experience with a dual affine variant of Karmarkar’s method for linear programming. (English) Zbl 0627.90065
The purpose of this paper is to describe computational experience with a dual affine variant of Karmarkar’s method for solving linear programming problems. This approach was implemented by the authors over a twelve week period during the summer of 1986. Computational tests were made comparing this implementation with MINOS 5.0, a state-of-the-art implementation of the simplex method. Our implementation compares favorably on publicity- available linear programming test problems with an average speedup of about three over MINOS 5.0.

MSC:
90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
Software:
MINOS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, I.; Resende, M.G.C.; Veiga, G., An implementation of Karmarkar’s algorithm for linear programming, ()
[2] E.R. Barnes, personal communication, Sept. 1985.
[3] Barnes, E.R., A variation on Karmarkar’s algorithm for solving linear programming problems, IBM Watson research center report, (1986) · Zbl 0626.90052
[4] Bayers, D.A.; Lagarias, J.C., The nonlinear geometry of linear programming, I. affine and projective scaling trajectories, II. I egendre transform coordinates, III. central trajectories, ()
[5] Cavalier, T.M.; Soyster, A.L., Some computational experience and a modification of Karmarkar’s algorithm, ()
[6] Chen, S., Computational experience with the karmarkar algorithm, ()
[7] Gay, D.M., Electronic mail distribution of linear programming test problems, Mathematical programming society COAL newsletter, (Dec. 1985)
[8] Gill, P.E.; Murray, W.; Saunders, M.A.; Tomlin, J.A.; Wright, M.H., On projected Newton methods for linear programming and an equivalence to Karmarkar’s projective method, () · Zbl 0624.90062
[9] Golub, G.H.; Van Loan, C.F., Matrix computations, (1984), Johns Hopkins University Press Baltimore, MD
[10] Karmarkar, N.K., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[11] Karmarkar, N.K.; Ramakrishnan, K.G., Further developments in the new polynomial-time algorithm for linear programming, () · Zbl 0739.90042
[12] Monma, C.L., Recent breakthroughs in linear programming methods, ()
[13] Murtaugh, B.A.; Saunders, M.A., MINOS 5.0 User’s guide, ()
[14] Renegar, J., A polynomial-time algorithm, based on Newton’s method, for linear programming, () · Zbl 0618.65038
[15] Scientific Computing Associates, SMPAK User’s guide version 1.0, (1985)
[16] Sinha, L.P.; Freedman, B.A.; Karmarkar, N.K.; Putcha, A.; Ramakrishnan, K.G., Oversease network planning, ()
[17] Vanderbei, R.J.; Meketon, M.S.; Freedman, B.A., A modification of Karmarkar’s algorithm, () · Zbl 0626.90056
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.