Combining Problem Structure with Basis Reduction to solve a Class of Hard Integer Programs
(2002) Mathematics of operations research — Vol. 27, n° 3, p. 470-484 (2002)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 401.41 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Université de Liège Département d'électricité
Citations
Louveaux, Q., & Wolsey, L. (2002). Combining Problem Structure with Basis Reduction to solve a Class of Hard Integer Programs. Mathematics of operations research, 27(3), 470-484. https://doi.org/10.1287/moor.27.3.470.315 (Original work published 2002)