ISSN:
1436-4646
Schlagwort(e):
Linear programming degeneracy
;
Pivot rules
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01585762
Permalink
