On polynomial kernels for sparse integer linear programs

Successful solvers for integer linear programs (ILPs) demonstrate that preprocessing can greatly speed up the computation. We study preprocessing for ILPs via the theoretical notion of kernelization from parameterized complexity. Prior to our work, there were only implied lower bounds from other problems that hold only for dense instances and do not take into account the domain size. We consider the feasibility problem for ILPs Ax≤b where A is an r-row-sparse matrix parameterized by the number of variables, i.e., A has at most r nonzero entries per row, and show that its kernelizability depends strongly on the domain size. If the domain is unbounded then this problem does not admit a polynomial kernelization unless NP⊆coNP/poly. If, on the other hand, the domain size d of each variable is polynomially bounded in n, or if d is an additional parameter, then we do get a polynomial kernelization.