** The need for new linear programming textbooks.** The world of linear
programming has
changed dramatically in the last ten years. For one thing, the incredible
changes in computer
technology have made it easy to solve truly huge LPs, and routine LP
problems solve in
fractions of a second even on a personal computer. As a result, the study
of linear
programming algorithms is of less interest to the casual student. (In a
similar vein, we
usually do not teach students how to efficiently compute square roots; we
simply presume they
can press the right buttons on their calculator.) On the other hand,
because we can now solve
truly gigantic linear programs, issues of computer implementation,
numerical stability, and
software architecture, etc., are as important for the serious optimizer as
is, say, duality
theory. Furthermore, the development and recognition of the importance of
interior point
methods has changed the landscape of linear programming significantly, so
that linear
programming is no longer synonymous with the simplex method, and a modern
treatment of LP must
also present an in-depth treatment of the most important interior point
methods.

** Vanderbei's book is thoroughly modern.** Vanderbei's book is completely
up-to-date.
Aside from a nice treatment of the simplex method, it also contains a very
up-to-date treatment
of interior point methods, including the homogeneous self-dual formulation
and algorithm
(which might soon become the dominant algorithm in practice and theory). It
contains extensive material on issues of implementation of both the
simplex algorithm and
interior point algorithms. A politician might call it a *book for the
21st century.*

**Vanderbei's book has many novel features.** This book is quite
different from most other
textbooks on LP in a number of important ways. For starters, the
*standard form* of a linear
program in the book is the symmetric form of the problem (max c^T x |
Ax <= b, x >= 0),
as opposed to the usual form (min c^T x | Ax=b, x >= 0). This
difference allows for an
easier treatment of duality, and allows one to see the geometry of linear
programming more
easily as well. The symmetric form also makes it easier to set up the
homogeneous self-dual
interior point algorithm. However, this form has the drawback that
discussions of bases, basic
feasible solutions, and some of the mechanics of the simplex method are all
a bit more
awkward. (The book uses the language of *dictionaries* to describe the
essential information
in a simplex method iteration.) The book has more of a focus on
engineering applications than
does the more typcial LP textbook (which tend to rely on business
problems). For example,
there is a nice chapter on optimization of engineering structures such as
trusses. The book
gives a very broad treatment of interior point methods, including several
topics that are not
usually found in textbooks such as the homogeneous self-dual formulation
and algorithm,
quadratic programming via interior point methods, and general convex
optimization via interior
point methods.

These novel features are good in that the author has clearly tried to be innovative and to build an LP text from the ground up, without regard for past texts.

**Some Nice Features.** There are some particularly nice features in
the book.
The book contains a much-simplified variant of the Klee-Minty polytope that
allows for a more
straightforward proof that the simplex method can visit exponentially many
extreme points. In
addition to proving strong duality, the book also presents Tucker's strict
complementarity
theorem, which has become important in the new view of sensitivity analysis,
optimal partitions,
and interior point methods. The book also contains a nice treatment of the
steepest edge pivot
rule, which has recently emerged as an important component in speeding up
the performance of
the simplex algorithm. In the treatment of interior point methods, the
author spends very little
time on polynomial time bounds and guarantees (as a theorist, I like to
see this material),
instead adding value by discussing important computational and implemention
issues,
including ordering
heuristics, strategies for solving the KKT system by Newton's method, etc.
The book sometimes
has an engineer's feel for the proofs, which is good for students but is a
bit frustrating to
hard-core math types such as myself. There are many instances where the
*proof* is just a
proof via an example. This is consistent with the conversational and
informal style of the
text, and this informality spills over into the mathematics on occasion.

**This book has style.** As mentioned earlier, the book has a
wonderfully appealing
conversational style. While the author does not purposely go out of his
way to be cute and
corny, he succeeds in leaving the reader grinning with his humor. There
are some passages that
are downright funny, but the style succeeds mostly by default. One section
on the issue of
modeling the anchoring of truss design problems is called *Anchors Away*,
the subsection on
updating factorizations to reduce fill-in is aptly called *Shrinking the
Bump.* And there is
the hint of a racy discussion of an application of Konig's Theorem
involving boys and girls
that the curious reader might enjoy.

Overall, I greatly enjoyed reviewing this book, and I highly recommend the book as a textbook for an advanced undergraduate or master's level course in linear programming, particularly for courses in an engineering environment. In addition, the book also is a good reference book for interior point methods as well as for implementation and computational aspects of linear programming. This is an excellent new book.