Proceedings of Symposia in Applied Mathematics
Volume 61, 2004
Lattice basis reduction in optimization: Selected topics
Karen Aardal
In memory of my father.
ABSTRACT. Lattice basis reduction has proven to be a powerful tool in many
areas of discrete mathematics, such as cryptography and integer programming.
We will review some of these results with an emphasis on Lovasz' basis reduc-
tion algorithm, H.W. Lenstra's algorithm for integer programming, and some
related algorithms. These integer programming algorithms have in common
that they enumerate lattice hyperplanes, i.e., hyperplanes in which the whole
lattice is contained. By using basis reduction, Lenstra proved that for fixed
dimension the number of hyperplanes we need to consider is bounded by a
function that depends on the dimension only. This result not only resolved an
important open question, but introduced new tools to integer optimization.
1. Introduction and motivation
In our lecture we mainly focus on the following integer linear feasibility problem.
Let P = {x G Rn | Ax d}, where the m x n matrix A and the m-vector d are
given by integer input. Assume P is bounded and full-dimensional.
(1.1) Does there exist a vector x G P f)
Zn?
This problem is related to the integer linear optimization problem, where we want to
find a solution that maximizes or minimizes a given objective function ex, where c
is an n-dimensional row vector. Branch-and-bound has proven to be a very success-
ful method to solve integer linear optimization problems, especially when combined
with cutting planes, and it is implemented in several commercial optimization pack-
ages. The key component of branch-and-bound is to solve the linear relaxation, i.e.,
we maximize (or minimize) ex over P. If the optimal solution x* to the linear re-
laxation is integer, then we are done; otherwise we choose a non-integral component
of x*, say Xj with value fj and create two subproblems by adding the constraints
Xj [/jj, and Xj \fj] respectively to P. This is the part of the algorithm that is
called "branching". Each of the subproblems is again treated in the same fashion.
2000 Mathematics Subject Classification. Primary 90C10; Secondary 11H06, 68Q25.
Key words and phrases. Integer optimization, Lattice basis reduction, Branching on
hyperplanes.
The author was supported in part by NSF grants DMI-0100020 and DMII-0121495.
© 2004 Karen Aardal
http://dx.doi.org/10.1090/psapm/061/2104728
Previous Page Next Page