An implementation of Karmarkar’s algorithm for linear programming. (English) Zbl 0682.90061

Adler, Ilan; Resende, Mauricio G. C.; Veiga, Geraldo; Karmarkar, Narendra

Math. Program., Ser. A 44, No. 3, 297-335 (1989).

Summary: This paper describes the implementation of power series dual affine scaling variants of Karmarkar’s algorithm for linear programming. Based on a continuous version of Karmarkar’s algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an equality form, which allows for the inexact computation of the algorithm’s direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex code MINOS 4.0.

MSC:

90C05	Linear programming
65K05	Numerical mathematical programming methods

Keywords:

interior point methods; power series dual affine scaling variants; Karmarkar’s algorithm; Implementation

Software:

MINOS; YSMP

References:

[1]	I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, ”Data structures and programming techniques for the implementation of Karmarkar’s algorithm,”ORSA Journal on Computing 1(2) (1989). · Zbl 0752.90043
[2]	I. Adler and R.C. Monteiro, ”Limiting behaviour of the affine-scaling continuous trajectories for linear programming problems,” Report ESRC 88-9, Engineering Systems Research Center, University of California (Berkeley, CA, 1988). · Zbl 0719.90044
[3]	A.I. Ali and J.L. Kennington, ”Mnetgn program documentation,” Technical Report IEOR 77003, Department of Industrial Engineering and Operations Research, Southern Methodist University (Dallas, TX, 1977).
[4]	J. Aronson, R. Barr, R. Helgason, J. Kennington, A. Loh and H. Zaki, ”The projective transformation algorithm by Karmarkar: A computational experiment with assignment problems,” Technical Report 85-OR-3, Department of Operations Research, Southern Methodist University (Dallas, TX, August 1985).
[5]	E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052 · doi:10.1007/BF02592024
[6]	D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming: I. Affine and projective rescaling trajectories,” to appear in Transactions of the AMS (1989). · Zbl 0671.90045
[7]	M.L. de Carvalho, ”On the work needed to factor a symmetric positive definite matrix,” Technical Report ORC 87-14, Operations Research Center, University of California (Berkeley, CA, 1987).
[8]	V. Chandru and B.S. Kochar, ”A class of algorithms for linear programming,” Research Memorandum 85-14, School of industrial Engineering, Purdue University (West Lafayette, IN, 1986).
[9]	I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[10]	J.J. Dongarra and E. Grosse, ”Distribution of mathematical software via electronic mail,”Communications of the ACM 30 (1987) 403–414. · doi:10.1145/22899.22904
[11]	I.S. Duff, A.M. Erisman and J.K. Reid,Direct Methods for Sparse Matrices (Claredon Press, Oxford, 1986). · Zbl 0604.65011
[12]	S.C. Eisenstat, M.C. Gurshy, M.H. Schultz and A.H. Sherman, ”The Yale sparse matrix package, I. The symmetric codes,”International Journal of Numerical Methods in Engineering 18 (1982) 1145–1151. · Zbl 0492.65012 · doi:10.1002/nme.1620180804
[13]	D.M. Gay, ”Electronic mail distribution of linear programming test problems,”Mathematical Programming Society Committee on Algorithms Newsletter 13 (December 1985) 10–12.
[14]	D.M. Gay, ”Electronic mail distribution of linear programming test problems,” Numerical Analysis Manuscript 86-0, AT&T Bell Laboratories (Murray Hill, NJ, 1986).
[15]	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 · doi:10.1007/BF02592025
[16]	C. Gonzaga, ”Interior point algorithms for linear programming problems with inequality constraints,” Report ES-140/88, COPPE-Federal University of Rio de Janeiro (Rio de Janeiro, Brazil, 1988).
[17]	J.K. Ho and E. Loute, ”A set of staircase linear programming test problems,”Mathematical Programming 20 (1981) 245–250. · Zbl 0448.90036 · doi:10.1007/BF01589349
[18]	J.H. Hooker, ”Karmarkar’s linear programming algorithm,”Interfaces 16 (1986) 75–90. · doi:10.1287/inte.16.4.75
[19]	K.N. Johnson, ”Forplan version 1: An overview,” Technical Report, Land Management Planning-System Section, USDA, Forest Service (Fort Collins, CO, 1986).
[20]	N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[21]	N. Karmarkar, J. Lagarias, L. Slutsman and P. Wang, ”Power series variants of Karmarkar type algorithms,” Technical Report, AT&T Bell Laboratories (Murray Hill, NJ, 1989). · Zbl 0682.90060
[22]	J. Kennington, ”A primal partitioning code for solving multicommodity flow problems (version 1),” Technical Report 79008, Department of Industrial Engineering and Operations Research, Southern Methodist University (Dallas, TX, 1979).
[23]	I.J. Lustig, ”A practical approach to Karmarkar’s algorithm,” Technical Report SOL 85-5, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1985).
[24]	N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms for linear programming,” IBM Research Report RJ5319, Almadén Research Center (San Jose, CA, 1986). · Zbl 0675.90050
[25]	B.A. Murtagh and M.A. Saunders, ”Minos user’s guide,” Technical Report 77-9, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1977).
[26]	B.A. Murtagh and M.A. Saunders, ”Minos 5.0 user’s guide,” Technical Report 83-20, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1983).
[27]	D.J. Rose, ”A graph-theoretical study of the numerical solution of sparse positive definite systems of linear equations,” in: R.C. Read, ed.,Graph Theory and Computing (Academic Press, New York, 1972) pp. 183–217.
[28]	R.E. Tarjan,Data Structures and Network Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983). · Zbl 0584.68077
[29]	M.J. Todd and B.P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424. · Zbl 0621.90048 · doi:10.1007/BF01840455
[30]	J.A. Tomlin, ”An experimental approach to Karmarkar’s projective method for linear programming,” Manuscript, Ketron, Inc. (Mountain View, CA, 1985). · Zbl 0634.90044
[31]	K. Tone, ”An implementation of a revised Karmarkar method,” Interim Report, Graduate School for Policy Science, Saitama University (Urawa, Saitama 338, Japan, 1986).
[32]	R.J. Vanderbei, M.J. Meketon and B.A. Freedman, ”A modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–407. · Zbl 0626.90056 · doi:10.1007/BF01840454
[33]	M. Yannakakis, ”Computing the minimum fill-in is NP-complete,”SIAM Journal on Algebraic and Discrete Methods 2 (1981) 77–79. · Zbl 0496.68033 · doi:10.1137/0602010