Ebook: Primal-Dual Interior-Point Methods

There are basically 2 well-developed practical methods that dominate the solution methods known for solving linear programming (linear optimization) problems on the computer. The first one is the "Simplex Method" which was first developed in the 1940s but has since evolved into an efficient method through the use of many algorithmic and memory storage tricks. The other methods are much newer, starting in 1984, and are called "Interior-Point Methods". Interior-Point Methods are actually subdivided into many possible variations, thus making this field confusing to the newcomer. During the last decade, the Interior-Point Methods have matured and the picture is now much clearer. This book is perhaps the easiest one I know that explains some of the best performing Interior-Point Methods. Should you desire more introductory material about linear programming, an excellent companion to the above book would be "Optimization in Operations Research" by Rardin, although Rardin has only one chapter about Interior-Point Methods (I haven't read this book, but the reviews sound like this book is the best general introduction to linear programming and other optimization problems). It's tempting to say that you should learn the Simplex Method first before going on to Interior-Point methods--but I'm sure there are others who would disagree. As far as I know, the older Simplex Method can still be quite competitive--some problems are solved faster by the Simplex Method while other problems are solved faster using Interior-Point Methods. Nevertheless, this is a dynamic field of research and what is now true about the comparisons between these 2 methods can easily become false in the near future.