A practical anti-cycling procedure for linearly constrained optimization

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

doi:10.1007/BF01589114

A practical anti-cycling procedure for linearly constrained optimization

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

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	437-474
Number of pages	38
Journal	Mathematical Programming
Volume	45
Issue number	1-3
DOIs	https://doi.org/10.1007/BF01589114
State	Published - Aug 1989

Keywords

Linear programming
active-set methods
cycling
degeneracy
simplex method

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1007/BF01589114

Cite this

@article{d44a650173c344679fc25d6a02306b2d,

title = "A practical anti-cycling procedure for linearly constrained optimization",

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.",

keywords = "Linear programming, active-set methods, cycling, degeneracy, simplex method",

author = "Gill, {Philip E.} and Walter Murray and Saunders, {Michael A.} and Wright, {Margaret H.}",

year = "1989",

month = aug,

doi = "10.1007/BF01589114",

language = "English (US)",

volume = "45",

pages = "437--474",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-3",

}

TY - JOUR

T1 - A practical anti-cycling procedure for linearly constrained optimization

AU - Gill, Philip E.

AU - Murray, Walter

AU - Saunders, Michael A.

AU - Wright, Margaret H.

PY - 1989/8

Y1 - 1989/8

N2 - 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.

AB - 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.

KW - Linear programming

KW - active-set methods

KW - cycling

KW - degeneracy

KW - simplex method

UR - http://www.scopus.com/inward/record.url?scp=0012489966&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0012489966&partnerID=8YFLogxK

U2 - 10.1007/BF01589114

DO - 10.1007/BF01589114

M3 - Article

AN - SCOPUS:0012489966

SN - 0025-5610

VL - 45

SP - 437

EP - 474

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-3

ER -

A practical anti-cycling procedure for linearly constrained optimization

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this