  Motivated by the analysis of the performance of the simplex method we study
the behavior of families of pivot rules of linear programs. We introduce
normalized-weight pivot rules which are fundamental for the following reasons:
First, they are memory-less, in the sense that the pivots are governed by local
information encoded by an arborescence. Second, many of the most used pivot
rules belong to that class, and we show this subclass is critical for
understanding the complexity of all pivot rules. Finally, normalized-weight
pivot rules can be parametrized in a natural continuous manner.
  We show the existence of two polytopes, the pivot rule polytopes and the
neighbotopes, that capture the behavior of normalized-weight pivot rules on
polytopes and linear programs. We explain their face structure in terms of
multi-arborescences. We compute upper bounds on the number of coherent
arborescences, that is, vertices of our polytopes.
  Beyond optimization, our constructions provide new perspectives on classical
geometric combinatorics. We introduce a normalized-weight pivot rule, we call
the max-slope pivot rule which generalizes the shadow-vertex pivot rule. The
corresponding pivot rule polytopes and neighbotopes refine monotone path
polytopes of Billera--Sturmfels. Moreover special cases of our polytopes yield
permutahedra, associahedra, and multiplihedra. For the greatest improvement
pivot rules we draw connections to sweep polytopes and polymatroids.
