Parametric Integer Programming in Fixed Dimension
| dc.creator | Eisenbrand, Friedrich | |
| dc.creator | Shmonin, Gennady | |
| dc.date | 2008-01-28 | |
| dc.date.accessioned | 2026-07-07T08:56:52Z | |
| dc.date.available | 2026-07-07T08:56:52Z | |
| dc.description | We consider the following problem: Given a rational matrix $A \in \setQ^{m \times n}$ and a rational polyhedron $Q \subseteq\setR^{m+p}$, decide if for all vectors $b \in \setR^m$, for which there exists an integral $z \in \setZ^p$ such that $(b, z) \in Q$, the system of linear inequalities $A x \leq b$ has an integral solution. We show that there exists an algorithm that solves this problem in polynomial time if $p$ and $n$ are fixed. This extends a result of Kannan (1990) who established such an algorithm for the case when, in addition to $p$ and $n$, the affine dimension of $Q$ is fixed. As an application of this 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 \setZ^n \}$ and its linear programming relaxation over all right-hand sides $b$, for which the integer program is feasible. The algorithm is polynomial if $n$ is fixed. This is an extension of a recent result of Hoşten and Sturmfels (2003) who presented such an algorithm for integer programs in standard form. | |
| dc.description | 23 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/0801.4336 | |
| dc.identifier | http://arxiv.org/abs/0801.4336 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/146764 | |
| dc.subject | Optimization and Control | |
| dc.subject | 90C10 | |
| dc.title | Parametric Integer Programming in Fixed Dimension | |
| dc.type | text |