Resolving Degeneracy in Combinatorial Linear Programs: Steepest Edge, Steepest Ascent, and Closest Ascent.

摘要

While variants of the steepest edge pivoting rule are commonly used in linear programming codes they are not known to have the theoretically attractive property of avoiding an infinite sequence of pivots at points of degeneracy. A natural extension of the steepest edge pivoting rule based on steepest ascent is developed and shown to be provably finite. An alternative finite pivoting procedure that is computationally more attractive than steepest ascent is then introduced and it is argued that with probability 1 the procedure has the same computational requirements as steepest edge independent of the linear program being solved. Both procedures have the unique advantage that they choose the pivot element without explicit knowledge of the set of all active constraints at a point of degeneracy, thus making them attractive in combinatorial settings where the linear program is never explicitly written out.