Linear Programming: Foundations and Extensions

By Robert J. Vanderbei

Book Overview

This book focuses largely on constrained optimization. It begins with a substantial treatment of linear programming and proceeds to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. Along the way, dynamic programming and the linear complementarity problem are touched on as well. This book aims to be the first introduction to the topic. Specific examples and concrete algorithms precede more abstract topics. Nevertheless, topics covered are developed in some depth, a large number of numerical examples worked out in detail, and many recent results are included, most notably interior-point methods. The exercises at the end of each chapter both illustrate the theory, and, in some cases, extend it. Optimization is not merely an intellectual exercise: its purpose is to solve practical problems on a computer. Accordingly, the book comes with software that implements the major algorithms studied. At this point, software for the following four algorithms is available: The two-phase simplex method The primal-dual simplex method The path-following interior-point method The homogeneous self-dual methods. /LIST .

• Format: Paperback
• Language: English
• ISBN: 0792381416
• ISBN13: 9780792381419
• Release Date: March 1998
• Publisher: Springer
• Length: 418 Pages
• Weight: 1.64 lbs.
• Dimensions: 0.9" x 6.4" x 9.2"

Customer Reviews

Professor Robert Freund's review

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 = 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 symmet