On lattice point counting in Δ-modular polyhedra

Optimization Letters. 2022. Vol. 16. No. 7. P. 1991–2018.

Gribanov D., Zolotykh N.

Let a polyhedron $P$ be defined by one of the following ways: 
\begin{enumerate}
\item[(i)] $P = \{x \in \RR^n \colon A x \leq b\}$, where $A \in \ZZ^{(n+k) \times n}$, $b \in \ZZ^{(n+k)}$ and $\rank A = n$,
\item[(ii)] $P = \{x \in \RR_+^n \colon A x = b\}$, where $A \in \ZZ^{k \times n}$, $b \in \ZZ^{k}$ and $\rank A = k$,
\end{enumerate} 
and let all rank order minors of $A$ be bounded by $\Delta$ in absolute values. We show that the short rational generating function for the power series 
$$
\sum\limits_{m \in P \cap \ZZ^n} \BX^m
$$
can be computed with the arithmetical complexity 
$
O\left(T_{\SNF}(d) \cdot d^{k} \cdot d^{\log_2 \Delta}\right),
$
where $k$ and $\Delta$ are fixed, $d = \dim P$, and $T_{\SNF}(m)$ is the complexity of computing the Smith Normal Form for $m \times m$ integer matrices.
In particular, $d = n$, for the case (i), and $d = n-k$, for the case (ii).

The simplest examples of polyhedra that meet the conditions (i) or (ii) are the \emph{simplices}, the \emph{subset sum} polytope and the \emph{knapsack} or \emph{multidimensional knapsack}  polytopes. Previously, the existence of a polynomial time algorithm in varying dimension for the considered class of problems was unknown already for simplicies ($k = 1$).

We apply these results to parametric polytopes and show that the step polynomial representation of the function $c_P(\BY) = |P_{\BY} \cap \ZZ^n|$, where $P_{\BY}$ is a parametric polytope, whose structure is close to the cases (i) or (ii), can be computed in polynomial time even if the dimension of $P_{\BY}$ is not fixed. As another consequence, we show that the coefficients $e_i(P,m)$ of the Ehrhart quasi-polynomial 
$$
\left|  mP \cap \ZZ^n\right| = \sum\limits_{j = 0}^n e_j(P,m)m^j
$$ 
can be computed with a polynomial-time algorithm, for fixed $k$ and $\Delta$.

Keywords: knapsack problems, Integer programming, Ehrhart polynomial, Multi-dimensional knapsack problem, the subset sum problem, generating functions, bounded minors, Step polynomial, Parametric polytope

Publication based on the results of: Theoretical and algorithmic aspects of network analysis algorithms (2021)