
COP's are interesting because they
include both the easiest and hardest problems to solve. The
difference is described by the partition of all optimization
problems into two sets, P and NPComplete.
The classification of problems into these two sets and by other
distinctions is the subject of complexity theory and
is far beyond this simple introduction. The subject is important
to OR practice, however, because a particular problem will probably
be tractable if it is identified as a member of P,
while the problem will probably be difficult or impossible to
solve if it is identified as a member of NPComplete.
A problem in the set P can be solved by an algorithm whose
solution time grows as a polynomial function of the
size of the problem. For example the shortest path problem for
a network with having n nodes and with nonnegative
arc lengths can be solved with Dijkstra's
algorithm. If implemented correctly, the computation time
is bounded from above by a constant times the number of nodes
squared. We say the solution time is order
or .
Since the function in the parentheses is a polynomial, this
is a polynomial algorithm and the shortest path problem with
positive arc lengths is in the set P. We say that this is an
easy problem because large problems can be solved in
reasonable times with the proper algorithm and on a fast computer.
A variety of special case COP's fall in the set P including
versions of the assignment, minimal spanning tree, shortest
path tree, pure network flow programming and linear programming
problems.
For the problems in the set NPComplete, no polynomial algorithms
have been found. As an example, the time for enumerating all
the solutions of a binary IP with n variables is .
The function in the parentheses is exponential in n.
This is bad news. Although it may be possible to solve problems
by enumeration for some small n, it is clear that for
some larger n the enumeration will be impossible. One
might ask, "why not solve the problem with a more efficient
method such as branch and bound or with cutting planes?"
The answer is that these methods also have exponential bounds.
In fact, no polynomial algorithm has been found for the binary
IP problem. If one could find one, the problem would be in class
P. In fact, most researchers would say that it is unlikely that
such an algorithm will ever be discovered. Again, one might
ask, why not wait for a faster computer to be invented? Surely
there will be one. The answer is that no matter how fast computers
become, exponential growth will eventually make problems of
some size unsolvable. On the following pages we call problems
in the NPComplete class hard problems.
What does this say to someone who must solve a COP? If the
problem can be reduced to a member of the class P, just apply
the associated the algorithm. Even if a problem is in P it may
not be easy to solve because appropriate algorithms are not
always easy to find, easy to program or inexpensive to purchase.
For a given COP it is often not easy to tell if it can or cannot
be reduced to P. Even if the COP is identified as a member of
P, a slight variation of the problem, perhaps a change in form
for the objective function or the addition of a constraint,
may cause the COP to be no longer reducible to P. It is easy
to find the shortest path from node a to node b
in network, but if the path is required to have at least a specified
number of arcs, the problem becomes hard.
If the problem cannot be reduced to a problem in P, does that
mean it is in the class NPComplete? We can prove that a problem
is in NPComplete if we can take some problem that is known
to be NPComplete and reduce it to the problem at hand. Again,
this is not always easy to determine.
If the analyst is not able to classify a problem, if it cannot
be reduced to a member of P or one does not have a convenient
algorithm, is all lost? The answer is that a problem can be
solved to optimality if it is not too big. If it is too big,
then there are heuristic methods that may yield acceptable solutions.
