Linear Programming Using MATLAB®

There are several good textbooks for Operations Research, typically covering both the theory behind linear programming as well as the wide range of different types of problems that can be solved. One classic text is Hillier and Lieberman’s Introduction to Operations Research, which spends the first several chapters on the theory behind the simplex method and linear programming in general, and then later chapters on specific types of problems, such as network optimization, integer programming, etc. Since operations research is so applicable in the real world, and such problems tend to be computationally heavy, it’s no surprise that there are many different software packages available to do the calculations for large-scale linear programming problems. Ploskas and Samaras’ book is dedicated to discussing the theory behind the simplex method and showing how the computational software MATLAB® can be used to solve linear programming problems.

Although the book covers many of the standard topics, it seems to assume some familiarity with these topics going in, and focuses on using MATLAB to solve given problems in different ways. As an example, consider Chapter 6: Pivoting Rules. The simplex method uses Dantzig's rule, in which the entering variable is chosen by the largest (in a negative sense) negative coefficient of the objective function equation. However, this choice doesn’t necessarily lead to the optimal solution with the fewest number of pivot operations. Several other rules are presented here: Bland’s rule, the Greatest Increment Method, the Least Recently Considered Method, the Partial Pricing rule, and the Steepest Edge rule.  The key issue is whether the extra computational work at the front end is worth the reduction in computation at the back end. (On average, no.) The algorithms for these methods are presented in the text, along with a computational study of these methods applied to a set of Linear Programming Benchmark problems. These benchmark problems (which involve several ill-conditioned and highly degenerate problems) are used throughout the book to test various algorithms and their efficiency.

The topics covered in this text include: the theory of the simplex method (along with variations such as the dual simplex method and interior and exterior point methods), presolve methods and scaling techniques, and sensitivity analysis. There are no exercises in the book, but there are many examples and references included. And there are two appendices, covering MATLAB’s Optimization Algorithms and the Computational Infrastructure for Operations Research (COIN-OR). This is a good book to have sitting next to your standard OR text.

Donald L. Vestal is an Associate Professor of Mathematics at South Dakota State University.  His interests include number theory, combinatorics, spending time with his family, and working on his hot sauce collection.  He can be reached at Donald.Vestal(AT)sdstate.edu