Reference : Combining problem structure and basis reduction to solve a class of hard integer programs
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
Combining problem structure and basis reduction to solve a class of hard integer programs
Louveaux, Quentin mailto [Université catholique de Louvain > CORE, INMA > > >]
Wolsey, Laurence A. mailto [Université catholique de Louvain > CORE, INMA > > >]
Mathematics of Operations Research
INFORMS: Institute for Operations Research
Yes (verified by ORBi)
[en] Integer Programming ; Lattices
[en] We consider a hard integer programming problem that is difficult for the standard
branch-and-bound approach even for small instances. A reformulation based
on lattice basis reduction is known to be more effective. However
the step to compute the reduced basis, even if it is found in polynomial time, becomes a bottleneck
for small to medium instances. By using the structure of the problem,
we show that we can decompose the problem and obtain the basis by
taking the kronecker product of two smaller bases easier to compute. Furthermore,
if the two small bases are reduced, the kronecker product is also reduced
up to a reordering of the vectors. Computational results show the gain from such an approach.
Center for Operations Research and Econometrics
Fonds de la Recherche Scientifique (Communauté française de Belgique) - F.R.S.-FNRS ; Politique Scientifique Fédérale
Researchers ; Professionals
The paper is available on the website of the journal.

File(s) associated to this reference

Fulltext file(s):

Open access
CombiningProblemStructure.pdfPublisher postprint137.04 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.