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. English Brand New Book. In the past decade, primal-dual algorithms have emerged as the most important and useful algorithms from the interior-point class. This book presents the major primal-dual algorithms for linear programming in straightforward terms. A thorough description of the theoretical properties of these methods is given, as are a discussion of practical and computational aspects and a summary of current software. This is an excellent, timely, and well-written work. The major primal-dual algorithms covered in this book are path-following algorithms (short- and long-step, predictor-corrector), potential-reduction algorithms, and infeasible-interior-point algorithms. A unified treatment of superlinear convergence, finite termination, and detection of infeasible problems is presented. Issues relevant to practical implementation are also discussed, including sparse linear algebra and a complete specification of Mehrotra s predictor-corrector algorithm. Also treated are extensions of primal-dual algorithms to more general problems such as monotone complementarity, semidefinite programming, and general convex programming problems
