Solving staircase linear programs by the simplex method, 1: Inversion

Robert H Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or 'staircase', structure. The present paper looks at 'inversion' routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines 'pricing' routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.

Original languageEnglish (US)
Pages (from-to)274-313
Number of pages40
JournalMathematical Programming
Volume23
Issue number1
DOIs
StatePublished - Dec 1 1982

Keywords

  • Large-Scale Optimization
  • Linear Programming
  • Simplex Method
  • Staircase Linear Programs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Solving staircase linear programs by the simplex method, 1: Inversion'. Together they form a unique fingerprint.

Cite this