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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1979
Accession Number
ADA080837

Entities

People

  • George Bernard Dantzig

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Case Studies
  • Coefficients
  • Computer Programming
  • Computer Science
  • Electric Power
  • Equations
  • Heuristic Methods
  • Inequalities
  • Iterations
  • Linear Programming
  • New York
  • Operations Research
  • Polynomials
  • Simplex Method
  • United States
  • United States Government

Fields of Study

  • Mathematics

Readers

  • Fluid Dynamics.
  • Operations Research