Abstract |
: |
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. |