2
$\begingroup$

Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed throughout the years.

But I have not encountered a comprehensive, systematic list of pivot rules in literature. Though comprehensiveness might be infeasible, one could hope for a list that at least contains rules that have been researched attention and discussion in the scientific community.

Do you know about such a list? Conversely, what prevents people from assembling such a list or survey?

$\endgroup$
  • $\begingroup$ Although it's not a new pivot rule, you might find this interesting: arxiv.org/abs/1311.5935. It sheds some light on why certain pivot rules take exponential time, namely that executing the pivot rule itself (rather than just the output of the simplex algorithm) is solving an NP-hard problem. $\endgroup$ – Joshua Grochow Jul 21 '16 at 15:11
1
$\begingroup$

A starting point might be this survey:

T. Terlaky and S. Zhang, "Pivot Rules for Linear Programming:A Survey on Recent Theoretical Developments", Annals of Operations Research, 46, 203 - 233, 1993.(Technical Report, pdf)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.