You are here

Linear Programming: Foundations and Extensions

Number of Pages: 

Textbooks on linear programming (LP) have traditionally approached the subject by introducing the simplex method using the tableau notation and then going on to discuss the revised simplex method, the dual simplex method, and specialized versions of the simplex method for assignment and network flow problems. Students can easily be lost in the details of the manipulations of the simplex tableau and miss out on many of the important mathematical and computational issues in LP.

Vasek Chvátal (1983) broke new ground with his approach to the subject. Chvátal introduces the simplex method using the notation of dictionaries. Although there is a simple equivalence between dictionaries and tableaus, the dictionary notation makes it much clearer to students that we're simply manipulating a system of equations and inequalities. Chvátal's book was also notable for its elegant approach to duality theory and for its focus on issues of computational complexity. Unfortunately, since it was published just before the advent of interior point methods, there is no discussion of this important aspect of the subject in Chvátal's book.

Robert Vanderbei's textbook on linear programming, now in its third edition, builds on many of the approaches used by Chvátal and includes up-to-date coverage of a number of topics, including interior point methods, that have become important in the 25 years since the publication of Chvátal's book.

Vanderbei's book is divided into four parts. The first part of the book covers the simplex method in dictionary form, the revised simplex method, duality theory, and some applications to convex analysis, game theory, regression, and finance. The second part of the book discusses the application of the simplex method to network flow problems. The presentation of these topics is at a similar level to the presentation in Chvátal's book, but Vanderbei has included some nontraditional topics, including the parametric self dual simplex method, applications in computational finance, and a chapter on applications of network simplex method to problems in the optimization of structures.

Interior point methods for LP, including primal-dual path following methods, affine scaling methods, and the homogeneous self dual embedding are the topic of the third part of the book. The author wisely avoids technical issues in proving that these are polynomial time algorithms. Instead, the author focuses attention on computational issues in the implementation of the methods. Some of the material on the KKT system and the factorization of quasi-definite matrices is unique to this book. Although the author has included a brief section comparing interior point methods and the simplex method, this is a topic that warrants a much more thorough discussion.

The fourth section of the book is made up of three unrelated chapters on integer programming, quadratic programming, and convex optimization. Unfortunately, these topics are only loosely connected to the earlier chapters.

The author has created some useful resources for readers of the book and made them available on his web site. Implementations of the simplex and interior point methods written in C are available for download. Two java applets can be used to manipulate dictionaries and perform simplex pivots. There are also transparencies from the author's lectures.

The first two sections of the book are suitable for use in a first course in linear programming covering the simplex method at the advanced undergraduate or graduate level. For a more advanced course at the graduate level it would be possible to review the material on the simplex method in the first two parts of the book and then thoroughly cover the material on interior point methods in the third part of the book.


Chvátal, Vasek. Linear Programming . W. H. Freeman, 1983.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems. 

Date Received: 
Friday, December 7, 2007
Include In BLL Rating: 
Robert J. Vanderbei
International Series in Operations Research and Management Science 114
Publication Date: 
Brian Borchers
Publish Book: 
Modify Date: 
Thursday, May 22, 2008