UC Davis

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. The latter leads to 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 and compute upper bounds on the number of coherent arborescences, that is, vertices of our polytopes. We introduce a normalized-weight pivot rule, called the max-slope pivot rule, which generalizes the shadow-vertex pivot rule. The corresponding pivot rule polytopes and neighbotopes refine the monotone path polytopes of Billera and Sturmfels. Our constructions are important beyond optimization and provide new perspectives on classical geometric combinatorics. Special cases of our polytopes yield permutahedra, associahedra, and multiplihedra. For the greatest-improvement pivot rules we draw connections to sweep polytopes and polymatroids.