I hope I have convinced you for the need for heuristics. Many problems have no solution technique that meets limitations on time, data, and so on. Heuristics are a natural choice in these situations.

Many heuristics are extremely clever, taking great advantage of the
particular structure of the problem to be solved (by the way, I make a
distinction between *problems* and *instances*. A problem is
a set of instances. Generally, we will look at heuristics for
problems, though sometimes a particular instance is important enough
to justify heuristics for itself. Furthermore, heuristics for an
individual instance can often be generalized to a larger problem).
But it is equally important to find general methods of creating
heuristics. These provide quick and dirty solutions to many problems.
Although the solution quality may not be the best, often they work
well enough. In this section, we will examine some general heuristic
techniques. These are random, greedy and exchanging methods. The
first two are *solution generation* methods, while the last is a
*solution improvement* method. Again, I will illustrate these
ideas with the traveling salesman problem, but these are very general
heuristic techniques. I will illustrate the heuristics using the
example in figure 1

- Random solutions.
- Greedy Solutions
- Exchanging Heuristics
- Simplification Heuristics
- Break-Combine Heuristics
- Improving our Solutions

Tue Oct 8 08:16:54 EDT 1996