Linear programming is a method for solving complex, real-life business problems, using the power of mathematics. Organizations have been applying this method for 50+ years, across nearly all industries, to optimize operational efficiency—to get the most value from their limited resources. For example:
Before you even start programming, you’ll need to collect some important information about your business problem:
Then, you need someone with mathematical and programming know-how to express this information as a mathematical model—in this case, a linear program. This requires some linear algebra and calculus skills, plus familiarity with mathematical notation and basic Python knowledge.
Not mathematically minded? Our trusted partners can handle that for you.
As a final step, you will input your linear program into a “solver” (such as the Gurobi Optimizer), and the solver quickly determines how you can best reach your goals, given your limitations, and outputs a recommended action plan that answers your specific questions.
Although there are countless ways to use linear programming, let’s look at a relatively simple one: the Furniture Factory Problem.
Imagine there’s a data scientist who’s in charge of developing a weekly production plan for a factory’s chairs and tables—two key products for this particular furniture factory.
The data scientist, using machine learning, predicts that the selling price of a chair is $45, and the selling price of a table is \$80.
Building a chair requires two critical resources:
|
Each week, the factory will have access to:
|
The data scientist estimates:
|
The challenge: To identify how many chairs and tables to make, to maximize total revenue while satisfying the resource constraints.
This is a classic linear programming challenge. Find out how it works through our helpful Linear Programming Tutorial Video Series, which walks you through the entire process.
You’ve come to the right place! We have a robust library of functional code examples and Jupyter Notebook modeling examples. These are a great way to jump in and start digging into the code and trying out your own variations.
Linear programming (LP) is a powerful framework for describing and solving optimization problems. It allows you to specify a set of decision variables, and a linear objective and a set of linear constraints on these variables.
To give a simple and widely used example, consider the problem of minimizing the cost of a selection of foods that meets all the recommended daily nutrient guidelines. The LP model would have:
Using linear algebra notation, a linear program can be described as follows:
When described in this form, the vector x represents the decision variables, the vector c captures the linear objective function, the matrix equation Ax = b specifies the linear constraints on x, and the vectors l and u give the lower and upper bounds on x.
The set of applications of linear programming is literally too long to list. It includes everything from production scheduling to web advertising optimization to clothing manufacturing. LP touches nearly every commercial industry in some way.
Linear programming was first introduced by Leonid Kantorovich in 1939 and then independently reintroduced by George Dantzig in 1947. Dantzig developed the first algorithm for solving linear programming problems, called the “simplex” method. Remarkably, this decades-old algorithm remains one of the most efficient and reliable methods for solving such problems today.
Learn more about the simplex method in practice.
The primary alternative to the simplex method is the barrier or “interior-point” method. This approach has a long history, but its popularity is due to Karmarkar’s 1984 polynomial-time complexity proof.
Interior-point methods have benefited significantly from advances in computer architecture, including the introduction of multi-core processors and SIMD instruction sets, and they are generally regarded as being faster than simplex for solving LP problems from scratch.
However, the sheer variety of different linear programming models—and the many ways linear programming is used—mean that neither algorithm dominates the other in practice. Both are important in computational linear programming.
Given that the simplex and interior-point algorithms have been solving linear programs for decades, you might expect that all solvers (which use those algorithms to solve the linear programming models) would perform the same. But this is far from the case.
Computational benchmarks—across a range of models—show wide performance and robustness variations between solvers. For example, the open-source simplex solvers CLP and GLPK are, on average, a factor of 2.5 and 58 times slower than the Gurobi simplex solver, respectively.
What explains such wide disparities between implementations of such well-established methods? The differences primarily come down to three factors.
The constraint matrices that arise in linear programming are typically extremely sparse. Sparse matrices contain very few non-zero entries. It is not unusual to find constraint matrices containing only 3 or 4 non-zero values per columns of A. The steps of both the simplex and interior-point algorithms involve a number of computations with extremely sparse matrices and extremely sparse vectors. Sparse matrices must be factored, systems of sparse linear equations must be solved using the resulting factor matrices, the factor matrices must be modified, etc. It takes years of experience in sparse numerical linear algebra and linear programming to understand the computational issues associated with building efficient sparse matrix algorithms for LP.
The second factor is careful handling of numerical errors. Whenever you solve systems of linear equations in finite-precision arithmetic, you will always get slight numerical errors in the results. A crucial part of building an efficient LP algorithm is to design effective strategies for managing such errors. Failing to do so can mean the difference between a model solving in a fraction of a second and not solving at all.
The third factor is developing effective heuristic strategies for making the variety of choices that arise in the course of the solution process. To give one example, the simplex algorithm must repeatedly pick one variable from among many to enter the basis. The strategy used can have a profound effect on the runtime of the algorithm. Differences between the different strategies are often quite subtle, and in many cases, they are simply based on empirical observations about which schemes are most effective in practice. Again, choosing effective strategies takes years of experience.
Public benchmarks of different commercial linear programming solvers demonstrate the effectiveness of the approaches that Gurobi has taken for each of these issues. For both the simplex and barrier methods, the Gurobi solver provides both higher performance and better numerical robustness than competing solvers.
This difference matters when you are solving linear programming models, but more importantly, it also provides a more solid foundation on which to build the many algorithms that rely on linear programming as a subroutine. One very important example is the branch-and-bound algorithm that is used for solving mixed integer programming (MIP) models.
Ready to learn about mixed integer programming—another key type of mathematical programming? Check out our Mixed Integer Programming (MIP) Primer as well as our Recommended Books and Blogs.
GUROBI NEWSLETTER
Latest news and releases
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.