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