Simplex method rule helps avoid stalling moves in optimization
Escaping Degeneracy by Following Shadow Edges
Data Structures and Algorithms
Summary
In solving optimization problems with the Simplex method, a major slowdown happens when the algorithm gets stuck making moves that don't improve the solution, a situation called degeneracy. The authors prove there is a way to choose moves (called a pivot rule) that can avoid these unproductive steps and follow any path intended, using only a limited number of these stalling moves. This result improves the understanding of how the Simplex method behaves, especially for problems defined with 0/1 variables. Overall, it offers a way to make the search more efficient in certain linear programming problems.
What this means in practice
- •For operations research teams: Improve pivot selection in linear program solvers to reduce stalling steps when handling degenerate cases.
- •For financial analysts using optimization: Gain more predictable solving time for portfolio or risk models expressed as 0/1 linear programs by avoiding long degenerate sequences.
A theory result. No direct application yet.
Authors
Alexander E. Black, Sean Kafer, Laura Sanità
Abstract
The Simplex method is among the most widely used approaches for solving linear programs. Starting at a vertex solution of the feasible region, the algorithm proceeds through a sequence of basis exchanges (known as pivots), each corresponding to a move along an improving edge of the polyhedron toward a better vertex. A central challenge affecting the efficiency of the Simplex method is degeneracy, which can cause long sequences of pivot operations that fail to change the current vertex solution. In this paper, we prove the existence of a pivot rule which is able to escape degeneracy and follow any given shadow edge-direction when initialized at some compatible basis, with a linear number of degenerate Simplex pivots. As a byproduct of our result, we obtain an improved bound on the number of degenerate Simplex pivots needed to solve linear programs defined on 0/1 polytopes.