Optimization Online


Integer Points in a Parameterised Polyhedron

Friedrich Eisenbrand (eisen***at***math.uni-paderborn.de)
Gennady Shmonin (shmonin***at***math.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 )


Download: [PDF]

Entry Submitted: 04/30/2007
Entry Accepted: 04/30/2007
Entry Last Modified: 04/30/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society