  


Integer Points in a Parameterised Polyhedron
Friedrich Eisenbrand (eisenmath.unipaderborn.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 righthand 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 Modify/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  