Integer programming, lattices, and results in fixed dimension

K.I. Aardal, F. Eisenbrand

Research output: Chapter in Book/Report/Conference proceedingChapterProfessional

9 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationDiscrete Optimization
EditorsK.I. Aardal, G.L. Nemhauser, R. Weismantel
Place of PublicationAmsterdam
PublisherNorth-Holland Publishing Company
ISBN (Print)0-444-51507-0
Publication statusPublished - 2005

Publication series

NameHandbooks in Operations Research and Management Science
ISSN (Print)0927-0507


Dive into the research topics of 'Integer programming, lattices, and results in fixed dimension'. Together they form a unique fingerprint.

Cite this