Integer Programming, Lattices and Results in Fixed Dimension

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.