Integer programming, lattices, and results in fixed dimension

Autor: Aardal, Karen, Eisenbrand, F., Nemhauser, G., Weismantel, R.
Přispěvatelé: Algorithms, Networks and Optimization
Jazyk: angličtina
Rok vydání: 2005
Předmět:
Zdroj: Discrete Optimization, 171-243
STARTPAGE=171;ENDPAGE=243;TITLE=Discrete Optimization
ISSN: 0927-0507
DOI: 10.1016/s0927-0507(05)12004-0
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: