Preventing Degeneracy: The Complexity and Limitations of Lexicographic rule and Bland’ rule.

Résumé

Degeneracy and cycling present two of the most significant theoretical and practical hurdles in

Linear Programming (LP). They happen when the simplex algorithm gets stuck, wasting time without getting

close to an answer.

As artificial intelligence (IA) grow more complex, especially in areas like neural network verification and

safety certification, these mathematical roadblocks become more then just academic curiosities.

The represent real challenges that can prevent AI from finding optimal solution or guaranteeing safety.

This paper provides a comprehensive comparative analysis of two foundational classical approaches: Lex

icographic and Bland’s smallest index rules. Think of these as different traffic control systems designed to

prevent infinite loops in the mathematical journey toward the best solution while the methods provides the

rigorous mathematical guaranties needed for high stacks AI applications, our analysis reveals a trade-off: they

are like having a perfect but incredibly slow GPS it will get you there, but the journey might take forever.

The computational overhead makes them impractical for today’s massive high-dimensional AI problems.

This work lays the ground work for exploring more modern, efficient methods that can handle these

mathematical challenges without the heavy computational cost-essentially paving the way for traffic control

systems that work well even in today’s AI superhighways.