Developing the Simplex Method with NumPy and Matrix OperationsSam GrassiBlockedUnblockFollowFollowingMay 25In this post, I seek to address the paucity of resources describing and implementing the Simplex Method from a matrix operations perspective.
In particular, most computational implementations of the Simplex Method are developed by directly implementing the Simplex tableau method.
As such, in this post I seek to give an alternative implementation of the Simplex Method by developing a program of the Simplex Method that leverages matrix operations instead of the tableau method.
I avoid the mathematics of the particular matrix operations implementation to keep this post concise, however if the reader wishes to learn more about the mathematics of this particular implementation, they can refer to the book Linear and Nonlinear Programming by Stephen Nash and Ariela Sofer, which gives a great introduction into the Simplex Method and the many ways to implement it.
The book Linear Programming and Network Flows by Bazaraa, Jarvis, and Sherali is also a great in-depth resource that touches upon many of the ideas mentioned in this post.
The Simplex Method, invented by the late mathematical scientist George Dantzig, is an algorithm used for solving constrained linear optimization problems (these kinds of problems are referred to as linear programming problems).
Linear programming problems often arise in operations research related problems, such as finding ways to maximize profits given constraints on time and resources.
Linear programming problems consist of two key elements: an objective function and a system of linear inequalities.
The fundamental goal in solving such linear programming problems is to maximize or minimize the objective function given the linear constraints on the solution.
The systems of linear inequalities creates a feasible region, such that the optimal solution must lie within the feasible region.
This feasible region formed by the linear inequalities is a convex polytope, where a visualization of such a region is given below.
A Convex PolytopeAs seen in the image, the constraints are linear, so the convex polytope has flat edges, and the feasible region is the interior and boundary of the polytope.
A key insight is that the optimal solution to any constrained linear optimization problem is always on one of the corners of the convex polytope.
It is with this insight that we can motivate the development of the Simplex Method.
The Simplex Method starts at some point within the feasible region, and then with each iteration of the algorithm maps from one adjacent corner (representing a possible solution to the problem) of the convex polytope to another, such that each step gives a better or equivalent solution than the one in the previous step.
This is hardly a satisfactory description of the Simplex Method, so if the reader wants a more insightful intuition into the method, I recommend visiting this article, or watching the first two short videos on the Simplex Method video series by PatrickJMT, which give a good introduction into the kinds of problems the Method solves and how it works.
Upon taking classes in operations research or optimization (particularly at the undergraduate level) and reviewing the resources available online that cover the Simplex Method, one will almost certainly be introduced to the tableau method for solving linear programming problems with the Simplex method.
Some examples of solving linear programming problems with the tableau method are given here and here.
Unfortunately, the tableau method is often the only method mentioned in classes or texts covering the Simplex Method.
As such, many of the computer programs implementing the Simplex Method directly implement the tableau method.
The tableau method was developed to solve linear programming problems by hand, with pencil and paper.
As such, it is not computationally efficient, and should not be the chosen method when implementing the Simplex Method in computational form.
In the following embedded Jupyter Notebook, I implement a version of the Simplex Method that uses matrix operations in NumPy instead of the tableau method to solve linear constrained optimization problems.
As such, we obtain a far more efficient, concise, and natural implementation of the Simplex Method.
If the reader wishes to follow along with the exact mathematics and notation used in the following program, refer to Chapter 5 of Linear and Nonlinear Programming by Nash and Sofer.
The Simplex Method is seldom used in practice today, having been overcome by faster interior point methods.
However, when the Simplex Method is implemented in practice, it is usually developed with matrix factorizations, which offer an implementation of the Simplex Method that is even faster than using the matrix operations method given in this post.
For lower dimensional linear programming problems, the matrix operations method given here is fine, however as one begins to solve problems with hundreds or thousands of variables, it makes more sense to implement the Simplex Method using matrix factorizations.
It is my hope that this post gave the reader a high level intuition into the less mentioned but ultimately superior methods of implementing the Simplex Method, and that the program offered serves as a useful alternative to other less efficient implementations of the Simplex Method that use the tableau method.
.