Combining problem structure with basis reduction to solve a class of hard integer programs

Quentin Louveaux and Laurence Wolsey

No 2000051, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 theirmethod 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.

Keywords: Integer programming; basis reduction; lattices; market share problem. (search for similar items in EconPapers)
Date: 2000-10
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2000.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2000051

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS (alain.gillis@uclouvain.be).