  Integer linear programs (ILPs) are a widely applied framework for dealing
with combinatorial problems that arise in practice. It is known, e.g., by the
success of CPLEX, that preprocessing and simplification can greatly speed up
the process of optimizing an ILP. The present work seeks to further the
theoretical understanding of preprocessing for ILPs by initiating a rigorous
study within the framework of parameterized complexity and kernelization.
  A famous result of Lenstra (Mathematics of Operations Research, 1983) shows
that feasibility of any ILP with n variables and m constraints can be decided
in time O(c^{n^3} m^c'). Thus, by a folklore argument, any such ILP admits a
kernelization to an equivalent instance of size O(c^{n^3}). It is known, that
unless NP \subseteq coNP/poly and the polynomial hierarchy collapses, no
kernelization with size bound polynomial in n is possible. However, this lower
bound only applies for the case when constraints may include an arbitrary
number of variables since it follows from lower bounds for Satisfiability and
Hitting Set, whose bounded arity variants admit polynomial kernelizations.
  We consider the feasibility problem for ILPs Ax<= b where A is an
r-row-sparse matrix parameterized by the number of variables. We show that the
kernelizability of this problem depends strongly on the range of the variables.
If the range is unbounded then this problem does not admit a polynomial
kernelization unless NP \subseteq coNP/poly. If, on the other hand, the range
of each variable is polynomially bounded in n then we do get a polynomial
kernelization. Additionally, this holds also for the more general case when the
maximum range d is an additional parameter, i.e., the size obtained is
polynomial in n+d.
