Linear Programming

CPLEX revolutionized the world of linear programming when this 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.

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:

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 CPLEX 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. You may want to focus on the following sections:

• IDE and OPL > Optimization Programming Language (OPL) > Language User’s Manual > The application areas > Applications of linear and integer programming > Linear programming
• IDE and OPL > Optimization Programming Language (OPL) > Language User’s Manual > Introduction to OPL > Language overview > Mathematical programming

IBM ILOG CPLEX Optimization Studio can also be a very good entry door 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:

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

The dual simplex algorithm provides the best overall performance and is used by default in CPLEX. Yet, you may be able to improve the speed through further experimentation. Discover how:

• Deciding which CPLEX's numerous linear programming algorithms for fastest performance
• CPLEX has internal logic that enables it to examine and solve linear programs. The application's default settings typically perform very well. However, if you should want to improve CPLEX's performance on a linear program, read CPLEX performance tuning for linear programs
• For version-over-version speed comparisons of CPLEX algorithms see CPLEX Optimizer performance benchmarks

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).

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 programming 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.

• 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