Narendra Karmarkar

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.