Linear Programming: An essential optimization technique
Linear programming was revolutionized when CPLEX software was created over 20 years ago: it was the first commercial linear optimizer on the market written in the C language, and it gave operations researchers unprecedented flexibility, reliability and performance to create novel optimization algorithms, models, and applications. In fact, the name CPLEX itself is a pun built on the concept of a Simplex algorithm written in C: C-Simplex gave CPLEX. The Simplex algorithm, invented by George Dantzig in 1947 became the basis for the entire field of mathematical optimization and provided the first practical method to solve a linear programming problem. Of course, CPLEX evolved over time to embrace and become a leader in the children categories of linear programming, such as integer programming, mixed-integer programming and quadratic programming, too.
Depending on how familiar you are with linear programming, you may be interested in various levels of information around linear programming and how they are handled by CPLEX. The information presented below goes from the highest level fundamental explanation of what linear programming is (and how it runs in CPLEX) down to more advanced notions. At the end, you will also find some external classic references on linear programming.
Linear Programming: An essential optimization technique
If you're a total newcomer to linear programming, you first may want to see how business managers can use optimization to produce concrete, measurable improvements in performance. As abstract as the mathematics appears to be, it has powerful capabilities that enable businesses to reduce costs, improve profitability, use resources effectively, reduce risks, and provide benefits in many other key dimensions. Furthermore, optimization can automate decision processes to improve speed of responses and allow managers to focus their attention on critical uncertainties rather than routine matters. And these benefits have been demonstrated in numerous real-world implementations. Get your feet wet by first understanding what optimization can do for your business.
The concept behind a linear programming problem is simple. It consists for four basic components:
- Decision variables represent quantities to be determined
- Objective function represents how the decision variables affect the cost or value to be optimized (minimized or maximized)
- Constraints represent how the decision variables use resources, which are available in limited quantities
- Data quantifies the relationships represented in the objective function and the constraints
In a linear program, the objective function and the constraints are linear relationships, meaning that the effect of changing a decision variable is proportional to its magnitude. While this requirement may seem overly restrictive, many real-world business problems can be formulated in this manner. That provides a powerful and robust analytical methodology for supporting fact-based decision making.
For example: If you want to decide how to supply of each kind of product in order to minimize your costs, you have to do that within a set of constraints. For instance you have to be able to produce enough to satisfy the demand on all your various products and you have to do it within the capacity you have, which can produce units at a given cost.
In more mathematical terms, here's what a linear program would look like in the OPL language:
Here's an example linear program. A manufacturer wants to sell a product. The product can either be made inside the factory or purchased outside. Inside production uses scarce capacity, and there is an inside cost per unit to manufacture.
Outside acquisition has a higher outside cost per unit to purchase but uses none of the scarce capacity. Using both sources, all demand must be satisfied. The goal is to minimize total cost.
For linear programming, there are fast implementations of the primal simplex algorithm, the dual simplex algorithm, the network simplex algorithm, as well as a barrier method. All of these algorithms use the automatic CPLEX pre-solve algorithms to speed up performance.
The above example is an excerpt from our on-demand video Introduction to CPLEX. This presentation is the perfect jumpstart to IBM ILOG CPLEX Optimizer if you're already familiar with mathematical programming. You'll be able to dive deeper into:
- Various algorithms CPLEX offers not only for linear programming, but also integer programming, mixed integer programming, and quadratic programming
- Basics on how to build CPLEX applications
- What interfaces and connectors are available
- How CPLEX achieves great performance
- How CPLEX uses parallel processing
- The Getting Started Manuals can also give you a good overview of linear programming. You can have some hands-on practice with tutorials based on OPL. The OPL manuals include a section on application which details several different linear programming formulations.
Examples of problems solved with linear programming
IBM ILOG CPLEX Optimization Studio can also be a very good entry point for a hands-on approach to learning linear programming.
|Supply chain||Product deployment|
|Time tabling||Manpower planning|
Quadratic and Quadratically Constrained Programming
In quadratic programs, the objective function can have both quadratic and linear terms. Quadratic objective functions to be minimized can be either convex, where there is a unique solution, or non-convex, where there can be many solutions. CPLEX can solve both convex and non-convex quadratic to global optimality. Similarly, for maximization problems, CPLEX will find the unique solution to a concave problem and a first-order solution to a non-concave problem. Problems which are neither convex nor concave are also called indefinite. CPLEX has both barrier and simplex algorithms for solving convex quadratic programs and a barrier algorithm for solving non-convex problems.
CPLEX can also solve problems with convex quadratic constraints. These problems can also be formulated as second-order cone programs (SOCPs), including formulations with rotated cones.
Sometimes, linear relationships are not enough to capture the essence of a business problem. This is particularly true when decisions involve discrete choices, such as whether or not to open a warehouse at a particular location. For these situations, you need to use integer programming (or if the problem includes both discrete and continuous choices, it is a mixed integer program). Mixed integer programs can have linear or convex quadratic objectives and linear, convex quadratic or second-order cone constraints.
Examples of Mixed Integer Programming Problems
- Vehicle routing
- Facility location
- Personnel scheduling
- Power plant commitment
- Costs with fixed and variable components
- Materials cutting
- Network design
Integer programs are much harder to solve than linear programs, but they have important business applications. CPLEX uses sophisticated mathematical techniques to solve very hard integer programs. These techniques involve systematically searching over possible combinations of the discrete decision variables, using linear or quadratic programming relaxations to compute bounds on the value of the optimal solution. They also use linear programming and other techniques to compute linear constraints that cut off possible solutions that violate the discreteness constraints. CPLEX's innovative technologies have made it possible to solve mixed-integer programs that were previously considered intractable, thus enabling use of optimization in important business applications
More resources on linear programming, with or without CPLEX
- Model Building in Mathematical Programming (link resides outside of ibm.com) - H.P. Williams - Wiley
- Linear Programming: Foundations and Extensions (link resides outside of ibm.com) - Robert J. Vanderbei - Springer
Considering a purchase?
Technical discussion around ILOG Optimization products including CPLEX