Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.