Linear programming is one of the fundamental approaches to mathematical optimization. Optimization professionals can adopt a number of linear programming methods and algorithms when developing their solution, including the simplex method.
If linear programming is right for you, this tutorial can help you get started with the basics.
Linear models can graphically map the area of feasible solutions. Due to the many variables and constraints involved, the area is a complex polytope. The simplex method starts with a feasible solution for the optimization problem, and then iterates on the solution by evaluating how it compares to its neighboring vertices (i.e., corners) of the polytope.
This approach works for two reasons:
To begin linear programming with the simplex method, it is assumed that an extreme point is known.
Once a basic feasible solution (or “extreme point”) is known, the algorithm then compares that outcome to the two neighboring corners of the polytope.
If one is a more optimal solution, the algorithm then compares the more optimal solution to its neighboring vertices. It continues iterating until it identifies a solution with no neighboring vertices that are more optimal.
For more detailed instructions on linear programming with the simplex method, check out this tutorial.
The simplex method allows mathematical optimization professionals to analyze complex problems in a relatively straightforward way.
While the simplex method has many strengths, a few factors may delay progress. The first is ensuring that a feasible solution exists, given the constraints. In some cases, feasibility will be immediately apparent.
The second factor affecting the simplex method is identifying the initial feasible solution vertex. While the workshop example above has an easily identified initial solution, most problems will have many more variables and constraints. The solver may need to devote significant time to identifying an initial vertex for the solver to begin comparing.
The third factor affecting this approach’s performance is complexity. While the simplex method excels at identifying optimal solutions to complex problems, a high number of variables can increase the number of vertices exponentially. This means the most complex problems can take a long time to solve with this approach.
The simplex method is a straightforward way for solvers like Gurobi to find an optimal solution to complex problems. Under the right circumstances, it may be the best approach for your key business questions. To learn more about the various approaches to linear programming, check out Gurobi’s resources.
Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.
Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.