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/2007
Entry Accepted: 04/30/2007
Entry Last Modified: 04/30/2007

Modify/Update this entry