Download PDF
ABSTRACT
Degeneracy is a fundamental feature of linear programming that can affect the behaviour of the Simplex Method without changing the feasible solution or objective value. Although degeneracy does not necessarily cause difficulties, a sequence of degenerate pivots may result in stalling and, under an unfortunate pivot-selection rule, cycling. This paper provides a theoretical and illustrative analysis of degeneracy, stalling, and cycling in the Simplex Method. The distinction between a degenerate basic feasible solution, a degenerate pivot, and a tied minimum-ratio test is first clarified through basic simplex formulations and an illustrative numerical example. A classical cycling example is then used to demonstrate how repeated zero-step pivots can return the algorithm to a previously visited basis. Several anti-cycling strategies are subsequently examined, including Bland’s rule, lexicographic pivoting, perturbation methods, and numerical safeguards. Particular attention is given to Bland’s rule and its finite-termination property. The paper also illustrates the relevance of degeneracy and anti-cycling procedures to structured linear programming applications. The analysis shows that degeneracy itself does not imply cycling; rather, cycling depends on the interaction between degeneracy and the pivot-selection rule. The study provides a concise theoretical framework for understanding these issues and highlights the importance of deterministic tie-breaking procedures in reliable implementations of the Simplex Method.
keyword Linear programming, Simplex Method, degeneracy, degenerate basic feasible solution, stalling, cycling, Bland’s rule, anti-cycling rules