A practical anti-cycling procedure for linearly constrained optimization

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

Research output: Contribution to journalArticlepeer-review


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
Issue number1-3
StatePublished - Aug 1989


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

ASJC Scopus subject areas

  • Software
  • General Mathematics


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

Cite this