Contemporary Mathematics
Volume 452, 2008
Lattice reformulation of integer programming problems
Karen Aardal
ABSTRACT. We discuss how to use the structure of lattices to reformulate
and solve integer programming problems. We take a closer look at integer
knapsack problems and illustrate how it is possible to use the structure of
lattices to prove properties of certain classes of knapsack problems, and how
these properties can be used in designing practically efficient algorithms.
1. Background
The integer optimization problem is defined as follows:
max{ (c,x)
I
Ax:::;
b,
X
E
zn}
0
For simplicity of presentation we assume that the input is integer. We are given
c,
A, and band we wish to find an integer-valued vector x maximizing the linear
function ex. In the integer feasibility problem we wish to determine whether the
polyhedron
{X
E
JR.n
I
Ax :::; b}
contains an integer vector. The study and solution of integer optimization and
integer feasibility problems is often referred to as integer programming.
1.1.
Cutting planes and branch-and-bound. The history of integer pro-
gramming is, compared to many other mathematical subjects, quite brief. The first
papers on integer programming as we know it today were published by Ralph E.
Gomory, see for instance [Gom58, Gom63]. It is also interesting to read Gomory's
[Gom91] own remarks on how he entered the field and viewed the topic. Gomory,
while at Princeton, worked as a consultant for the US Navy, and there he was
presented with a problem from the Navy Task Force.
It
was a linear programming
problem with the additional important feature that the answer should be given in
integer numbers. After having a thorough look at the problem at hand, Gomory
made the following observation: all objective function coefficients are integer, so
the optimal value should also be integer. One could solve the linear programming
2000 Mathematics Subject Classification. Primary 90C10; Secondary 45A05, 11Y50.
Key words and phroses. Integer programming, lattices, reduced bases.
Supported in part by ADONET Marie-Curie Research Training Network MRTN-CT-2003-
504438 and the Dutch BSIK/BRICKS project.
@2008 Karen Aardal
1
http://dx.doi.org/10.1090/conm/452/08768
Previous Page Next Page