Integer Points in a Parameterised Polyhedron

The classical parameterised integer feasibility problem is as follows. Given a rational matrix $A \in \mathbb{Q}^{m \times n}$ and a rational polyhedron $Q \subseteq \mathbb{R}^m$, decide, whether there exists a point $b \in Q$ such that $A x \leq b$ is integer infeasible. Our main result is a polynomial algorithm to solve a slightly more general parameterised integer feasibility problem if the number $n$ of columns of $A$ is fixed. This extends a result of Kannan (1992) who provided such an algorithm for the case in which additionally to $n$, also the affine dimension of the polyhedron $Q$ has to be fixed. As an application of our result, we describe an algorithm to find the maximum difference between the optimum values of an integer program $\max \{ c x : A x \leq b, \, x \in \mathbf{Z}^n \}$ and its linear programming relaxation, as the right-hand side $b$ varies over all vectors, for which the integer program is feasible. The latter is an extension of a recent result of Hosten and Sturmfels (2003) who presented such an algorithm for integer programs in standard form.



View Integer Points in a Parameterised Polyhedron