ISSN:
1436-4646
Keywords:
Linear programming degeneracy
;
Pivot rules
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract While variants of the steepest edge pivot 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. An example is presented demonstrating that the steepest edge pivot rule can fail to terminate finitely. It is then shown that a natural extension of the steepest edge pivot rule based on steepest ascent is guaranteed to determine a direction of ascent or a proof that no such direction exists after a finite number of pivots, although without modification the extension may not terminate with an ascent direction corresponding to an edge. Finally, it is demonstrated that a computationally more efficient pivot rule proposed by Magnanti and Orlin has similar theoretical properties to steepest ascent with probability 1independent of the linear program being solved. Unlike alternative methods such as primal lexicographic rules and Bland's rule, the algorithms described here have the 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 represented implicitly.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585762
Permalink