Solving staircase linear programs by the simplex method, 2: Pricing

Robert Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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 preceding paper considered 'inversion' routines that factorize the basis and solve linear systems. The present paper examines 'pricing' routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.

Original languageEnglish (US)
Pages (from-to)251-292
Number of pages42
JournalMathematical Programming
Issue number3
StatePublished - Oct 1983


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

ASJC Scopus subject areas

  • Software
  • General Mathematics


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

Cite this