<p>A starting point might be this survey:</p>

<p>T. Terlaky and S. Zhang, "<a href="http://link.springer.com/article/10.1007%2FBF02096264" rel="nofollow">Pivot Rules for Linear Programming:A Survey on Recent Theoretical Developments</a>", Annals of Operations Research, 46, 203 - 233, 1993.(Technical Report, <a href="http://www.menet.umn.edu/~zhangs/Reports/1993_TZ.pdf" rel="nofollow">pdf</a>)</p>

CC BY-SA 3.0
2016-07-19T17:58:27.070Z
2016-07-19T17:58:27.070Z
David Clark
<p>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.</p>

<p>But I have not encountered a <strong>comprehensive, systematic list</strong> 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. </p>

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

CC BY-SA 3.0
2016-07-21T15:11:48.903Z
Although it's not a new pivot rule, you might find this interesting: http://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.
Joshua Grochow
<ds.algorithms><reference-request><linear-programming>
List of Pivot rules for simplex methods
shuhalo
# List of Pivot rules for simplex methods

(Asked by: username_0 on 2016-07-13)

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?

**Tags:** ds.algorithms, reference-request, linear-programming

> **Comments:**
> **username_1**: Although it's not a new pivot rule, you might find this interesting: http://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.  

---

## 1 answers

### Answer by username_2 on 2016-07-19. Score: 2

A starting point might be this survey:

T. Terlaky and S. Zhang, "[Pivot Rules for Linear Programming:A Survey on Recent Theoretical Developments](http://link.springer.com/article/10.1007%2FBF02096264)", Annals of Operations Research, 46, 203 - 233, 1993.(Technical Report, [pdf](http://www.menet.umn.edu/~zhangs/Reports/1993_TZ.pdf))


---

