Mathematical Programming

The term "programming" in mathematical programming should not be confused with computer programming. It was coined in the 1940's by a mathematician named George Bernard Dantzig to describe problems being studied for the post-World War II Defense Department. The problems were supporting research to devise programs of activities for future conflicts and were therefore called "programming problems".

Mathematical programming (commonly referred to as optimization in the realm of mathematics) breaks down into numerous subfields but only Linear Programming (LP) and Integer programming (IP) are included in the OPL language.

LP problems are based on linear polynomial functions and have limited applicability. A linear polynomial is an equation like 3x + 4y + 5z = 6. No variables can be raised to a power, used in a square root, etc. Another limitation is that the constraint functions must be of the form: <polynomial> [<=, =, =>] <some constant value>.

LP uses a set of linear polynomial functions as constraints and attempts to minimize or maximize an objective equation (which must also be linear). The variables used in the equations represent unknown values that must be determined by a solving algorithm. The most famous algorithm for solving LP problems is called the Simplex algorithm and was invented by Dantzig. The simplex algorithm will be used within the jOpt implementation of OPL.

IP problems, also known as mixed integer programming problems (MIP), are a special instance of LP problems where some or all of the unknown values cannot have fractional values. The solution to these problems can be found using different techniques including Branch-and-Bound and Cutting Plane. Both techniques involve a type of recursion where a simplex algorithm is performed at each step.

An example IP problem might look like:

Objective
       Maximize N
Subject to
       N = X^2
       N+100000000 = Y^2

The problem with LP and IP techniques is that, in the real world, not all constraints can be modeled using linear polynomials.

Development Status

A large amount of research has been put into this component of the OPL project since it is a major component. However, only a small portion of the development is complete.