A Strictly Improving Phase 1 Algorithm Using Least-Squares Subproblems

Abstract

Although the simplex method's performance in solving linear programming problems is usually quite good, it does not guarantee strict improvement at each iteration on degenerate problems. Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do) , we have developed a new Phase I algorithm that is completely impervious to degeneracy, with strict improvement attained at each iteration. it is also noted that the new Phase I algorithm is closely related to a number of existing algorithms. When tested on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3. 5 times faster than the simplex method; on some problems, it was over 10 times faster.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1992
Accession Number
ADA251913

Entities

People

  • G. B. Dantzig
  • J. W. Davis
  • S. A. Leichner

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Computations
  • Computer Programming
  • Errors
  • Iterations
  • Linear Programming
  • Numbers
  • Operations Research
  • Optimization
  • Quadratic Programming
  • Residuals
  • Simplex Method
  • Sparse Matrix
  • United States

Readers

  • Linear Algebra
  • Software Engineering.
  • Systems Analysis and Design