next up previous contents
Next: Random solutions. Up: Heuristics for Consultants Previous: A Cautionary Tale

Heuristic Problem Solving

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

Figure 1: Example problem.

Michael A. Trick
Tue Oct 8 08:16:54 EDT 1996