Gennady
Shmonin
Title:
Testing integer rounding properties
Abstract:
We consider systems of linear inequalities of the form $A x
\leq b$,
where the right-hand side $b$ is varying. First, we show that one can
precompute---in polynomial time, if the dimension of $x$ is
fixed---the set of lattice directions such that, for any $b$, the
width of the polyhedron $\{x : A x \leq b\}$ is attained along one of
these directions. This result gives rise to the algorithm to decide
the following: Given a rational matrix $A$ and a polyhedron $Q$, is
there a $b \in Q$ such that the system $A x \leq b$ does not have any
integer solution? The algorithm runs in polynomial time, whenever the
rank of $A$ is fixed. This extends the algorithm of Kannan (1992), in
which $b$ is required to vary over a polyhedron of fixed dimension.
The latter algorithm can be applied to recognise integer linear
programs having integer rounding property. Traditionally, a system $A
x \leq b$ is said to have the integer rounding property if, for all
$b$, the optimum value of the integer program $\min \{yb : yA = c, y
\geq 0 \mbox{ integer}\}$ is equal to the optimum value of its linear
relaxation rounded down. We extend this definition by allowing the
optimum values of the integer program and its linear relaxation to
differ on some absolute value $\gamma$. Assuming that the rank of
$A$ is fixed, we can test in polynomial time whether a given system
satisfies this property.