The goal of this paper is to design a simplex algorithm for linear programs on lattice polytopes that traces ‘short’ simplex paths from any given vertex to an optimal one. We consider a lattice polytope P contained in [0, k]^n and defined via m linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of P of length in O(n^4 k log(nk)). The length of this path is independent on m and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as a linear function in n and k.

Motivated by the fact that most known lattice polytopes are defined via 0,±1 constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value α of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in O(n^2 k log(nkα)). In particular, if α is bounded by a polynomial in n, k, then the length of the simplex path is in O(n^2 k log(nk)).

For both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time.