Linear Programming Basics

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, and 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 cTConstraints: 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.

 

Linear Programming Algorithms

The first algorithm for solving linear programming problems was the simplex method, proposed by George Dantzig in 1947. Remarkably, this 65 year old algorithm remains one of the most efficient and most reliable methods for solving such problems today. The primary alternative to the simplex method is the barrier or interior-point method. This approach has a long history, but its recent popularity is due to Karmarkar’s 1984 polynomial-time complexity proof. Interior-point methods have benefited significantly from recent advances in computer architecture, including the introduction of multi-core processors and SIMD instructions sets, and are generally regarded as being faster than simplex for solving LP problems from scratch.  However, the sheer variety of different LP models, and the many different ways in which LP is used, mean that neither algorithm dominates the other in practice. Both are important in computational linear programming.

 

Computational Linear Programming

Given the age of these algorithms (65 years for the simplex method, and 28 years for interior point methods), you might expect that the implementation issues associated with the methods would be well understood, and that different implementations would give similar results. Surprisingly, this is far from true. Computational benchmarks across a range of models show wide performance and robustness variations between different implementations. 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 old and well-established methods? The differences primarily come down to three factors.

Sparse Linear Algebra

The first factor is 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.

Dense Matrix

Sparse Matrix

Numerical Errors

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.

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 LP 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 solvers provide both higher performance and better numerical robustness than competing solvers. This difference is of course relevant when you are solving LP models, but more importantly, it also provides a more solid foundation on which to build the many algorithms that rely on LP as a subroutine. One very important example is the branch-and-bound algorithm that is used for solving Mixed Integer Programming (MIP) models.

 

References

If you would like more information on these methods, we refer you to the following books:

  • Bertsimas, D., and Tsitsiklis, J., Introduction to Linear Optimization, 1997.
  • Vanderbei, R., Linear Programming: Foundations and Extensions, 2010
  • Wright, S., Primal-Dual Interior-Point Methods, 1997.

Guidance for Your Journey

Gurobi: Always Free for Academics

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

Trusted Partners, at Your Service

When you face complex optimization challenges, you can trust our Gurobi Alliance partners for expert services.

We’ve Got Your Back

Our global team of helpful, PhD-level experts are here to support you—with responses in hours, not days.

What's
New at Gurobi

News
Gurobi 10.0 Delivers Blazing-Fast Speed, Innovative Data Science Integration, and an Enterprise Development and Deployment Experience
Latest release enables data professionals to easily integrate machine learning models into optimization models to solve new types of problems.
 Learn More
Event
Webinar: What’s New in Gurobi 10.0
In this webinar, attendees will get a first look at our upcoming product release, Gurobi 10.0. We will summarize the performance improvements and highlight some of the underlying algorithmic advances, such as the network simplex algorithm, enhancements in concurrent LP, and optimization based bound tightening.
 Learn More
new content
Cost Savings & Business Benefits for Gurobi Customers
2022 Total Economic Impact™ Study Reveals A 518% ROI with Gurobi
 Learn More