Integer programming, lattices, and results in fixed dimension

K.I. Aardal, F. Eisenbrand

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureHoofdstukProfessioneel

7 Citaten (Scopus)

Samenvatting

We review and describe several results regarding integer programming problems in fixed dimension. First, we describe various lattice basis reduction algorithms that are used as auxiliary algorithms when solving integer feasibility and optimization problems. Next, we review three algorithms for solving the integer feasibility problem. These algorithms are based on the idea of branching on lattice hyperplanes, and their running time is polynomial in fixed dimension. We also briefly describe an algorithm, based on a different principle, to count integer points in an integer polytope. We then turn the attention to integer optimization. Again, we describe three algorithms: binary search, a linear algorithm for a fixed number of constraints, and a randomized algorithm for a varying number of constraints. The topic of the next part of our chapter is how to use lattice basis reduction in problem reformulation. Finally, we review cutting plane results when the dimension is fixed.
Originele taal-2Engels
TitelDiscrete Optimization
RedacteurenK.I. Aardal, G.L. Nemhauser, R. Weismantel
Plaats van productieAmsterdam
UitgeverijNorth-Holland Publishing Company
Pagina's171-243
ISBN van geprinte versie0-444-51507-0
DOI's
StatusGepubliceerd - 2005

Publicatie series

NaamHandbooks in Operations Research and Management Science
Volume12
ISSN van geprinte versie0927-0507

Vingerafdruk Duik in de onderzoeksthema's van 'Integer programming, lattices, and results in fixed dimension'. Samen vormen ze een unieke vingerafdruk.

Citeer dit