A practical anti-cycling procedure for linearly constrained optimization

Philip E. Gill, Walter Murray, Michael A. Saunders, Margaret H. Wright

Research output: Contribution to journalArticle

Abstract

A procedure is described for preventing cycling in active-set methods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a "working" feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and "stalling" cannot occur with exact arithmetic. The method appears to be reliable, based on computational results for the first 53 linear programming problems in the Netlib set.

Original languageEnglish (US)
Pages (from-to)437-474
Number of pages38
JournalMathematical Programming
Volume45
Issue number1-3
DOIs
StatePublished - Aug 1989

Keywords

  • Linear programming
  • active-set methods
  • cycling
  • degeneracy
  • simplex method

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A practical anti-cycling procedure for linearly constrained optimization'. Together they form a unique fingerprint.

  • Cite this