Complexity and Computability of Solutions to Linear Programming Systems.

Abstract

Complexity, computability and solution of linear programming systems are re-examined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems and alternate representations are reviewed. It is shown that the Klee-Minty example has never been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm is polynomial where (approximate) ellipsoidal 'centered-cut-off' algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. Both the Klee-Minty and the new J. Clausen example are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with an a priori regularization for linear programming systems. New polyhedral 'constraint contraction' algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1980
Accession Number
ADA084682

Entities

People

  • Abraham Charnes
  • M. Kress
  • S. Duffuaa
  • William W. Cooper

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Business Administration
  • Coefficients
  • Computations
  • Computer Programming
  • Computers
  • Convergence
  • Convex Programming
  • Ellipsoids
  • Equations
  • Geometric Programming
  • Geometry
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Operations Research