You are here

Understanding and Using Linear Programming

J. Matoušek and B. Gärtner
Springer Verlag
Publication Date: 
Number of Pages: 
BLL Rating: 

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

[Reviewed by
Fabio Mainardi
, on

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

Preliminary.- 1 What is it, and what for?- 2 Examples.- 3 Integer Programming and LP Relaxation.- 4 Theory of Linear Programming: First Steps.- 5 The Simplex Method.- 6 Duality of Linear Programming.- 7 Not Only the Simplex Method.- 8 More Applications.- 9 Software and Further Reading.