Linear Programming, Second Edition - Foundations and Extensions (International Series in Operations Research and Management Science, Volume 37) (International ... Research & Management Science, 37.) (Hardcover)

by Robert J. Vanderbei (Author) "This book is mostly about a subject called Linear Programming..." (more)
Key Phrases: primal dictionary, uneliminated part, quasidefinite matrix, Minimax Theorem, Max-Flow Min-Cut Theorem, Nobel Prize (more...)

Editorial Reviews

Review

From the reviews:

"This book is highly recommended, it is a must for modern linear programmers." (Short Book Reviews, August (2002)

Product Description
Linear Programming: Foundations and Extensions is an introduction to the field of optimization. The book emphasizes constrained optimization, beginning with a substantial treatment of linear programming, and proceeding to convex analysis, network flows, integer programming, quadratic programming, and convex optimization.

The book is carefully written. Specific examples and concrete algorithms precede more abstract topics. Topics are clearly developed with a large number of numerical examples worked out in detail. Moreover, Linear Programming: Foundations and Extensions underscores the purpose of optimization: to solve practical problems on a computer. Accordingly, the book is coordinated with free efficient C programs that implement the major algorithms studied:

+ The two-phase simplex method; + The primal--dual simplex method; + The path-following interior-point method; + The homogeneous self-dual methods. In addition, there are online JAVA applets that illustrate various pivot rules and variants of the simplex method, both for linear programming and for network flows.Also, check the book's webpage for new online instructional tools and exercises that have been added in the new edition.

Product Details

• Hardcover: 472 pages
• Publisher: Springer; 2nd edition (May 1, 2001)
• Language: English
• ISBN-10: 0792373421
• ISBN-13: 978-0792373421
• Product Dimensions: 9.2 x 6.7 x 1.2 inches
• Shipping Weight: 2 pounds (View shipping rates and policies)
• Average Customer Review: 3.4 out of 5 stars See all reviews (5 customer reviews)
• Amazon.com Sales Rank: #1,106,210 in Books (See Bestsellers in Books)

Customer Reviews

Most Helpful Customer Reviews

15 of 15 people found the following review helpful:

5.0 out of 5 stars Professor Robert Freund's review, April 30, 2004

By A Customer

This is a much more detailed one as compared to the other two and was penned by MIT ORC Professor Robert Freund.

Summary. This book presents a thoroughly modern treatment of linear programming that achieves a healthy balance between theory, implementation, computation, and between the simplex method and interior-point methods. It's most novel feature is that it is written in a delightful and refreshing conversational style, that bespeaks the author's teaching style and relaxed wit. It is a pleasure to read: students will find the book to be friendly and engaging, while professors will find in the book a wealth of teaching material, nicely organized and packaged for classroom use. The book is also meant to be used in conjunction with a public-available website that contains software for various algorithms, additional exercises, and demos of algorithms.
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.

3 of 4 people found the following review helpful:

5.0 out of 5 stars Excellent book, July 17, 2002

By	Levent Oktem (Sunnyvale, CA United States) - See all my reviews

This review is from: Linear Programming : Foundations and Extensions (International Series in Operations Research and Management Science, 4) (International Series in Operations Research & Management Science) (Paperback)

Very clearly written. Unlike most math books, the notation is easy to understand for engineers and programmers. I found the free online version first, and then decided to buy the hard copy.

1.0 out of 5 stars Not a Clear Book, May 26, 2009

By	Carlos Sierra - See all my reviews

I fully agree with J. Pierce. I bought this book because I wanted to refresh the things I learned in the university about linear programming. I don't recall these concepts being so difficult and obscure: when the author introduces a new topic, he does so without trying to explain how does it fit into the general subject, he doesn't bother demonstrating most of the important facts in the book and most of them come as a given. I got to the 4th chapter and I decided to look somewhere else!!!

As I said, I did good when I as studying these topics in the university (simplex method and linear programming), and I just wanted something I could read on my kindle to refresh my memory and get me on track for writing an algorithm I need to solve a somewhat complex linear programming model. If this would have been my first book, I would have thought that the topic was really obscure and difficult to understand!!!

Fortunately I have Hillier and Lieberman's Operation Research book on my bookshelf. I will go back to that one, which I know will do the trick. Unfortunately it isn't available for the kindle, and it is as heavy as a brick, which is what I was trying to avoid when I went shopping for a kindle book on the subject.