Understanding Degeneracy in Linear Programming: Implications and Cycles

Linear programming is a versatile optimization technique widely used in various domains ranging from econometrics to production planning. One of the intricate aspects of linear programming is degeneracy, which can significantly impact the efficiency and accuracy of solutions obtained through the simplex algorithm. This article delves into the concept of degeneracy, its implications, and the phenomenon of cycling.

What is Degeneracy in Linear Programming?

Degeneracy in a linear programming problem occurs when a basic feasible solution contains a smaller number of non-zero variables than the number of independent constraints, or when the replacement ratio is the same for some variables. This situation often arises when one or more of the basic variables have a value of zero.

Formally, a basic feasible solution is degenerate if it has one or more basic variables that are zero. For a given linear programming problem, the number of independent constraints should correspond to the number of non-zero basic variables. If a basic variable is zero, it does not contribute to the reduction in the objective function, leading to a degenerate solution.

Causes and Consequences of Degeneracy

The primary cause of degeneracy is the presence of linearly dependent constraints, or redundant variables, in the problem. These constraints or variables do not contribute to the feasible region's defining boundaries in a meaningful way. When such variables are present, the simplex algorithm might converge to a basic feasible solution with more zero-valued variables than the number of independent constraints. This situation can lead to undesirable outcomes, including cycles and computational inefficiencies.

The consequence of degeneracy can be particularly severe when the simplex algorithm is applied. If there is a tie for the minimum ratio in the minimum ratio test during a pivot operation, the decision of which leaving variable to select becomes arbitrary. This arbitrariness can lead to the simplex algorithm cycling, a situation where the algorithm keeps iterating through previous solutions without ever reaching an optimal solution. This cycling can cause significant computational burdens, as the algorithm may continue to loop through the same iterations infinitely.

Addressing Degeneracy: Techniques and Preventive Measures

There are several techniques and preventive measures that can help address the issue of degeneracy and prevent cycling. These include:

Bland's Rule: Bland's rule is a strategy to eliminate the possibility of cycling. It stipulates that when there is a tie for the minimum ratio, the variable entering the basis is chosen with the smallest index. This simple addition ensures that the algorithm does not cycle indefinitely.E-Nearest Neighbor Selection: This method involves slightly perturbing the objective function or the constraints to break ties and ensure a unique selection of the entering and leaving variables. This approach can help avoid the arbitrary selection that leads to cycling.Leaving Variable Selection: Maintaining a carefully chosen order of leaving variables can also prevent cycling. By choosing the leaving variable based on a predefined sequence, one can ensure that the algorithm converges efficiently.

Conclusion

The concept of degeneracy in linear programming plays a critical role in understanding the robustness of optimization algorithms. The presence of degenerate solutions and the potential for cycling highlight the importance of implementing appropriate measures to ensure the efficient and accurate resolution of linear programming problems. By leveraging strategies such as Bland's rule, E-nearest neighbor selection, and thoughtful leaving variable selection, one can effectively mitigate the risks associated with degeneracy and achieve optimal solutions.