The author claims that this short monograph is a self-contained mathematical introduction to the theory of linear programming. It is intended for mathematically sophisticated undergraduates and graduate students. A reader should be versed in linear algebra and comfortable with mathematical proofs. For example, the spectral theorem for symmetric matrices is stated without proof. The book is a theoretical monograph with no exercises or application code. It is tightly written and well crafted, and is a direct outgrowth of a series of lecture notes.
The titles of the five chapters are descriptive:
The Basics
The Simplex Algorithm
Duality
The Ellipsoid Algorithm
Karmarkar’s Algorithm
Karloff does not waste words. The material in the first chapter states the relevant facts and theorems required in succeeding chapters. Chapter 2 begins with a nontrivial but toy example that is carefully solved and brings cogent theory to bear as required. The mathematical formalism is precise, with no handwaving. We do not see graphical figures with a solver marching from extreme point to extreme point of the feasible region. Initialization, careful pivoting rules to avoid cycling, and performance are covered nicely. Duality is covered straightforwardly in a scant 20 pages in chapter3. Nothing about the first three chapters is remarkable. The value of the monograph is the excellence of the last two chapters. Both are eminently readable. One possible cause for concern is that readers can be lulled into a sense of understanding that then betrays those who did not completely understand the explanations.
The chapter on the ellipsoid algorithm gives a careful description of the algorithm. The central theme is that the ellipsoid algorithm provides a polynomial-time algorithm for the linear strict inequalities problem, and this can be used to construct a polynomial-time linear programming algorithm. The details could be found in other texts [1]. This chapter follows nicely from the first three chapters, however, and is a good read.
Finally, the chapter on Karmarkar’s algorithm gives an excellent introduction to the projection transformation method. It contrasts nicely with the exterior point methods of the previous chapter. The reader is thus introduced to interior point methods. The level of difficulty of the mathematics is comparable to that of the chapter on the ellipsoid algorithm. The presentation of the last two chapters is such that a reader can work through the mathematics of the important algorithms and gain valuable insight.
The shortcomings of the monograph include the fact that only toy examples, as opposed to real-world problems, are solved in detail. Larger problems are beyond the scope of the author’s intent, but some readers may feel cheated.
The author provides a bibliography of 61 references. Comments throughout the monograph referring to the items in the bibliography ease the way for the reader who seeks additional details and examples. The index is brief, but the reader will be well served by reading the monograph from cover to cover. The author succeeds in providing a concise, readable, understandable introduction to modern linear programming.
