You are here:
| Reference : Combining problem structure and basis reduction to solve a class of hard integer programs |
| Scientific journals : Article | |||
| Engineering, computing & technology : Computer science Physical, chemical, mathematical & earth Sciences : Mathematics | |||
| http://hdl.handle.net/2268/441 | |||
| Combining problem structure and basis reduction to solve a class of hard integer programs | |
| English | |
Louveaux, Quentin  [Université catholique de Louvain > CORE, INMA > > >] | |
| Wolsey, Laurence A. [Université catholique de Louvain > CORE, INMA > > >] | |
| 2002 | |
| Mathematics of Operations Research | |
| INFORMS: Institute for Operations Research | |
| 27 | |
| 3 | |
| 470-484 | |
| International | |
| 0364-765X | |
| [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 | |
| http://hdl.handle.net/2268/441 | |
| http://mor.journal.informs.org/ | |
| The paper is available on the website of the journal. |
| File(s) associated to this reference | ||||||||||||||
|
Fulltext file(s):
| ||||||||||||||
All documents in ORBi are protected by a user license.
