On The Polyhedral Geometry Of Pivot Rules

          @misc{ scivideos_18809,
            doi = {},
            url = {https://simons.berkeley.edu/talks/polyhedral-geometry-pivot-rules},
            author = {},
            keywords = {},
            language = {en},
            title = {On The Polyhedral Geometry Of Pivot Rules},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {dec},
            note = {18809 see, \url{https://scivideos.org/index.php/Simons-Institute/18809}}
          }
          

Abstract

Geometrically, a linear program is a polyhedron together with an orientation of its graph. A simplex method determines a path from any given starting vertex to the sink. The centerpiece of any simplex algorithm is the pivot rule that successively selects outgoing edges along the path. We introduce normalized-weight pivot rules, a class of pivot rules that are memory-less, that subsume many of the most-used pivot rules, and that can be parametrized in a natural continuous manner. We introduce two polytopes that capture the behavior of normalized-pivot rules on polytopes and linear programs. On the one hand, this gives a new perspective on the performance of pivot rules. On the other hand, our constructions generalize classical constructions (e.g. monotone path polytopes) and objects (e.g. permutahedra, associahedra, multiplihedra) from geometric combinatorics, This is joint work with Alex Black, Jesus De Loera, and Niklas Lütjeharms.