Parametrizing an Integer Linear Program by an Integer
Bobby Shen · SIAM Journal on Discrete Mathematics · 2018
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$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, \ldots, P_{d-1}$ such that for sufficiently large $t,$ $f_\ell(t)=P_{t({\rm mod}\ d)}(t).$ Closely related to finding the $\ell$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), \ldots, \mathbf{v_k}(t)$, where $\mathbf{v_i}$ is a vector whose coordinates are in $\mathbb{Q}(t)$ and of size $O(t),$ 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(t)$ assumption.