Browse Books

Reviewer: Thomas L. Clarke

This comprehensive introduction to linear programming is intended for advanced undergraduates and first-year graduate students. Following the introduction, a quick review of linear algebra and the concepts of convex analysis establishes the level of mathematical maturity expected. The next three chapters are devoted to the simplex method, the basic algorithm, starting and convergence problems, and special implementations. The coverage of the simplex method is rounded out by a discussion of duality and a consideration of methods for decomposing large problems into more manageable pieces. One chapter is devoted to the new Khachian and Karmarkar polynomial time linear programming algorithms. The treatment centers on Karmarkar's projection algorithm, which has proven more useful in practice than Khachian's ellipsoidal algorithms. This material is welcome because access to these new algorithms has been impeded by commercial and proprietary concerns. Chapter 9 introduces the graph theory needed for dealing with the network flow minimization problem. The simplex method provides a solution technique that is a natural fit for network flow problems. The similarly networked structured transportation and assignment problems receive a chapter of their own. Chapter 11 introduces the out-of-kilter algorithm for network flow problems, which is related nicely to dual simplex algorith ms. The final chapter considers several generalized flow topics, including multiple commodity flows and the network synthesis problem. As the authors suggest, the material in this book would be sufficient for a year course in linear programming and network flows. Several different semester courses covering linear programming only, networks only, or some combination of the two could also use this text. For much of the book, the authors depart from the usual theorem/proof format. Instead, they successfully strive to build intuition through the use of many drawings and numerical examples. Nevertheless, the book is well enough indexed to serve as a reference beyond the course. The bibliography is extensive and up to date. Each chapter concludes with notes and references that provide a good entry to the literature. In summary, this well-thought-out book will amply reward those who take the time to master its material.