ISSN:
1436-4646
Keywords:
Linear programming
;
simplex method
;
active-set methods
;
degeneracy
;
cycling
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 theNetlib set.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01589114
Permalink