There are many optimization problems from real life that can be modelled as linear programs: diet optimization, maximum transfer rate between computers, least squares fitting, finding the largest disk in a convex polygon, finding the maximum set of independent vertices in a graph, and many others. But what is exactly a linear program? In mathematical terms, one wants to maximize (or minimize) a linear function, subject to certain constraints, given in the form of linear inequalities. The number of variables and inequalities is often huge, so it is necessary to have efficient algorithms, to be implemented with computers. The most popular algorithm is probably the simplex algorithm, which occupies chapter 5 of the book.
The author’s guiding phrase is “what every theoretical computer scientist should know about linear programming”. However, the book is of interest to mathematicians as well, at least to mathematicians with a taste for interdisciplinary questions.
The only prerequisite for this book is a basic knowledge of linear algebra (an appendix reviews some of the theory at the end of the book). Beyond that, it is self-contained; in fact, every tool from general mathematics (e.g convex functions, Lagrange multipliers) is recalled when needed. For a mathematician, this book is easy and pleasant reading. A number of examples and illustrations is provided throughout the book.
It is the author’s choice to write an introductory book on linear programming, with no claim of completeness: in fact, there is a plethora of thicker, more advanced publications on this topic. Here you will find a clear description of three algorithms: the simplex method, the ellipsoid method, the interior point method. Also covered in this book are duality theory, the Farkas lemma, and sparse solutions of linear systems.
It should be clear that this book is not about programming. You won’t find the implementation of these algorithms, and you don’t need any background in computer science.
The book is well written and well organized; I recommend it to undergraduate students and also to ‘pure mathematicians’ wishing to learn some beautiful applied mathematics. Unfortunately, there are no exercises in the book; it is essential for the reader to works out the examples himself in order to understand in depth how and why everything works.
A glossary concludes the book and serves as a very quick overview of topics not covered by the main text.
I recommend this book to computer scientists and mathematicians willing to learn the fundamentals of linear programming, and some of its many applications.
Fabio Mainardi earned a PhD in Mathematics at the University of Paris 13. His research interests are Iwasawa theory, p-adic L-functions and the arithmetic of automorphic forms. He may be reached at firstname.lastname@example.org.