### 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 language | English |
---|---|

Title of host publication | Discrete Optimization |

Editors | K.I. Aardal, G.L. Nemhauser, R. Weismantel |

Place of Publication | Amsterdam |

Publisher | North-Holland Publishing Company |

Pages | 171-243 |

ISBN (Print) | 0-444-51507-0 |

DOIs | |

Publication status | Published - 2005 |

### Publication series

Name | Handbooks in Operations Research and Management Science |
---|---|

Volume | 12 |

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