Linear programming

Linear programming and CPLEX Optimizer

Introduction to CPLEX: Linear programming and beyond. Watch the on demand video.

Introduction to CPLEX: Linear programming and beyond

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.

Linear Programming

The concept behind a linear programming problem is simple. It consists for four basic components:

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:

Decision VariablesDecision Variables 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:

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. In the OPL documentation, you'll be able to find a valuable model library, and you'll be able to work on the following problems:

Industry Problem
Manufacturing Blending
Economic planning
Factory planning
Farm planning
Food manufacturing
Refinery planning
Supply chain Product deployment
Time tabling Manpower planning
Transportation Network flows

Practice expressing linear programming problems with OPL by reviewing the OPL and IDE Getting Started Manual and the ILOG CPLEX Optimization Studio Preview Edition.

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 programs but in the case of non-convex problems, only can find a solution meeting first-order optimality conditions. 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 be formulated as second-order cone programs (SOCPs), including formulations with rotated cones.

Integer Programming

Sometimes, linear relationships aren’t 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’s 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

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

Contact IBM

Considering a purchase?


Optimization Forums

.

Technical discussion around ILOG Optimization products including CPLEX

Go to the forum

Related links

IBM Academic Initiative