Antistalling Pivot Rule Bounding Degenerate Simplex Pivots in Linear Programming
A pivot rule for the simplex algorithm that uses any improving feasible direction at a degenerate extreme point to guarantee at most n-m-1 consecutive degenerate pivots, so the algorithm cannot stall indefinitely at one vertex. Students learn how a case distinction on the minimum-ratio test either pivots non-degenerately, shrinks the support of the guiding direction, or repairs that direction, and how the resulting bound combines with reduced-cost analyses to give strongly polynomial pivot counts for combinatorial linear programs such as matching, covering and flow formulations.
On the Number of Degenerate Simplex Pivots
The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) t…