×

zbMATH — the first resource for mathematics

Feasibility issues in a primal-dual interior-point method for linear programming. (English) Zbl 0726.90050
The author proposes a new method (based on the generic primal-dual algorithm) for obtaining an initial feasible interior-point solution to a linear program which avoids the use of a “big-\({\mathcal M}''\).
Reviewer: J.Rohn (Praha)

MSC:
90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
65K05 Numerical mathematical programming methods
Software:
symrcm; MINOS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar’s algorithm for linear programming,”Mathematical Programming 44 (1989) 297–336. · Zbl 0682.90061
[2] E. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1985) 174–182. · Zbl 0626.90052
[3] I.C. Choi, C.L. Monma and D.F. Shanno, ”Further development of a primal–dual interior point method,” manuscript, Columbia University (New York, NY, 1988), to appear in:ORSA Journal on Computing. · Zbl 0757.90051
[4] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[5] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[6] D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Mathematical Programming Society COAL Newsletter (December, 1985).
[7] J.A. George and J.W.H. Liu,Computer Solution of Large Sparse Positive Definite Systems (Prentice-Hall, Englewood Cliffs, NJ, 1981). · Zbl 0516.65010
[8] P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, ”On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method,”Mathematical Programming 36 (1986) 183–209. · Zbl 0624.90062
[9] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”A practical anti-cycling procedure for linearly constrained optimization,”Mathematical Progamming 45 (1990) 437–474. · Zbl 0688.90038
[10] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[11] M. Kojima, S. Mizuno and A. Yoshise, ”A primal–dual interior point algorithm for linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer, New York, 1988) pp. 29–48. · Zbl 0708.90049
[12] J.W.H. Liu, ”The multifrontal method and paging in sparse Cholesky factorization,” Technical Report CS-87-09, Department of Computer Science, York University (Downsview, Ontario, Canada, 1987a). · Zbl 0900.65062
[13] J.W.H. Liu, ”A collection of routines for an implementation of the multifrontal method,” Technical Report CS-87-10, Department of Computer Science, York University (Downsview, Ontario, Canada, 1987b).
[14] I.J. Lustig, ”A generic primal–dual interior point algorithm,” Technical Report SOR 88-3, Program in Statistics and Operations Research, Department of Civil Engineering and Operations Research, School of Engineering and Applied Science, Princeton University (Princeton, NJ, 1988).
[15] I.J. Lustig, ”An analysis of an available set of linear programming test problems,”Computers and Operations Research 16 (1989) 173–184. · Zbl 0661.90056
[16] K.A. McShane, C.L. Monma and D.F. Shanno, ”An implementation of a primal–dual interior point method for linear programming,”ORSA Journal on Computing 1 (1989) 70–83. · Zbl 0752.90047
[17] N. Megiddo, ”Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer, New York, 1988) pp. 131–158.
[18] C.L. Monma and A.J. Morton, ”Computational experience with a dual affine variant of Karmarkar’s method for linear programming,”Operations Research Letters 6 (1987) 261–267. · Zbl 0627.90065
[19] R.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms–Part I: linear programming,”Mathematical Programming 44 (1989) 27–42. · Zbl 0676.90038
[20] B.A. Murtagh and M.A. Saunders, MINOS 5.1 user’s guide, Technical Report SOL 83-20R, Department of Operations Research, Stanford University (Stanford, CA, 1987).
[21] R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”A modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–408. · 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.