Parametrizing an integer linear program by an integer

Abstract

We consider a family of integer linear programs in which the coefficients of the constraints and objective function are polynomials of an integer parameter $t.$ For $\ell$ in ${\mathbb{Z}}_{+},$ we define $f_{\ell }(t)$ to be the ${\ell }^{\text{th}}$ largest value of the objective function with multiplicity for the integer linear program at $t.$ We prove that for all $\ell ,$ $f_{\ell }$ is eventually quasi-polynomial; that is, there exists $d$ and polynomials $P_0,\dots ,P_{d-1}$ such that for sufficiently large $t,$ $f_{\ell }(t)=P_{d(\mathrm{mod}t)}(t).$ Closely related to finding the ${\ell }^{\text{th}}$ largest value is describing the vertices of the convex hull of the feasible set. Calegari and Walker showed that if $R(t)$ is the convex hull of ${\mathbf{v}}_1(t),\dots ,{\mathbf{v}}_{\mathbf{k}}(t)$ where ${\mathbf{v}}_{\mathbf{i}}$ is a vector whose coordinates are in $\mathbb{Q}(u)$ and of size $O(u),$ then the vertices of the convex hull of the set of lattice points in $R(t)$ has eventually quasi-polynomial structure. We prove this without the $O(u)$ assumption.

16 pages, 3nd version, Accepted by SIDMA