A lattice path model for the volume of the Monge polytope

Monge matrices arise throughout combinatorial optimization and algorithm design; the Monge polytope ${\mathcal{M}}_{pq}$ is the set of $p\times q$ Monge matrices lying inside the standard simplex on the set of matrix coordinates. We find a Stanley decomposition of the associated affine semigroup, and use it to obtain a volume formula for ${\mathcal{M}}_{pq}$ expressed as a sum over “Z-avoiding” Delannoy paths in a $p\times q$ grid. An efficient dynamic-programming implementation of this formula computes the volume in dimensions far beyond the reach of general-purpose exact-volume algorithms (e.g., the volume of ${\mathcal{M}}_{20,20}$, which has dimension 399, is computed in a fraction of a second). As a corollary of our Stanley decomposition, we also obtain a combinatorial closed form for the Ehrhart series of ${\mathcal{M}}_{pq}$.