You are here

Linear Programming: An Introduction to Finite Improvement Algorithms

Daniel Solow
Publisher: 
Dover Publications
Publication Date: 
2014
Number of Pages: 
414
Format: 
Paperback
Edition: 
2
Price: 
24.95
ISBN: 
9780486493763
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Allen Stenger
, on
06/11/2016
]

This book gives thorough coverage of the theory of the simplex algorithm for linear programming, and almost as thorough coverage of its practice. The present book is a Dover 2014 unaltered reprint of the 1984 North-Holland edition that adds a new preface and a new appendix on using Microsoft Excel to solve linear programming problems.

The book was very prescient to realize in 1984 that most of the calculation would be done by computers, and so it teaches by focusing on strategies and the geometric motivation rather than algorithms. It’s also very strong in problem formulation (deciding how to represent real-world problems as linear programs). Interior-point methods were just being developed when the book was published, and so are not covered here.

The novel feature of this exposition is that it explains everything in terms of matrix operations, and holds off on the simplex tableau until the very end. Chapter 4 develops all the needed matrix algebra (it focuses on solutions of systems of equations, not on operators and eigenvalues). This is a very strong approach, because it allows us to use our knowledge of linear algebra to improve our algorithms. In particular there is a good discussion of the use of LU-decomposition and some discussion of sensitivity analysis. In most books the simplex method is presented as a ritual, and it’s barely clear how it works, much less how to improve it.

This is also a proofs book, and all needed results are proved in the text. Chapter 3 covers proof techniques for beginners, and is a very condensed version of the same author’s How to Read and Do Proofs. Each theorem is equipped with an “outline of proof” that explains the method of attack, followed by the formal proof. Most of the exercises are numerical, with only a few items to prove.

Bottom line: still a good book, although the audience has shifted, and today it is more a specialized reference on linear programming and not as useful as an introduction. Very good computer codes are available today (these were just becoming available in 1984 when the book was first published), and most people won’t need the detailed algorithmic knowledge that is in this book. The field of optimization has grown greatly since the book’s initial publication, and I think undergraduate math majors would be better served by a good survey of optimization, such as Guenin & Könemann & Tunçel’s A Gentle Introduction to Optimization.


Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.

Introduction to the Dover Edition

Preface

Acknowledgements

Chapter 1. Problem Formulation

Chapter 2. Geometric Motivation

Chapter 3. Proof Techniques

Chapter 4. Linear Algebra

Chapter 5. The Simplex Algorithm

Chapter 6. Phase 1

Chapter 7. Computational Implementation

Chapter 8. Duality Theory

Chapter 9. Sensitivity and Parametric Analysis

Chapter 10. Techniques for Handling Bound Constraints

Chapter 11. Network Flow Problems

Appendix A. The Tableau Method

Appendix B. How Efficiently Can We Solve LP Problems?

Appendix C. Spreadsheet Modeling Using Excel

Index