Circuit augmentation schemes are a family of combinatorial algorithms for linear programming that generalize the simplex method. To solve the linear program, they construct a so-called monotone circuit walk: They start at an initial vertex of the feasible region and traverse a discrete sequence of points on the boundary, while moving along certain allowed directions (circuits) and improving the objective function at each step until reaching an optimum. Since the existence of short circuit walks has been conjectured (Circuit Diameter Conjecture), several works have investigated how well one can efficiently approximate shortest monotone circuit walks towards an optimum. A first result addressing this question was given by De Loera, Kafer, and Sanita [SIAM J. Opt., 2022], who showed that given as input an LP and the starting vertex, finding a 2-approximation for this problem is NP-hard. Cardinal and the third author [Math. Prog. 2023] gave a stronger lower bound assuming the exponential time hypothesis, showing that even an approximation factor of \(O(\frac{\log m}{\log \log m})\) is intractable for LPs defined by \(m\) inequalities. Both of these results were based on reductions from highly degenerate polytopes in combinatorial optimization with high dimension.

Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice, we propose a new algorithm analysis framework that we call by-the-book analysis. In contrast to earlier frameworks, by-the-book analysis not only models an algorithm's input data, but also the algorithm itself. Results from by-the-book analysis are meant to correspond well with established knowledge of an algorithm's practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances. We apply our framework to the simplex method, an algorithm which is beloved for its excellent performance in practice and notorious for its high running time under worst-case analysis. The simplex method similarly showcased the previous state of the art framework smoothed analysis (Spielman and Teng, STOC'01). We explain how our framework overcomes several weaknesses of smoothed analysis and we prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time. Our results provide analytical justification for these features which are common to all high-quality simplex method implementations.

The diameter of the graph of a d-dimensional lattice polytope P ⊆ [0, k]n is known to be at most dk due to work by Kleinschmidt and Onn. However, it is an open question whether the monotone diameter, the shortest guaranteed length of a monotone path, of a d-dimensional lattice polytope P = {x : Ax ≤ b} ⊆ [0,k]n is bounded by a polynomial in d and k. This question is of particular interest in linear optimization, since paths traced by the Simplex method must be monotone. We introduce partial results in this direction including a monotone diameter bound of 3d for k = 2, a monotone diameter bound of (d — 1)m + 1 for d-dimensional (ℓ + 1)-level polytopes, a pivot rule such that the Simplex method is guaranteed to take at most dnk||A||∞ non-degenerate steps to solve a LP on P, and a bound of dk for lengths of paths from certain fixed starting points. Finally, we present a constructive approach to a diameter bound of (3/2)dk and describe how to translate this final bound into an algorithm that solves a linear program by tracing such a path.