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

In this paper, we consider the counting function \({{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y) = |{{\,\mathrm{\mathcal {P}}\,}}_{y} \cap {{\,\mathrm{\mathbb {Z}}\,}}^{n_x}|\) ${\mathcal{E}}_{\mathcal{P}}(y)=|{\mathcal{P}}_y\cap {\mathbb{Z}}^{n_x}|$ for a parametric polyhedron \({{\,\mathrm{\mathcal {P}}\,}}_{y} = \{ x \in {{\,\mathrm{\mathbb {R}}\,}}^{n_x} :A x \le b + B y\}\) ${\mathcal{P}}_y=\{x\in {\mathbb{R}}^{n_x}:Ax\le b+By\}$ , where \(y \in {{\,\mathrm{\mathbb {R}}\,}}^{n_y}\) $y\in {\mathbb{R}}^{n_y}$ . We give a new representation of \({{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)\) ${\mathcal{E}}_{\mathcal{P}}(y)$ , called a 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 \({{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)\) ${\mathcal{E}}_{\mathcal{P}}(y)$ in certain scenarios.

The most important cases are the following: 1)

We show that, for the parametric polyhedron \({{\,\mathrm{\mathcal {P}}\,}}_y\) ${\mathcal{P}}_y$ defined by a standard-form system \(A x = y,\, x \ge 0\) $Ax=y,x\ge 0$ with a fixed number of equalities, the function \({{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)\) ${\mathcal{E}}_{\mathcal{P}}(y)$ can be represented by a polynomial-time computable function. In turn, such a representation of \({{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)\) ${\mathcal{E}}_{\mathcal{P}}(y)$ can be constructed by an \({{\,\textrm{poly}\,}}\bigl (n, \Vert A\Vert _{\infty }\bigr )\) ${\text{poly}(n,\Vert A\Vert }_{\infty })$ -time algorithm;