A new polynomial-time algorithm for linear programming

Reviewer: Michael Todd

This paper describes a remarkable new polynomial algorithm for linear programming which has already elicited considerable publicity in the popular press, as well as among the operations research and computer science research communities, because of the striking claims made for its performance. Karmarkar has reported solving several large-scale problems by a factor of 50 times or more faster than those achieved by the simplex method, a practically very efficient (although exponential in the worst case) algorithm devised by Dantzig in 1947 [1]. I will comment further on computational issues below. In its basic form, Karmarkar's algorithm applies to problems in the form: minimize c Tx subject to Ax=0, &Sgr;x j=1 and x?, where it is assumed that A has full row rank, that a strictly positive feasible vector x 0 is known, and that the minimum value is zero. In this case, the algorithm generates a sequence of strictly positive feasible vectors whose objective function values decrease by a constant factor every n iterations, where n is the number of variables. This provides the polynomial time bound by rounding, as in the analysis by Gro¨tschel, Lova´sz, and Schrijver [2] of the ellipsoid method. The latter algorithm, originally developed for convex programming by Yudin and Nemirovski in the Soviet Union based on work by Shor, was shown to provide a polynomial algorithm for linear programming by Khachian in 1979 (see, e.g., [3]). There is a fascinating relationship between these two algorithms: while based on very different ideas, both generate a sequence of ellipsoids (in the ellipsoid algorithm containing, and in Karmarkar's method contained in, the feasible region), with each iteration implicitly solving a weighted least squares problem; both are intrinsically infinite iterative methods, though each can be truncated in a polynomial number of steps with relational data; and both use ideas of nonlinear programming more heavily than those of linear programming. The contrast in their significance is also noteworthy. The ellipsoid method appears not to be computationally efficient, but has been used theoretically by Gro¨tschel et al. [2] and others to prove that in a certain sense optimization is equivalent to separation, and thus establish the computational complexity of several combinatorial optimization problems. On the other hand, Karmarkar's algorithm, with its considerable computational promise, is apparently unable to provide such theoretical results since it cannot deal with an exponential number of implicit constraints. The ideas introduced by Karmarkar are also novel. He uses projective transformations to view each iteration as similar to the first (the ellipsoid method uses affine transformations analogously). The performance guarantee is provided by an auxiliary objective function, Karmarkar's potential function, which decreases by a constant at every iteration. The form of this function is reminiscent of logarithmic barrier functions in nonlinear programming. If one can solve in polynomial time linear programming problems in the canonical form above, one can similarly solve general problems. However, the transformation described by Karmarkar in Section 5 has a small gap, in that the transformed problem might have an optimal solution with the extra homogenizing variable x? n+1=0. In this case, the projective transformation cannot be inverted, or leads to a point at infinity. This could occur, for instance, if the original problem were: minimize x 1?x 2 subject to x 1?x 2? 1, ?x 1+x 2? 2, x 1, x:- 0I2?. The resulting canonical problem has an optimal solution x?=(1/2,1/2,0,...,0) T, with corresponding “point at infinity” x 1=x 2= ? y=u=v=0, &lgr;=0. Note that the original problem could have an optimal solution or be infeasible according to whether b 1+b 2 is nonpositive or positive respectively. I believe the problem can be fixed by perturbing b and c, but at a cost of an increased complexity bound. Finally, let me comment briefly on computational experience. A number of researchers have confirmed the very small number of iterations required by Karmarkar's algorithm (growing very slowly with n, if at all; indeed it seems that 30 iterations almost always suffice). However, at present only Karmarkar has been able to perform each iteration (basically a weighted least squares problem) fast enough to provide dramatic speedups compared to the simplex method.