When asked to characterize computation and to describe all of
the problems that are solved through computation, a computer scientist will usually
begin by describing a programming language in which to do the computation. Most would
present an imperative language such as C++, but some might mention functional languages
or logic programming languages. All however, would probably then discuss computation
in terms of the resources required to perform the required task.

There is another way, namely mathematical programming. This is
where a problem is defined as the solution to a system of simultaneous equations.
In fact, every one of the problems which we compute using programs written in our
favorite languages can also be described in terms of mathematical programming. An
example of such a problem is finding values for the triple of variables: <x, y, z>
which satisfy the constraints specified in following two equations.

^{2 }+ y + 4z

^{4}£ 178

7x + 8y

^{3}+ z

^{2}³ 11

The triples <1, 1, 1> and <2, 2, 1> are among the
many solutions to this particular problem.

Instead of computational resources, the standard method used to
classify mathematical programming problems is by the largest exponent found in any
of the constraint equations. This provides a hierarchy which contains the classes
of linear programming problems, quadratic programming problems, third power problems,
and so forth. Our above example is a fourth power mathematical programming problem.
In graphics and geometric modeling problems with higher powers abound, but in most
areas of computer science and operations research one concentrates primarily upon
linear programming problems.

A practical example is the following truck packing problem. Suppose
we have a truck with a capacity of 2000 pounds and wish to load it with packages. We
are allowed to make up the load from a collection of three kinds of packages which
weigh 540, 1270, and 303 pounds each. To make things a little more difficult, we
find that the packages are worth $770, $1900, and $400 respectively and that our load
must be worth at least $2670. Setting x, y, and z as the numbers of each type of
package that we place on the truck, we now easily describe possible solutions to this
problem with the equations:

540x + 1270y + 303z £ 2000

770x + 1900y + 400z ³ 2670

770x + 1900y + 400z ³ 2670

The

*feasible**solution**space*or collection of correct solutions to a mathematical programming problem can be represented geometrically by a polytope in n-space where n is the number of variables found in the constraint equations. Consider the two linear equations:
3x + 5y £ 15

x - 2y ³ 2

x - 2y ³ 2

Pairs of values <x, y> that satisfy both equations must
lie below the line defined by 3x + 5y = 15 and above that defined by x - 2y = 2.
These two lines are shown in figure 1.

Figure 1 – A Linear Programming Solution Space

A common further constraint is to require the values of
x and y to be no less than zero. This corresponds to practical problems where
we cannot have negative values as solutions. The shaded area in figure 1 is where
all of the feasible solutions to our example can be found.

A particular problem may be termed

*convex*or*nonconvex*depending upon whether the geometric representation of its solution space forms a convex and nonconvex polytope. Examples of both of these for 3-space may be found in figure 2.

Figure 2 - Convex and Nonconvex Solution Spaces

On the left is a convex polytope and on the right is a collection
of polytopes which form a solution space which is nonconvex.

A picture of mathematical programming problems appears as
Figure 3. As mentioned above, of particular interest are the linear programming
problems because these are the problems for which we actually compute optimum
solutions. This is because they are convex and we shall explore this further below.
The other class of problems that interest computer scientists are problems
with integer values as solutions – those for which fractions are not appropriate.
(The truck packing problem mentioned above is one since we were not allowed
to load part of a package.)

Figure 3 - Mathematical Programming Problems

Note that not all of the linear integer programming problems are
convex. The convex integer linear programming problems are of great interest to
computer scientists since they are exactly the set of graph problems solvable in
polynomial time.

We are interested in two styles of computational problems.
The first group we shall examine are

*decision**problems*. These are all of the problems with*true*or*false*as solutions. Several examples are:

- Is x a prime number?

- Are there any solutions to the first mathematical programming problem presented above?

- Can the truck mentioned above be packed with a cargo worth at least $2700?

We are often interested in finding not only finding solutions,
but optimum solutions to problems. To do this, a problem must be stated in such a
way that an optimum solution is requested. This is done by either maximizing or
minimizing a relationship between the variables called an

*objective function*. Below is an example stated in the general format for*optimization problems*.*maximize:*

*subject to the constraints:*

17x - y - 3z £ 45

5x - y + z £ 38

*where x, y, and z*

*³ 0*

In an optimization problem we must find a solution
which provides either a minimum or maximum value for the objective
function. This is depicted geometrically by selecting the point on the
surface of the feasible solution polytope which provides an optimum
value for the objective function. With convex problems this appears
straightforward if we hop on the surface and go uphill until we reach
the top.

With nonconvex problems things are not so simple.
Consider the curve shown in Figure 4. There are two places on the curve
with values larger than the points adjacent to them, one at point a and
one at point b. The greatest of these (that at point b) is called the

*global maximum*while any other point at which there is a maximum relative to immediately adjacent points is called a*local maximum*. The solution space on the right in figure 2 also contains local and global maxima.

Figure 4 - Local and Global Maxima

Note that the polytope on the left in Figure 2 has
only one maximum and thus it is a global maximum, while the solution
space represented by the collection of polytopes on the right in Figure 2
has many maxima. One of the nice things about restricting our attention
to convex problems is that all maxima and minima are guaranteed to be
global.

**Theorem.**

*Any local maximum (or minimum) for a convex programming problem is also a global maximum (or minimum).*

Unfortunately many of the problems of interest to us
as computer scientists are nonconvex and thus usually have several local
maxima (or minima). This makes finding optimum solutions more
difficult and leads to some very interesting methods for finding these
solutions.