A Primer on Karmarkar's Algorithm for Linear Programming

A new algorithm for solving linear programs has been proposed recently by N. Karmarkar. Instead of hopping from extreme point to extreme point along the boundary of the solution set, as the simplex method does, Karmarkar's algorithm cuts across the set of feasible solutions. As a solution procedure for solving very large-scale linear programming problems, the new algorithm shows great potential. In this paper, Karmarkar's algorithm is described. Also, although Karmarkar's paper does not provide any explicit discussion of duality, it is shown that in this algorithm dual variables and dual relations are alive and well. Finally the degeneracy and multiple optimal solution issues are discussed with respect to the new algorithm.