Combining problem structure and basis reduction to solve a class of hard integer programs

We consider a hard integer programming problem that is difficult for the standard
branch-and-bound approach even for small instances. A reformulation based
on lattice basis reduction is known to be more effective. However
the step to compute the reduced basis, even if it is found in polynomial time, becomes a bottleneck
for small to medium instances. By using the structure of the problem,
we show that we can decompose the problem and obtain the basis by
taking the kronecker product of two smaller bases easier to compute. Furthermore,
if the two small bases are reduced, the kronecker product is also reduced
up to a reordering of the vectors. Computational results show the gain from such an approach.