# Is a Parametric Integer Linear Programming Problem eventually quasi-polynomial?

I will consider a family of Integer Linear Programs parametrized by a positive integer $t$.

Let $\mathbf{x} = (x_1, \ldots, x_n)$ be the indeterminates.

Let $A$ an $m$ by $n$ matrix whose elements are univariate polynomials with integer coefficients, let $\mathbf{b}$ be an $m$-dimensional vector whose elements are also univariate polynomials with integer coefficients, and let $P_i$ and $Q_i$ be univariate polynomials with integer coefficients and with positive leading coefficients for $i=1, \ldots, n.$

Let $f(t)$ be the maximum value of $\sum_{i=1}^n Q_i(t) x_i$ with constraints

$0 \le x_i \le P_i(t)$

$A(t) \mathbf{x} \le \mathbf{b}(t)$

$x_i \in \mathbb{Z}$

or $0$ if no points satisfy all constraints.

Is it true that $f(t)$ is eventually a quasi-polynomial function of $t$?

Equivalently, do there exist $m, N \in \mathbb{Z}^+$ and polynomials $R_0, \ldots, R_{m-1}$ in $\mathbb{R}[t]$ such that for all integers $t$ greater than $N,$

$f(t)=R_{t \pmod{m}}(t)$?

I think this could be true because the the set satisfying the constraints seems to have a convex hull whose vertices coordinates are eventually quasi-polynomials, possibly with some redundancy. I'm having a very hard time with convex hulls in high dimensions.

Note: quasi-polynomial as opposed to polynomial is necessary because maximizing $x_1$ subject to $0 \le x_1 \le t$ and $2 x_1 \le t$ gives $\lfloor t/2 \rfloor.$

Integer Linear Programming seems prominent enough that I thought I would ask this here first

• Isn't this very closely related to the ehrhart function of rational polytopes? – Per Alexandersson Jul 12 '15 at 9:00
• This seems harder because for Ehrhart's theorem, A is constant and b is a constant times t. I also don't know the proof of Ehrhart's theorem. – Bobby Shen Jul 12 '15 at 13:27