Skip to main content
1 of 3

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 in $\mathbb{Z}[t],$ $\mathbf{b}$ be an $m$-D vector whose elements are in $\mathbb{Z}[t],$ and $P_i(t), Q_i(t)$ be in $\mathbb{Z}[t]$ with positive leading coefficient 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?

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$ subject to $0 \le x_1 \le x$ and $2 x_1 \le x$ gives $\lfloor x/2 \rfloor.$

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