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

Robert H Fourer*

*Corresponding author for this work

Research output: Contribution to journalArticle

13 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 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
Volume25
Issue number3
DOIs
StatePublished - Oct 1 1983

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, 2: Pricing'. Together they form a unique fingerprint.

Cite this