TY - CHAP

T1 - Integer Programming, Lattices and Results in Fixed Dimension

AU - Aardal, Karen

AU - Eisenbrand, Friedrich

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

M3 - Chapter

T3 - Handbooks in Operations Research and Management Science

SP - 171

EP - 243

BT - Discrete Optimization

A2 - Aardal, Karen

A2 - Nemhauser, George

A2 - Weismantel, Robert

PB - Elsevier

ER -