When confronted with the question "What is Tabu Search?" you might be tempted to speculate that it has something to do with a blindfold party game or a quest for forbidden fruit. However, more significantly (or prosaically, depending on your orientation), tabu search constitutes an innovative approach that has been opening the door to solving a wide range of practical business problems.

To give some background for describing this approach, it is useful first to consider two simple but important ways that computers are used to solve quantitative business decision models. The first is to program some detailed formula for handling the information (sometimes called the input data). Then given the data that characterizes a particular instance of the problem, the computer works through the formula and produces an answer. (The formula yields a complete rule for processing the information in a single stage.) In the second method the computer is instructed to carry out a fairly simple operation that changes the information slightly, and then the operation is repeated on the changed information. This happens again and again until a final answer is reached or a stopping criterion is met.

For instance, if the problem were to estimate the compound interest on a sum of money, the first method would use a well-known formula to work out the final amount from the initial sum. The repetitive method would instead calculate the interest for the first year and then use this to calculate the interest for the second year, and so on. In this example the formula method would obviously be better, but in other cases the repetitive method is the only alternative. In fact, repetitive methods have the potential to assemble simple components to achieve remarkable levels of sophistication and complexity. A formula, as in the first example, may alternately become one of the pieces that is incorporated into a repetitive approach. Repetitive methods are commonly applied for the goals of finding:

	the best configuration of machines for production scheduling;
	the best investment portfolio for financial planning;
	the best utilization of employees for workforce planning;
	the best location of facilities for commercial distribution;
	the best operating schedule for electrical power planning;
	the best assignment of medical personnel in hospital administration;
	the best setting of tolerances in manufacturing design;
	the best set of treatment policies in waste management;
	and many other business objectives.

A seductive premise of the Information Age is that, since computers work so fast, the efficiency of a repetitive or iterative method does not matter; the time consumed by applying the method will be negligible in any case. However, consider a simplified investment problem in which the decision is to configure a portfolio that maximizes expected returns. If there are only two investment opportunities, say A and B, then we only need to examine four possible portfolio configurations. The alternatives are to invest in both, to invest only in A, to invest only in B, or not to invest at all. However, if instead of 2 investment opportunities we consider 20, then enumerating all possible portfolios would require more than 1 million evaluations. This number grows very rapidly as the number of investment choices increase. Even for today’s fastest computers, it is easily possible for complete enumeration to take weeks, months, or even years to carry out!

Recent developments focused on iterative computer methods have allowed the creation of intelligent search procedures capable of finding the best or nearly the best solution to complex business problems, by exploring only a small fraction of the possible alternatives. The process of finding the best solution to a decision problem is known as optimization, where the best solution is labeled optimal.

With roots going back to the late 1960’s and early 1970’s, tabu search was proposed in its present form in 1986 by Fred Glover. Tabu search has now become an established optimization approach that is rapidly spreading to many new fields, such as resource management, process design, logistics, and technology planning.

Tabu search is based on the premise that problem solving, in order to qualify as intelligent, must incorporate adaptive memory. The use of memory in tabu search emulates the human memory-surface. Cognitive research has shown that the way information is built up on the memory-surface into established patterns is very much affected by the sequence in which the pieces of information arrive. Yet the best possible arrangement of this information should depend on the information itself, and not on the order in which it arrived (unless of course the arrival time is a relevant component of the information). In other words, the time of arrival of the information adds a factor that characteristically should not be present in the final assembly of the information, if that final assembly is to be the best possible one.

This phenomenon also occurs when iterative methods are used to solve decision problems. At each intermediate stage the arrangement of information may be right, but this does not ensure that the final arrangement is right. Consider the following experiment designed by Dr. Edward de Bono, founder of the Cognitive Research Trust in Cambridge. When the following two pieces of plastic are given to someone with the instructions that they be arranged in a shape that can easily be described,

the pieces always get arranged as shown to give a rectangle.

This can be considered a "local" maximization of the available information. Then the following piece is added.

Since the task is still to arrange the pieces in a shape that is easy to describe, the result is usually another rectangle.

Then two further pieces are added as shown.

Very few people are able to complete the next stage, of incorporating these two final pieces effectively. The difficulty is that local maximization makes the second rectangle constructed almost inevitable once the first one has been made. Yet considering the pieces independently of the sequence in which they appeared, the square pattern is just as good an arrangement for the second step.

From the square pattern, the final arrangement, shown next, is quite obvious, but starting from the rectangle it is nearly impossible to conceive.

This example illustrates how a particular arrangement of information may make the best possible sense at the time and yet provide a block to further development. Humans use insight to overcome the limitation of sequential information processing. Tabu search treats insight as a function of memory together with associated strategies to manipulate information stored during the search for the best solution. In the example above, the procedure would record the outcome of constructing a final solution by using a rectangle configuration in the second step. Then the approach would undertake to generate further constructions, selectively making use of the information stored in memory to forbid a rectangle configuration in the second step. The action of provisionally forbidding the recurrence of certain patterns gives the method its "tabu" label.

Numerous experiments conducted over many different types of procedures have show that (when properly implemented) tabu search obtains results that characteristically rival and often surpass those of the best previously known techniques. In some cases, especially for problems that embody complexities typically encountered in real world applications, the improved quality of solutions afforded by tabu search can be dramatic.

Tabu search is becoming extremely popular among researchers and practitioners, perhaps because it has a rationale that is transparent and natural: its goal is to emulate intelligent uses of memory, particularly for exploiting structure. Since we are creatures of memory ourselves, who use a variety of memory functions to help thread our way through a maze of problem-solving considerations, it would seem reasonable to try to endow our solution methods with similar capabilities.