Integer Programming, Lattices and Results in Fixed Dimension

Karen Aardal, Friedrich Eisenbrand

Research output: Chapter in Book/Conference proceedings/Edited volumeChapterScientific

Abstract

We review and describe several results regarding integer programming problems infixed dimension .First, we describe various lattice basis reduction algorithms thatare used as auxiliary algorithms when solving integer feasibility and optimizationproblems .Next, we review three algorithms for solving the integer feasibilityproblem .These algorithms are based on the idea of branching on lattice hyper-planes, and their running time is polynomial in fixed dimension .We also brieflydescribe an algorithm, based on a different principle, to count integer points in aninteger polytope .We then turn the attention to integer optimization .Again, wedescribe three algorithms: binary search, a linear algorithm for a fixed number ofconstraints, and a randomized algorithm for a varying number of constraints .Thetopic of the next part of our chapter is how to use lattice basis reduction in problemreformulation .Finally, we review cutting plane results when the dimension is fixed.
Original languageEnglish
Title of host publicationDiscrete Optimization
EditorsKaren Aardal, George Nemhauser, Robert Weismantel
PublisherElsevier
Chapter4
Pages171-243
Number of pages73
Publication statusPublished - 2006
Externally publishedYes

Publication series

NameHandbooks in Operations Research and Management Science
Volume12

Fingerprint Dive into the research topics of 'Integer Programming, Lattices and Results in Fixed Dimension'. Together they form a unique fingerprint.

Cite this