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

Recently Aardal et al. have successfully solved some small difficult equality constrained integer programs by using basis reduction to reformulate the problems as inequality constrained integer programs in a different space. Here we adapt their method to solve integer programs that are larger, but have special structure. The practical problem motivating this work has variables xij and is a variant of the market share problem. More formally the problem can be viewed as finding a matrix X belongs Z exp.mn + satisfying XA = C,BX = D where A,B,C,D are matrices of compatible dimensions, and the approach requires us to find a reduced basis of the lattice L = {X belongs Z exp.mn : XA = 0,BX = 0}. The main topic of this paper is a study of the lattice L. It is shown that an integer basis of L can be obtained by taking the Kronecker product of vectors from integer bases of two much smaller lattices. Furthermore the resulting basis is a reduced basis if the integer bases of the two small lattices are reduced bases, and a suitable orderin is chosen. Finally some limited computational results are presented showing the benefits of making use of the problem structure.