Content area
A foundational problem in optimization is that of linear programming, the problem of maximizing a linear function c ⊺x subject to linear inequality constraints Ax ≤ b. Geometrically, this problem corresponds to finding the highest point in some direction on a polytope. The simplex method, one of the oldest and most famous algorithms for linear programming, does this by following a path on the graph of the polytope such that at each step the linear objective function value increases. Such a path is called a monotone path. The simplex method could potentially follow any monotone path on the polytope. For implementation, one must specify a rule to choose such a path called a pivot rule. The goal of this thesis is to study the geometric combinatorics of monotone paths and pivot rules for linear programs and bound the performance of the simplex method.
We first show performance bounds for the simplex method in the case of 0/1-polytopes. In this case, we introduce two pivot rules guaranteed to follow paths of length at most the dimension of the polytope matching optimal bounds of Naddef. We extend these results to d-dimensional (0, k)-lattice polytopes finding a path following algorithm using the simplex method as a subroutine guaranteed to follow a path of length at most 2dk asymptotically matching the best known bounds on diameters of their graphs due to Kleinschmidt and Onn and improving upon the best known bounds in this framework due to Del Pia and Michini. It remains open whether there is a pivot rule for the simplex method that guarantees even a polynomial in d and k many steps.
In the remainder of this thesis, we study two constructions: the monotone path polytope and pivot rule polytope. The monotone path polytope, introduced by Billera and Sturmfels, is a geometric model for the spaces of all monotone paths on a polytope that could be chosen by a shadow pivot rule for a fixed linear program. We study these on examples of polytopes fundamental in algebraic combinatorics such as cross-polytopes and products of simplices. We also study how monotone path polytopes are affected by other constructions such as prisms and pyramids. In each case, we find rich combinatorics with surprising new interpretations in terms of the simplex method. The pivot rule polytope is an alteration of the monotone path polytope to classify a broad set of pivot rules we study in detail called normalized weight pivot rules, both of which are defined in this thesis. In particular, we show that if a polynomial time version of the simplex method exists, there must be a normalized weight pivot rule guaranteed to always choose polynomial length paths. Finally, we study this construction on examples finding new realizations of polytopes in algebraic combinatorics such as the associahedron.