Comments on Khachian's Algorithm for Linear Programming.
STANFORD UNIV CALIF SYSTEMS OPTIMIZATION LAB
Pagination or Media Count:
Khachians 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 Khachians method.
- Operations Research