What is Linear Programming?

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:

  • Transportation providers, such as Air France, Swissport, and Uber, use mathematical programming to create optimal routing, staffing, and maintenance plans.
  • Professional sports leagues, including the National Football League and Beko BBL, plan their game schedules using mathematical programming.
  • Manufacturers use mathematical programming to plan and manage the procurement, production, and distribution of their products.

 

How Does Linear Programming Work?

Before you even start programming, you’ll need to collect some important information about your business problem:

  • The questions you’re asking (“decision variables”)
  • The goals you need to achieve (“linear objectives”)
  • The limitations you’re facing (“linear constraints”)

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.

 

What Is an Example of Linear Programming?

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:

  • Mahogany (measured in board square feet)
  • Labor (measured in hours)

 

Each week, the factory will have access to:

  • 400 units of mahogany
  • 450 units of labor

 

The data scientist estimates:

  • One chair requires five units of mahogany and 10 units of labor
  • One table will require 20 units of mahogany and 15 hours of labor

 

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.

 

Where Can I Find More Linear Programming Code Examples?

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.

 

What Are Decision Variables, Linear Objectives, and Linear Constraints?

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:

  • A set of decision variables that capture the amount of each food to buy.
  • A linear objective that minimizes the total cost of purchasing the chosen foods.
  • A linear constraint for each nutrient, requiring that the chosen foods together contain a sufficient quantity of that nutrient.

 

Using linear algebra notation, a linear program can be described as follows:

  • Objective: minimize cTx
  • Constraints: A x = b (linear constraints) l ≤ x ≤ u (bound constraints)

 

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.

 

What is the Simplex Method for Solving Linear Programming Models?

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.

 

How Does the Simplex Method Differ from the Interior-Point Method?

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.

 

What Makes Gurobi a Solver of Choice for 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.

1. Sparse Linear Algebra

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.

2. Numerical Error Handling

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.

3. Heuristic Strategies

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.

 

Benchmark Results

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.

 

Guidance for Your Journey

30 Day Free Trial for Commercial Users

Start solving your most complex challenges, with the world's fastest, most feature-rich solver.

Always Free for Academics

We make it easy for students, faculty, and researchers to work with mathematical optimization.

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Search