Combining Problem Structure with Basis Reduction to solve a Class of Hard Integer Programs

Recently Aardal et al. (2000) 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 is a variant of the market share problem. More formally, the problem can be viewed as finding a matrixX ? Z mn+ satisfyingXA =C,BX =D, whereA,B,C,D are matrices of compatible dimensions, and the approach requires us to find a reduced basis of the lattice L = { X ? Zm x n :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 ordering is chosen.Finally, some limited computational results are presented showing the benefits of making use of the problem structure.