Parametric linear programming and anti-cycling pivoting rules (Q1108192): Difference between revisions

It is well-known that in the presence of degeneracy in linear programming the simplex procedure may select a sequence of admissible bases that cycles. The perturbation method avoids cycling by refining the selection rule for the exiting variable while the combinatorial rule avoids cycling by refining the selection rule for both the exiting and entering variables. This raises the following question answered affirmatively by the authors. Is there a simplex pivoting procedure for avoiding cycling that does not restrict the minimum ratio rule choice of exiting variables? In this paper the authors describe an anti-cycling rule that avoids cycling by refining the selection rule for only the entering variable. The authors have also described a dual pivoting procedure that avoids cycling by refining only the choice of exiting variables.