Combining problem structure and basis reduction to solve a class of hard integer programs
by
Quentin Louveaux
Université catholique de Louvain, Center of Operations Research and Econometrics

Recently, Aardal, Hurkens and Lenstra have succesfully solved some small difficult equality constrained integer programs by basis reduction. Here, we adapt their method to solve integer programs that are larger but have special structure. Formally the problem can be viewed as finding a matrix X in Z^mn₊ satisfying XA = C, BX = D, and the approach requires us to find a reduced basis of the lattice L = { X in Z^m×n: XA=0, BX=0}.

The main topic of the talk is the 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.

Date received: March 26, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafv-85.