Comments on Khachian's Algorithm for Linear Programming.

Abstract

Khachian's polynomial bound for finding a feasible solution to a relaxed linear program is an important theoretical result. Unfortunately, a polynomial bound does not imply a good algorithm because such a bound could be too large for problems of practical interest. For example, using the formulae in the original paper, practical problems with 3000 non-negative variables and 1000 equations (which are solved under one-half hour on IBM 370-168 using the simplex method) would involve over 10 to 15th power iterations and would take 50,000,000 years to solve using Khachian's method.