3
$\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?

Improve this question
$\endgroup$
1
  • $\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, 2016 at 15:11

1 Answer 1

Reset to default
2
$\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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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