We move from the world of optimization to the world of ``good enough, fast enough'' solution techniques. No matter how many techniques we teach you, it is inevitable that in the real world you will face many, many problems that cannot be solved by any technique you know. For a great many of these problems, no solution technique is known at all. For these problems, heuristic solution techniques may be the only alternative.
In some sense, it is very difficult to teach heuristic solution techniques. The methods are very problem specific. There are some general rules, however, that make finding good heuristics easier. One might consider these heuristics for finding heuristics. In the next few classes, we will explore these general rules, and examine a few applications were these rules have been successful.
Heuristic problem solving involves finding a set of rules, or a procedure, that finds satisfactory solutions to a specific problem. The first question that must be addressed is ``Why?'' Why adopt a heuristic approach instead of an optimization approach? Certainly, sometimes the problem addressed does not fall into any of the neat classifications and hence is not amenable to known solution techniques. Even when the problem does fall into a known pigeon-hole, there may be resource limitations (computing time, data requirements, etc.) that make using the optimization approach inappropriate. The following list some problem features that may indicate the appropriateness of heuristics (the categories overlap to a large extent, and I am not completely convinced that I am not just repeating myself).
Ill-Structure. Problems for which there are no known algorithmic solutions are called ill-structured. A well-structured problem has the following characteristics:
An ill-structured model is one that fails one or more of the above criteria. Of course, ill-structure is defined only relative to our current state of knowledge. As we develop more algorithms and devise more powerful models, problems become well-structured.
In many cases, an management scientist is tempted to force an ill-structured problem into a well-structured problem. Merely by ignoring a few cases, making a few assumptions, faking a bit of data, most ill-structured problems can look respectable. This is hardly a good method of problem solving. It is far better to recognize the problem as ill-structured and use heuristic techniques.
Too Time Consuming. In many cases, there is
an appropriate, well defined model: integer programming. The current
state of the art in integer programming is not equipped to solve
anything but toy problems (with a few exceptions). In general, there
is a tremendous problem with the combinatorial explosion
inherent in integer programming and similar combinatorial optimization
problems. By this I mean any problem that must examine a large number
of possible solutions. Consider an integer program with 100
variables, each of which must be 0 or 1. Any technique that examines
all possible solutions must examine 
solutions (roughly
). If a computer can examine 100 solutions per second, it
would take roughly 10,000,000,000,000,000,000 years to find the
solution. Branch and bound attempts to cut down this number to a
manageable size, but there are very good reasons to believe that it
does no more that reduce the number by a constant factor. So even if
100 variable problems are solvable in minutes, 200 variable problems
will take millenia. The theory behind this explosion is called
NP-completeness.
In any case, due to this explosion, integer programming problems generally require heuristic solution techniques, as do many related problems due solely to the combinatorial explosion.
Satisficing. In many applications, the goal is not to find the optimal solution. Perhaps the data is uncertain enough that optimality doesn't mean anything. Or perhaps the decision maker has some non-quantifiable goals in mind. By optimizing a model, one solution is presented. Heuristics can often generate many different solutions, each one good in some way, from which the decision maker can choose. The goal in any decision making process is to find a satisfactory solution. Sometimes we can define satisfaction in terms of optimization; often we can't.