- Integer Points in a Parameterised Polyhedron Friedrich Eisenbrand (eisenmath.uni-paderborn.de) Gennady Shmonin (shmoninmath.uni-paderborn.de) Abstract: 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. Keywords: integer programming in fixed dimension; parameterised polyhedron; integer programming gap Category 1: Integer Programming (Other ) Citation: Download: [PDF]Entry Submitted: 04/30/2007Entry Accepted: 04/30/2007Entry Last Modified: 04/30/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.