Resolving Degeneracy in Linear Programs: Steepest Edge, Steepest Ascent, and Closest Ascent
Boyd, E. Andrew
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 independentof 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.
Citable link to this pagehttps://hdl.handle.net/1911/101722
MetadataShow full item record
- CAAM Technical Reports