Motivated by the problem of bounding the number of iterations of the simplex algorithm, we investigate the possible lengths of monotone paths followed inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the traveling salesman polytope, among others. We begin by showing that combinatorial cubes have monotone diameter and Bland simplex height upper bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size monotone diameter. In contrast, we show that for many well-known combinatorial polytopes, the height is at least exponential. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths.

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions to systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer k, we prove that there exists a constant c(n,k), depending only on the dimension n and k, such that if a polyhedron {x∈Rn: Ax≤b} contains exactly k integer points, then there exists a subset of the rows, of cardinality no more than c(n,k), defining a polyhedron that contains exactly the same k integer points. In this case c(n,0)=2n as in the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant c(n,k) and discuss some consequences, including a Clarkson-style algorithm to find the l-th best solution of an integer program with respect to the ordering induced by the objective function.