**Michael L. Overton**

**Draft for Encyclopedia Americana December 20, 1997
**

**LINEAR PROGRAMMING**, a specific class of mathematical problems,
in which a linear function is maximized (or minimized)
subject to given linear constraints.
This problem class is broad enough to encompass many interesting and important
applications, yet specific enough to be tractable even if the number of
variables is large.

**History.** Linear programming was developed as a discipline in the 1940's,
motivated initially by the need to solve complex planning problems in wartime
operations. Its development accelerated rapidly in the postwar period as many
industries found valuable uses for linear programming.
The founders of the subject are generally regarded as George B. Dantzig,
who devised the simplex method in 1947, and
John von Neumann, who established the theory of duality that same year.
The Nobel prize in econonmics was awarded in 1975 to the
mathematician Leonid Kantorovich (USSR) and the economist
Tjalling Koopmans (USA) for their contributions to the theory of optimal
allocation of resources, in which linear programming played a key role.
Many industries use linear programming as a standard tool,
e.g. to allocate a finite set of resources in an optimal way.
Examples of important application areas include
airline crew scheduling, shipping or telecommunication networks,
oil refining and blending, and stock and bond portfolio selection.

**Overview.**
The general form of a linear program is

Here , and
are given numbers, and are variables whose values
are to be determined, maximizing the given objective
subject to the given constraints. There are *n* variables and *m*
constraints, in addition to the nonnegativity restrictions on
the variables. The constraints are called linear because they
involve only linear functions of the variables. Quadratic terms such
as or are not permitted. If minimization is
desired instead of maximization, this can be accomplished by reversing
the signs of .

An example is very helpful. Consider the linear program

where the numbers and , defining the maximization objective
, have not yet been specified.
In this example, *n*, the number of variables, is 2, and *m*, the
number of constraints, is 3
In Figure 1, each constraint is shown by a straight line, with one
side of the line shaded to indicate that the points on that
side of the line *do not satisfy* the corresponding constraint.
The central unshaded region in Figure 1 is the set of points
which satisfy *all* the constraints. This is called
the *feasible region*. The boundary of the feasible region is a polygon.

Now consider the problem of maximizing the linear function
, for given numbers , , over points
lying in the feasible region. The quantity is called
the *objective function*.
If , the goal is to maximize , and
it is clear from Figure 1 that this is achieved by .
This point is called the *optimal solution*. On the other hand,
if , , the goal is to maximize , and the
optimal solution is . If , , the goal
is to maximize , and the optimal solution is any point on the line
segment between (2,1) and (2,2).
It is intuitively clear that regardless of the values of , ,
the optimal solution is on the boundary of the feasible region.
For most choices of , , the optimal solution is *unique*,
specifically at a *vertex* of the feasible region,
i.e. one of the corners of the boundary.

Not every linear program has an optimal solution.
It may happen that no solution exists, either
because the feasible region is infinitely large,
or because it is empty.
For *n*;*SPMgt*;2, the feasible region is a polyhedron in *n* dimensions,
possibly infinitely large or empty. If an optimal solution exists,
there must always be one at a vertex
of the polyhedron, though it is not always unique.

The most remarkable mathematical property of linear programs is the
theory of duality. The *dual* of the linear program given above is

This is a linear program in the variables . It is not hard to
show that if is in the feasible region for the first
linear program and
is in the feasible region for the dual linear program, than
the first objective function is less than
or equal to the dual objective function .
The remarkable fact is that these two objectives are always
*equal* for any and
which are, respectively, optimal solutions for the two linear programs.
This is of great practical importance for both the interpretation
of the solutions of linear programs and the methods for calculating their
solutions.

**The simplex method.**
The simplex method has been the standard technique for solving a linear
program since the 1940's. In brief,
the simplex method passes from vertex to
vertex on the boundary of the feasible polyhedron,
repeatedly increasing the objective function
until either an optimal solution is found, or it is established that
no solution exists. In principle, the time required
might be an exponential function of the number of variables, and this
can happen in some contrived cases. In practice, however, the method
is highly efficient, typically requiring a number of steps which is just
a small multiple of the number of variables.
Linear programs in thousands or even millions of variables are routinely
solved using the simplex method on modern computers.
Efficient, highly sophisticated implementations are available in
the form of computer software packages.

**Interior-point methods.**
In 1979, Leonid Khaciyan presented the ellipsoid method, guaranteed
to solve any linear program in a number of steps which is a polynomial
function of the amount of data defining the linear program.
Consequently, the ellipsoid method is faster than the simplex method in
contrived cases where the simplex method performs poorly. In practice,
however, the simplex method is far superior to the ellipsoid method.
In 1984, Narendra Karmarkar introduced an interior-point method for
linear programming,
combining the desirable theoretical properties of the ellipsoid method and
practical advantages of the simplex method.
Its success initiated an explosion in the development of interior-point
methods. These do not pass from vertex to vertex, but pass only through
the interior of the feasible region. Though this property is easy to state,
the analysis of interior-point methods is a subtle subject which is
much less easily understood than the behavior of the simplex method.
Interior-point methods are now generally considered competitive with
the simplex method in most, though not all, applications, and
sophisticated software packages implementing them are now available.
Whether they will ultimately replace the simplex method in industrial
applications is not clear.

An essential component of both the simplex and interior-point methods is the solution of systems of linear equations, which use techniques developed by C.F. Gauss and A. Cholesky in the 18th and 19th centuries. (see LINEAR EQUATIONS and MATRIX). Important generalizations of linear programming include integer programming, quadratic programming, nonlinear programming and stochastic programming (See OPERATIONS RESEARCH).

REFERENCES

- G.B. Dantzig,
*Linear Programming and Extensions*, Princeton University Press, Princeton, NJ, 1963. - R.J. Vanderbei,
*Linear Programming: Foundations and Extensions*, Kluwer Academic Publishers, Boston, 1996. - S.J. Wright,
*Primal-Dual Interior-Point Methods*, Society for Industrial and Applied Mathematics, Philadelphia, 1997. - J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver (eds.),
*History of Mathematical Programming: a collection of personal reminiscences*, North-Holland, Amsterdam, 1991.

Sat Dec 20 18:31:43 EST 1997