The American Mathematical Society sponsors a series of Short Courses, each
of which consists of a set of survey lectures on a single theme of pure and applied
mathematics. Initiated in 1973, these two-day courses occur immediately preced-
ing the Joint Mathematics Meetings held in January as well as at some summer
On January 5-6, 2004, the AMS Short Course Trends in Optimization 2004 took
place in Phoenix, Arizona. Optimization has not been the focus of a recent AMS
Short Course. Past Short Courses on related themes consist of: (i) Operations
Research, Washington D.C., 1975, (ii) Applied Combinatorics, Kalamazoo, 1975,
and (iii) Operations Research, Duluth, 1979. There have been impressive advances
in optimization since then, and our goal was to showcase some of the exciting more
recent work.
Our Short Course consisted of seven 75-minute lectures given by leaders in the
field of optimization. It is impossible to give a thorough cross-section of research
in optimization in a two-day course. Rather, we chose seven exciting areas to focus
on, with a clear bias toward the discrete side of optimization, somewhat reflecting
the interests of the organizers. This volume comprises edited notes prepared by our
Optimization is concerned with the efficient computation of the supremum of
an objective function f whose domain is restricted to some set of feasible solutions
S. Assumptions about the function / (linear, convex, continuous, differentiable,
etc.) and the set S (a hypercube, a convex set, a polyhedron, the integer lattice
points in a polyhedron, the set of symmetric positive semidefinite matrices, etc.)
lead to structural results and/or efficient algorithms. When the set S is a subset of
the power set of a finite set, we are in the domain of combinatorial optimization.
No sophisticated background is needed in order to read the lecture notes in
this volume. Many of them are self-contained and all provide extensive references.
However, basic knowledge of linear programming duality (which appears in almost
all chapters), the geometric combinatorics of polyhedral sets (extreme points and
rays, faces, valid inequalities, etc.), and the geometry of integer programming would
be useful. There are many nice books devoted to each topic above, but most cover
more than the introductory material. A good starting point where the reader
can find the needed material in a condensed but very readable form is Chapter 0
of Jon Lee's textbook A First Course in Combinatorial Optimization (Cambridge
University Press, 2004).
Karen Aardal (Georgia Institute of Technology) in her lecture Lattice basis
reduction in optimization, describes Lovasz's fundamental algorithm for producing
a short vector in a lattice by lattice basis reduction, and H.W. Lenstra's use (in the
Previous Page Next Page