Accession Number:

ADA080837

Title:

Comments on Khachian's Algorithm for Linear Programming.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF SYSTEMS OPTIMIZATION LAB

Personal Author(s):

Report Date:

1979-11-01

Pagination or Media Count:

7.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE