Integer programming, lattices, and results in fixed dimension

K.I. Aardal, F. Eisenbrand

Research output: Chapter in Book/Report/Conference proceedingChapterProfessional

7 Citations (Scopus)

Abstract

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
Pages171-243
ISBN (Print)0-444-51507-0
DOIs
Publication statusPublished - 2005

Publication series

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

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

  • Cite this

    Aardal, K. I., & Eisenbrand, F. (2005). Integer programming, lattices, and results in fixed dimension. In K. I. Aardal, G. L. Nemhauser, & R. Weismantel (Eds.), Discrete Optimization (pp. 171-243). (Handbooks in Operations Research and Management Science; Vol. 12). North-Holland Publishing Company. https://doi.org/10.1016/S0927-0507(05)12004-0