An Implementation of Karmarkar's Algorithm for Linear Programming

This paper describes the implementation of variants of Karmarkar's algorithm for linear programming. These variants are members of a family of interior point algorithms resulting from approximations of a continuous version of Karmarkar's algorithm. Two algorithms based on first and second order approximations of the trajectory defined by the continuous algorithm are implemented and tested. Linear programs are expressed in an inequality form, that allows for the inexact computation of the algorithm's direction of improvement. This inequality form results 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.