6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Isn't this very closely related to the ehrhart function of rational polytopes? $\endgroup$ – Per Alexandersson Jul 12 '15 at 9:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Bobby Shen Jul 12 '15 at 13:27
1
$\begingroup$

The answer seems to be yes by

Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior

by Kevin Woods, John Goodrick, and Tristram Bogart. DOI:10.19086/da.1254v2

The solution to your specific problem may have been known earlier, see the references [2,3] in the linked paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.