Combining problem structure with basis reduction to solve a class of hard integer programs
(2000)
Files
dp2000-51.pdf
Open Access - Adobe PDF
- 265.88 KB
Details
- Authors
- 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.
- Affiliations
Citations
Louveaux, Q., & Wolsey, L. (2000). Combining problem structure with basis reduction to solve a class of hard integer programs (CORE Discussion Papers 2000/51). https://hdl.handle.net/2078.5/34602