×

zbMATH — the first resource for mathematics

Computational results of an interior point algorithm for large scale linear programming. (English) Zbl 0739.90042
Summary: This paper gives computational results for an efficient implementation of a variant of a dual projective algorithm for linear programming. The implementation uses the preconditioned conjugate gradient method for computing projections. Our computational experience reported in this paper indicates that this algorithm has potential as an alternative for solving very large LPs in which the direct methods fail due to memory and CPU time requirements. The conjugate gradient algorithm was able to find very accurate directions even when the system was ill-conditioned. The paper also discusses a new mathematical technique called the reciprocal estimates for estimating the primal variables. We have conducted extensive computational experiments on problems representative of large classes of applications of current interest. We have also chosen instances of the problems of future potential interest, which could not be solved in the past due to the weakness of the prior solution methods, but which represent a large class of new applications. The hypergraph model is such an example. Comparison of our implementation with MINOS 5.1 shows that our implementation is orders of magnitude faster than MINOS 5.1 for these problems.

MSC:
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Software:
KORBX; LSQR; LOLIB; MINOS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler, N.K. Karmarkar, M.G.C. Resende and G. Veiga, ”An implementation of Karmarkar algorithm for linear programming,”Mathematical Programming 44 (1989) 297–335. · Zbl 0682.90061
[2] I. Adler, N.K. Karmarkar, M.G.C. Resende and G. Veiga, ”Data structures and programming techniques for the implementation of Karmarkar’s algorithm,”ORSA Journal of Computing 1(2) (1989). · Zbl 0752.90043
[3] E.R. Barnes, S. Chopra and D.L. Jensen, ”A polynomial time version of the affine scaling algorithm,” Technical Report No. 88-101, Graduate School of Business Administration, New York University (Washington Square, NY, 1988).
[4] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming I, affine and projective scaling trajectories,”Transactions of the American Mathematical Society 314 (1989) 499–526. · Zbl 0671.90045
[5] C. Berge,Graphs and Hypergraphs (North-Holland, New York, 1973).
[6] T.M. Cavalier and A.L. Soyster, ”Some computational experience and a modification of the Karmarkar algorithm,” ISME Working Paper 85-105, The Pennsylvania State University (University Park, PA, 1985).
[7] Y.C. Cheng, D.J. Houck Jr., J.M. Liu, M.S. Meketon, L. Slutsman, R.J. Vanderbei and P. Wang, ”The AT&T KORBX(TM) system,”AT&T Technical Journal (1989).
[8] J.R. Daduna and A. Wren, eds.,Computer-Aided Transit-scheduling: Proceedings of the Fourth International Workshop on Computer-Aided Scheduling of Public Transport, Hamburg, Germany, 1987 (Springer, New York, 1988).
[9] J.E. Dennis Jr., A.M. Morshedi and K. Turner, ”A variable-metric variant of the Karmarkar algorithm for linear programming,”Mathematical Programming 39 (1987) 1–20. · Zbl 0635.90058
[10] I.I. Dikin, ”Iterative solution of problems in linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[11] I.I. Dikin, ”On the convergence of an iterative process,”Upravlyaeye Sistemi 12 (1974) 54–60. [In Russian.] · Zbl 0402.90059
[12] L.R. Ford Jr. and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, NJ, 1962). · Zbl 0106.34802
[13] O.L. Frost, ”Adaptive least squares optimization subject to linear equality constraints,” Ph.D. Thesis, Stanford University (Stanford, CA, 1970).
[14] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). · Zbl 0411.68039
[15] D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Mathematical Programming Society Committee on Algorithms Newsletter 13 (1985) 10–12.
[16] 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
[17] F. Glover, D. Karney and D. Klingmen, ”Implementation and computational comparisons of primal, dual, and primal–dual computer codes for minimum cost network flow problems,”Networks 4(3) (1974) 191–212. · Zbl 0282.68020
[18] D. Goldfarb and S. Mehrotra, ”Relaxed variants of Karmarkar’s algorithm for linear programs with unknown objective value,”Mathematical Programming 40 (1988) 183–195. · Zbl 0645.90048
[19] D. Goldfarb and S. Mehrotra, ”A relaxed version of Karmarkar’s method,”Mathematical Programming 40 (1988) 289–315. · Zbl 0654.90049
[20] G.H. Golub and C.F. Van Laon,Matrix Computations (The Johns Hopkins University Press, Baltimore, MD, 1989, 2nd ed.). · Zbl 0733.65016
[21] M. Grötschel, M. Jünger and G. Reinelt, ”Optimal triangulation of large real world input–output matrices,”Statistische Hefte 25 (1984) 261–295.
[22] M. Grötschel, M. Jünger and G. Reinelt, ”On the acyclic subgraph polytope,”Mathematical Programming 33 (1985) 28–42. · Zbl 0577.05034
[23] F.B. Hildebrand,Introduction to Numerical Analysis (McGraw-Hill, New York, 1974, 2nd ed.). · Zbl 0279.65001
[24] T. Kailath,Linear Systems (Prentice Hall, Englewood Cliffs, NJ, 1980). · Zbl 0454.93001
[25] N.K. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[26] N.K. Karmarkar and K.G. Ramakrishnan, ”Further developments in the new polynomial-time algorithm for linear programming,” Talk given atORSA/TIMS Conference (Boston, MA, 1985).
[27] N.K. Karmarkar and K.G. Ramakrishnan, ”Further developments in the new polynomial-time algorithm for linear programming,” Talk given at the12th International Symposium on Mathematical Programming (Boston, MA, 1985).
[28] N.K. Karmarkar and K.G. Ramakrishnan, ”Implementation and computational results of the Karmarkar algorithm for linear programming using an iterative method of computing projections,” AT&T Bell Laboratories Technical Memorandum No. 11211-891011-10TM (1989).
[29] N.K. Karmarkar and L.P. Sinha, ”Application of Karmarkar’s algorithm to overseas telecommunications facilities planning,” Talk given at the12th International Symposium on Mathematical Programming (Boston, MA, 1985).
[30] J.L. Kennington and R.V. Helgason,Algorithms for Network Programming (Wiley, New York, 1980). · Zbl 0502.90056
[31] L.G. Khachian, ”A polynomial time algorithm in linear programming,”Soviet Mathematics Doklady 20 (1979) 191–194.
[32] H.W. Kuhn and R.E. Quandt, ”An experimental study of the simplex method,” in: N.C. Metropolis et al., eds.,Experimental Arithmetic, High Speed Computing, and Mathematics, Proceedings of Symposia in Applied Mathematics XV i (American Mathematical Society, Providence, RI, 1963) pp. 107–124. · Zbl 0127.08203
[33] D.G. Luenberger,Linear and Nonlinear Programming (Addison-Wesley, Reading, MA, 1984, 2nd ed.). · Zbl 0571.90051
[34] I.J. Lustig, ”An analysis of available set of linear programming test problems,” Technical Report SOL 87-11, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1987). · Zbl 0662.57002
[35] I.J. Lustig, R.E. Marsten and D.F. Shanno, ”Computational experience with a primal–dual interior-point method for linear programming,” Technical Report SOR 89-17, Department of Civil Engineering and Operations Research, Princeton University (Princeton, NJ, 1989). · Zbl 0731.65049
[36] C.L. Monma and A.J. Morton, ”Computational experience with a dual variant of Karmarkar’s method for linear programming,”Operations Research Letters 6 (1987) 261–267. · Zbl 0627.90065
[37] B.A. Murtagh and M.A. Saunders, ”Minos 5.1 user’s guide,” Technical Report SOL 83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1983, revised 1987).
[38] C.C. Paige and M.A. Saunders, ”LSQR: An algorithm for sparse linear equations and sparse least squares,”ACM Transactions on Mathematical Software 8 (1982) 43–71. · Zbl 0478.65016
[39] M. Saunders, Private communication to David Gay (1988).
[40] Scientific Computing Associates,SMPAK User’s Guide Version 1.0 (1985).
[41] D. Shanno and C. Monma, ”Computational experience with the primal–dual method,” Talk presented at theORSA/TIMS Conference (Washington, DC, 1988).
[42] L.P. Sinha, B.A. Freedman, N.K. Karmarkar, A. Putcha and K.G. Ramakrishnan,Overseas Network Planning-Application of Karmarkar’s Algorithm, Proceedings of NETWORK’86 Conference (Tarpon Springs, FL, 1986).
[43] G. Strang and G.J. Fix,An Analysis of Finite Element Method (Prentice-Hall, Englewood Cliffs, NJ, 1973). · Zbl 0356.65096
[44] Ultrix-32 Programmer’s Manual, Digital Equipment Corporation (Mayward, MA, 1987).
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.