A new and faster representation for counting integer points in parametric polyhedra

Computational Optimization and Applications. 2025. Vol. 92. P. 811–861.

Dmitry V. Gribanov, Dmitry S. Malyshev, Pardalos P. M., Zolotykh N. Y.

In this paper, we consider the counting function $\QEnum(y) = |\PC_{y} \cap \ZZ^{n_x}|$ for a parametric polyhedron $\PC_{y} = \{ x \in \RR^{n_x} \colon A x \leq b + B y\}$, where $y \in \RR^{n_y}$. We give a new representation of $\QEnum(y)$, called a \emph{piece-wise step-polynomial with periodic coefficients}, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart's quasi-polynomials. It gives the fastest way to calculate $\QEnum(y)$ in certain scenarios.

\textbf{The most important cases are the following:}

1) We show that, for the parametric polyhedron $\PC_y$ defined by a standard-form system $A x = y,\, x \geq 0$ with a fixed number of equalities, the function $\QEnum(y)$ can be represented by a polynomial-time computable function. In turn, such a representation of $\QEnum(y)$ can be constructed by an $\poly\bigl(n, \|A\|_{\infty}\bigr)$-time algorithm;

2) Assuming again that the number of equalities is fixed, we show that integer/rational Ehrhart's quasi-polynomials of a polytope can be computed by FPT-algorithms, parameterized by sub-determinants of $A$ or its elements; 

3) Our representation of $\QEnum$ is more efficient than other known approaches, if $A$ has bounded elements, especially if it is sparse in addition;

Additionally, we provide a discussion about possible applications in the area of compiler optimization. In some “natural” assumptions on a program code, our approach has the fastest complexity bounds.

Keywords: integer linear programming, Short rational generating function, subset-sum problem, Bounded sub-determinants, counting problem, parametric integer programming, multidimensional knapsack problem

Publication based on the results of: Network and graph models, algorithmic complexity and data mining (2025)