Computational Problems

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.

6x² + y + 4z⁴ £ 178
7x + 8y³ + z² ³ 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

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

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:

1. Is x a prime number?


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


3. 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:
w = 3x - y + 4z
subject to the constraints:
x + 5y + z £ 75
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.