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