# Karmarkar Algorithm Assignment

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).Google Scholar

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).Google Scholar

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).Google Scholar

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).Google Scholar

E.R. Barnes, “A variation on Karmarkar's algorithm for solving linear programming problems,”*Mathematical Programming* 36 (1986) 174–182.Google Scholar

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).Google Scholar

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).Google Scholar

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).Google Scholar

I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”*Soviet Mathematics Doklady* 8 (1967) 674–675.Google Scholar

J.J. Dongarra and E. Grosse, “Distribution of mathematical software via electronic mail,”*Communications of the ACM* 30 (1987) 403–414.Google Scholar

I.S. Duff, A.M. Erisman and J.K. Reid,*Direct Methods for Sparse Matrices* (Claredon Press, Oxford, 1986).Google Scholar

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.Google Scholar

D.M. Gay, “Electronic mail distribution of linear programming test problems,”*Mathematical Programming Society Committee on Algorithms Newsletter* 13 (December 1985) 10–12.Google Scholar

D.M. Gay, “Electronic mail distribution of linear programming test problems,” Numerical Analysis Manuscript 86-0, AT&T Bell Laboratories (Murray Hill, NJ, 1986).Google Scholar

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.Google Scholar

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).Google Scholar

J.K. Ho and E. Loute, “A set of staircase linear programming test problems,”*Mathematical Programming* 20 (1981) 245–250.Google Scholar

J.H. Hooker, “Karmarkar's linear programming algorithm,”*Interfaces* 16 (1986) 75–90.Google Scholar

K.N. Johnson, “Forplan version 1: An overview,” Technical Report, Land Management Planning-System Section, USDA, Forest Service (Fort Collins, CO, 1986).Google Scholar

N. Karmarkar, “A new polynomial-time algorithm for linear programming,”*Combinatorica* 4 (1984) 373–395.Google Scholar

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).Google Scholar

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).Google Scholar

I.J. Lustig, “A practical approach to Karmarkar's algorithm,” Technical Report SOL 85-5, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1985).Google Scholar

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).Google Scholar

B.A. Murtagh and M.A. Saunders, “Minos user's guide,” Technical Report 77-9, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1977).Google Scholar

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).Google Scholar

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.Google Scholar

R.E. Tarjan,*Data Structures and Network Algorithms* (Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983).Google Scholar

M.J. Todd and B.P. Burrell, “An extension of Karmarkar's algorithm for linear programming using dual variables,”*Algorithmica* 1 (1986) 409–424.Google Scholar

J.A. Tomlin, “An experimental approach to Karmarkar's projective method for linear programming,” Manuscript, Ketron, Inc. (Mountain View, CA, 1985).Google Scholar

K. Tone, “An implementation of a revised Karmarkar method,” Interim Report, Graduate School for Policy Science, Saitama University (Urawa, Saitama 338, Japan, 1986).Google Scholar

R.J. Vanderbei, M.J. Meketon and B.A. Freedman, “A modification of Karmarkar's linear programming algorithm,”*Algorithmica* 1 (1986) 395–407.Google Scholar

M. Yannakakis, “Computing the minimum fill-in is NP-complete,”*SIAM Journal on Algebraic and Discrete Methods* 2 (1981) 77–79.Google Scholar

Narendra Karmarkar is being recognized for his theoretical work in devising an Interior Point method for linear programming that provably runs in polynomial time, and for his implementation work suggesting that Interior Point methods could be effective for linear programming in practice as well as theory.

In the linear programming problem, we wish to maximize a linear objective function subject to a collection of linear inequalities on the variables. Linear programs model a wide variety of optimization problems in science, business, and industry. Their modeling value was recognized by the 1975 Nobel Prize in Economics, given to Kantorovich and Koopmans for their early work in this area. Until Karmarkar's work, the main workhorse for solving linear programs was the "Simplex" method of Dantzig, which seemed to work well in practice, but which could be shown to take exponential time on certain specially-constructed instances. In 1979, Khachian showed that the "Ellipsoid" method could solve linear programs in polynomially-bounded time, although this was primarily a theoretical advance since experiments revealed that in practice it was much slower than Simplex.

In a tour-de-force of algorithm design, Karmarkar in 1984 showed that a third approach, the "Interior Point" method, could also solve linear programs in polynomial time. Following the appearance of this result, researchers in nonlinear programming were able to place his in the context of earlier "barrier" methods. However almost everything had to be done just the way that Karmarkar invented if a polynomial bound was to be obtained. The running time bound proved by Karmarkar was also a significant improvement over that for Khachian's algorithm, but was still much slower than the average running time growth rates reported for the Simplex method in practice. Thus Karmarkar's result might have languished as another "merely theoretical" advance, had not Karmarkar also undertaken the job of implementing and testing his algorithm and variants of it. His initial experiments suggested that Interior Point methods were in fact not only competitive with Simplex methods, but could solve much bigger problems than were previously thought possible.

This initial work by Karmakar inspired a renaissance in the theory and practice of linear programming. Although his empirical results were first greeted with skepticism, soon a large number of researchers were able to duplicate these successes and began to develop extensions to his original method. Today, Interior Point methods are an essential tool for solving large scale linear programming problems and are included in all major commercial linear programming packages. They are currently the only way to solve a variety of very large linear programs, such as ones modeling global supply chains in the semiconductor industry and fleet assignment in the airline industry. The ability to optimize the latter can save hundreds of millions of dollars. Interestingly, the new levels of performance possible with Interior Point methods inspired researchers to improve and extend the Simplex method as well, so that today it is often still the algorithm of choice. The competition between the two approaches has definitely been good for the field. It is estimated that today's algorithms are perhaps 3 orders of magnitude faster than were the algorithms before Karmarkar's results. Combined with improvements in machine speed, that translates to approximately 6 orders of magnitude in total. Thus, on average, problems that took 10 days to solve 15 years ago, now take under 1 second.

Without Karmarkar's contribution, this might not have happened, and certainly wouldn't have happened so quickly. For this, and the parallel impact his work has had on the theory of mathematical programming, he is recognized with the 2000 Kanellakis Award.

## Comments