Tabu Search 

FRED GLOVER and BELEN MELIAN 

1. Introduction 

Tabu search (TS) has its antecedents in methods designed to cross boundaries of feasibility or local optimality treated as barriers in classical procedures, and to systematically impose and release constraints to permit exploration of otherwise forbidden regions (Glover, 1977). The tabu search name and terminology comes from Glover (1986). A distinguishing feature of the approach is its use of adaptive memory and special associated problem-solving strategies.(TS provides the origin of the memory-based and strategy-intensive focus in the metaheuristic literature, as opposed to methods that are memory-less or use only a weak inheritance-based memory. It is also responsible for emphasizing the use of structured designs to exploit historical patterns of search, as opposed to processes that rely almost exclusively on randomization.)
The fundamental principles of tabu search were elaborated in a series of papers in the late 1980s and early 1990s, and have been assembled and in the book Tabu Search (Glover and Laguna, 1997). The remarkable successes of tabu search for solving hard optimization problems (especially those arising in real world applications) has caused an explosion of new TS applications in the last several years. The web site www.tabusearch.net , for example, includes more than a thousand presentations and papers on the method, and is far from exhaustive.
The tabu search philosophy is to derive and exploit a collection of intelligent problem solving strategies, based on implicit and explicit learning procedures. The adaptive memory framework of TS not only involves the exploitation of the history of the problem-solving process, but also entails the creation of structures to make such exploitation possible. Problem-solving history extends to experience gained from solving multiple instances of a problem class by joining TS with an associated learning approach called Target Analysis (see, e.g., chapter 9 of Glover and Laguna, 1997). 
The memory structures of tabu search operate by reference to four principal dimensions, consisting of recency, frequency, quality, and influence. These dimensions in turn are set against a background of logical structure and connectivity. The role of these elements in creating effective problem solving processes are discussed in our following development 

2.	The Tabu Search Framework 

To provide a background for understanding some of the fundamental elements of tabu search, we illustrate its basic operation with an example from Glover and Laguna (1993).

2.1 An Illustrative Example 

Permutation problems are an important class of problems in optimization, and offer a useful vehicle to demonstrate some of the considerations that must be faced in the combinatorial domain. Classical instances of permutation problems include traveling salesman problems, quadratic assignment problems, production sequencing problems, and a variety of design problems. As a basis for illustration, consider the problem of designing a material consisting of a number of insulating modules. The order in which these modules are arranged determine the overall insulating property of the resulting material, as shown in Figure 1. 

Fig. 1 Modules in an insulating material. 

~ Modules 

The problem is to find the ordering of modules that maximizes the overall insulating property of the composite material. Suppose that 7 modules are considered for a particular material, and that evaluating the overall insulating property of a particular ordering is a computationally expensive procedure. We desire a search method that is able to fmd an optimal or near-optimal solution by examining only a small subset of the total possible permutations (in this case, numbering 5040, though for many applications the number can be astronomical). 

Closely related problems that can be represented in essentially the same way include serial fIltering and job sequencing problems. Serial fIltering problems arise in pattern recognition and signal processing applications, where a given input is to be subjected to a succession of fIlters (or screening tests) to obtain the "best" output. Filters are sequentially applied to the input signal, and the quality of the output is determined by the order in which they are placed (see Figure 2). In this case, the search method must be designed to find the best filtering sequence. Such filtering processes are also relevant to applications in chemical engineering, astronomy, and biochemistry. 

Fig. 2 Filtering sequence. 

Job sequencing problems consist of determining best sequences for processing a set of jobs on designated machines. Each machine thus is assigned some permutation of available jobs. A single machine problem is illustrated in Figure 3. (In some settings, multiple machine problems may be treated by extensions of processes for single machine problems.) 
There are many variants of the single machine problem depending on the definition of "best" sequence. For example, the best sequence may be the one that minimizes the makespan (i.e., the completion time of the last job in the sequence). Other possibilities are to minimize a weighted sum of tardiness penalties or a sum of setup costs. 

Fig. 3 Word processing jobs on a single machine. 

For well structured objective functions, evaluations of ways to move from one solution to another are generally fast. However, problems with even modest numbers of jobs overwhelm the capabilities of algorithms that "guarantee" optimality, rendering them unable to obtain solutions in reasonable amounts of time. That is one of the reasons why effective heuristic approaches have proved important in the area of production scheduling. 

Some useful variants of the foregoing problems can be represented “as if” they were permutation problems. These include, for example, problems where it is simultaneously desired to select a best subset of items (modules, filters, jobs) from an available pool, and to identify a best sequence for this chosen set. In this case, the problem can be represented by creating a dummy position to hold a residual pool, where all items that do not currently occupy one of the sequence positions are placed. (The path assignment problem discussed in Section 4 is a good example of this kind of representation.) 

We focus on the module insulation problem to introduce and illustrate the basic components of tabu search. First we assume that an initial solution for this problem can be constructed in some intelligent fashion, ie., by taking advantage of some problem-specific structure. Suppose the initial solution to our problem is the one shown in Figure 4. 

Fig. 4 Initial permutation. 

The ordering in Figure 4 specifies that module 2 is placed in the fIrst position, followed by module 5, etc. The resulting material has an insulating property of 10 units (which we assume was found by an accompanying evaluation routine, e.g., a simulator package for estimating the properties of a material without actually building a prototype). TS methods operate under the assumption that a neighborhood can be constructed to identify "adjacent solutions" that can be reached from any current solution. (Neighborhood search is described in Section 2.3.) Pairwise exchanges (or swaps) are frequently used to define neighborhoods in permutation problems, identifying moves that lead from one solution to the next. In our problem, a swap exchanges the position of two modules as illustrated in Figure 5. Therefore, the complete neighborhood of a given current solution consists of the 21 adjacent solutions that can be obtained by such swaps. 

Fig. 5 Swap of modules 5 and 6. 

Associated with each swap is a move value, which represents the change on the objective function value as a result of the proposed exchange. Move values generally provide a fundamental basis for evaluating the quality of a move, although other criteria can also be important, as indicated later. A chief mechanism for exploiting memory in tabu search is to classify a subset of the moves in a neighborhood as forbidden (or tabu). The classification depends on the history of the search, particularly as manifested in the recency or frequency that certain move or solution components, called attributes, have participated in generating past solutions. For example, one attribute of a swap is the identity of the pair of elements that change positions (in this case, the two modules exchanged). As a basis for preventing the search from repeating swap combinations tried in the recent past, potentially reversing the effects of previous moves by interchanges that might return to previous positions, we will classify as tabu all swaps composed of any of the most recent pairs of such modules; in this case, for illustrative purposes, the three most recent pairs. This means that a module pair will be kept tabu for a duration (tenure) of 3 iterations. Since exchanging modules 2 and 5 is the same as exchanging modules 5 and 2, both may be represented by the pair (2, 5). Thus, a data structure such as the one shown in Figure 6 may be used. 

Fig. 6 Tabu data structure for attributes consisting of module pairs exchanged. 

Each cell of the structure in Figure 6 contains the number of iterations remaining until the corresponding modules are allowed to exchange positions again. Therefore, if the cell (3, 5) has a value of zero, then modules 3 and 5 are free to exchange positions. On the other hand, if cell (2, 4) has a value of 2, then modules 2 and 4 may not exchange positions for the next two iterations (i.e., a swap that exchanges these modules is classified tabu). 

The type of move attributes illustrated here for defining tabu restrictions are not the only ones possible. For example, reference may be made to separate modules rather than module pairs, or to positions of modules, or to links between their immediate predecessors (or successors), and so forth. Some choices of attributes are better than others, and relevant considerations are discussed in Sections 2.5.1 and 2.5.2. (Attributes involving created and broken links between immediate predecessors and successors are often among the more effective for many permutation problems.) 

To implement tabu restrictions such as those based on module pairs, an important exception must be taken into account. Tabu restrictions are not inviolable under all circumstances. When a tabu move would result in a solution better than any visited so far, its tabu classification may be overridden. A condition that allows such an override to occur is called an aspiration criterion. (Several useful forms of such criteria are presented in Section 2.7.) The following shows 4 iterations of the basic tabu procedure that employs the paired module tabu restriction and the best solution aspiration criterion. 

Iteration 0 (Starting Point) 
Current solution 

Tabu structure 234567 
* 

The starting solution has an insulation value of 10, and the tabu data structure is initially empty (i.e., it is filled with zeros, indicating no moves are classified tabu at the beginning of the search). After evaluating the candidate swap moves, the top five moves (in terms of move values) are shown in the table for iteration 0 above. 

This information is provided by an independent evaluation subroutine designed to identify move values for this particular problem. (Of course, it is not necessary for the subroutine to sort and identify each of the 5 best moves, since we are interested only in the best. Additional options are included to clarify certain ideas subsequently presented.) To locally maximize the insulating property of the material, we swap the positions of modules 5 and 4, as indicated by the asterisk. The total gain of such a move equals 6 units. 

Iteration I Current solution 

Top 5 candidates 

The new current solution has an insulating value of 16 (i.e., the previous insulation value plus the value of the selected move). The tabu structure now shows that swapping the positions of modules 4 and 5 is forbidden for 3 iterations. The most improving move at this step is to swap 3 and 1 for a gain of 2. 

Iteration 2 Current solution 

The new current solution becomes the best solution found so far with an insulating value of 18. At this iteration two exchanges are classified tabu as indicated by the nonzero entries in the tabu structure. 

Note that entry (4,5) has been decreased from 3 to 2, indicating that its original tabu tenure of 3 now has 2 remaining iterations to go. This time none of the candidates (including the top 5 shown) has a positive move value. Therefore, a non-improving move has to be made. The most attractive non-improving move is the reversal of the move performed in the previous iteration, but since it is classified tabu, this move is not selected. Instead, the swap of modules 2 and 4 is chosen, as indicated by the asterisk. 

Iteration 3 
Current solution 

The new current solution has an insulation value inferior to the two values previously obtained, as a result of executing a move with a negative move value. The tabu data structure now indicates that 3 moves are classified tabu, with different remaining tabu tenures. At the top of the candidate list, we fmd the swap of modules 4 and 5, which in effect represents the reversal of the fIrst move perfonI1ed, and is classified tabu. However, perfonI1ing this move produces a solution with an objective function value that is superior to any previous insulation value. Therefore, we make use of the aspiration criterion to override the tabu classification of this move and select it as the best on this iteration. 

Iteration 4 
Current solution 

The current solution becomes the incumbent new best solution and the process continues. Note that the chosen tabu restriction and tabu tenure of 3 results in forbidding only 3 out of 21 possible swaps, since the module pair with a residual tenure of 1 always drops to a residual tenure of 0 each time a new pair with tenure 3 is introduced. (By recording the iteration when a module pair becomes tabu, and comparing this against the current iteration to determine the remaining tabu tenure, it is unnecessary to change these entries at each step as we do here.) 

In some situations, it may be desirable to increase the percentage of available moves that receive a tabu classification. This may be achieved either by increasing the tabu tenure or by changing the tabu restriction. For example, a tabu restriction that forbids swaps containing at least one member of a module pair will prevent a larger number of moves from being executed, even if the tenure remains the same. (In our case, this restriction would forbid 15 out of 21 swaps if the tabu tenure remains at 3!) Such a restriction is based on single module attributes instead of paired module attributes, and can be implemented with much less memory, i.e., by an array that records a tabu tenure for each module separately. Generally speaking, regardless of the type of restriction selected, improved outcomes are often obtained by tabu tenures that vary dynamically, as described in Section 2.6. 

Move Values and Candidate List Strategies. Because tabu search aggressively selects best admissible moves (where the meaning of best is affected by tabu classification and other elements to be indicated), it must examine and compare a number of move options. For many problems, only a portion of the move values will change from one iteration to the next, and often these changed values can be isolated and updated very quickly. This element of maintaining efficient updates is very important and often overlooked. For example, in the present illustration it may be useful to store a table move_value(j, k), which records the current move value for exchanging modules j and k. Then when a move is executed, a relatively small part of this table (consisting of values that change) can be quickly modified, and the updated table can then be consulted to identify moves that become the new top candidates. 

Such partial updating often can be further enhanced by a list MoveName(MoveValue) which, for each MoveValue in a relevant range, identifies MoveName to be a specific move that yields this value. A linked list then can connect this MoveName to the names of all other moves that yield the same MoveValue. The combination of the MoveName(MoveValue) array and the linked list can be updated very quickly to make it easy to locate moves with best move values in cases where only a relatively small number of elements change. A given MoveValue entry also can refer to a range of move values, with an option to regard all values within a specified range as "essentially equivalent." (However, we suggest the merit of differentiating members of a given range more carefully upon approaching local optimality.) 

On a broader scale, lists to facilitate access to best moves invite differentiation to include considerations introduced by move influence (Section 2.'7) and by candidate list strategies (Section 3). They are also subject to periodic scanning with reference to concerns that extend beyond the short term horizon, as we illustrate next 

Complementary Tabu Memory Structures. The accompaniment of recency based memory with frequency based memory adds a component that typically operates over a longer horizon. To illustrate one of the useful longer term applications of frequency based memory, suppose that 25 TS iterations have been performed, and that the number of times each module pair has been exchanged is saved in an expanded tabu data structure. The lower diagonal of this structure now contains the frequency counts. 

Iteration 26 Current solution 

At the current iteration (iteration 26), the recency memory indicates that the last three module pairs exchanged were (4, 1), (6,3), and (4, 7). The frequency counts show the distribution of moves throughout the first 25 iterations. We use these counts to diversify the search, driving it into new regions. This diversifying influence is restricted to operate only on particular occasions. In this case, we select those occasions where no admissible improving moves exist. Our use of the frequency information will penalize nonimproving moves by assigning a larger penalty to swaps of module pairs with greater frequency counts. (Typically these counts would be normalized, as by dividing by the total number of iterations or their maximum value.) We illustrate this in the present example by simply subtracting a frequency count from the associated move value. 

The list of top candidates for iteration 26 shows that the most improving move is the swap (1,4), but since this module pair has a residual tabu tenure of 3, it is classified tabu. The move (2, 4) has a value of -1, and it might otherwise be the one next preferred, except that its associated modules have been exchanged frequently during the history of the search (in fact, more frequently than any other module pair). Therefore, the move is heavily penalized and it looses its attractiveness. The swap of modules 3 and 7 thus is selected as the best move on the current iteration. 

The strategy of instituting penalties only under particular conditions is used to preserve the aggressiveness of the search. Penalty functions in general are designed to account not only for frequencies but also for move values and certain influence measures, as discussed in Section 2.8. 

In addition, frequencies defined over different subsets of past solutions, particularly subsets of elite solutions consisting of high quality local optima, give rise to complementary strategies called intensification strategies. Intensification and diversification strategies interact to provide fundamental cornerstones of longer term memory in tabu search. The ways in which such elements are capable of creating enhanced search methods, extending the simplified approach of the preceding example, are elaborated in following sections. 

2.2 Notation and Problem Description 

A few basic definitions and conventions are useful. We express the mathematical optimization problem as follows. 
    
  Minimize c(x)
 
subject to 

x ε X

The objective function c(x) may be linear or nonlinear, and the condition x ε X, summarizes constraints on the vector x. These constraints may include linear or nonlinear inequalities, and may compel some or all components of x to receive discrete values. 

In many applications of combinatorial optimization, the problem of interest is not explicitly formulated as we have shown it. In such cases the present formulation may be conceived as a code for another formulation. The requirement x ε X, for example, may specify logical conditions or interconnections that would be cumbersome to formulate mathematically, but may better be left as verbal stipulations (for example, in the form of rules). Often in these instances the variables are simply codes for conditions or assignments that are parts of the more complex structure. For example, an element of x may be a binary variable that receives a value of 1 to code for assigning an element u to a set or position v, and that receives a value 0 to indicate the assignment does not occur. 

2.3 Neighborhood Search 

TS may be conveniently characterized by reference to neighborhood search, though we warn that neighborhood search has a broader meaning in TS than in some other parts of the metaheuristic literature. For example, TS includes constructive and destructive procedures among the processes that it guides by adaptive memory, whereas such procedures and their combinations are often excluded from the definition of neighborhood search in other approaches.

A convenient representation of neighborhood search identifies, for each solution x ε X, an associated set of neighbors, N (x)  X, called the neighborhood of x. Each solution x’ ε N(x) can be reached directly from x by an operation called a move, and x is said to move (or transition) to x' when such an operation is performed. Normally in tabu search neighborhoods are assumed symmetric, i.e., x’ is a neighbor of x if and only if x is a neighbor of x'.

The steps of neighborhood search may be described as follows. We assume choice criteria for selecting moves, and termination criteria for ending the search, are given by some external set of prescriptions. 

Neighborhood Search Method 

Step 1 (Initialization). 
(A) Select a starting solution xNow ε X. 
(B) Record the current best known solution by setting xBest = xNow and defme BestCost = c(xBest). 
Step 2 (Choice and termination). 
Choose a solution xNext ε N(xNow). If the choice criteria employed cannot be satisfied by any member of N(xNow) (hence no solution qualifies to be xNext), or if other termination criteria apply (such as a limit on the total number of iterations), then the: method stops. 
Step 3 (Update). 
Re.set xNow = xNext, and if c(xNow) < BestCost, perform Step 1(B). Then return to Step 2. 

The foregoing method can represent a constructive method by stipulating that X is expanded to include x vectors whose components take null (unassigned) values, and by stipulating that a neighbor x’ of x can result by replacing a null component of x with a non-null component. (A change of representation sometimes conveniently allows null components to be represented by values of 0 and non-null components by values of 1.) A typical constructive method does not yield symmetric neighborhoods, since non-null components are not permitted to become null again (hence the method ends when no more components are null). However, tabu search reinstates the symmetric relation by allowing constructive and destructive moves to co-exist, as a special instance of an approach called strategic oscillation (see Section 3). 

The Neighborhood Search Method can easily be altered by adding special provisions to yield a variety of classical procedures. Descent Methods, which only permit moves to neighbor solutions that improve the current c(xNow) value, and which end when no improving solutions can be found, can be expressed by the following provision in Step 2. 

Descent Method 

Step 2 (Choice and termination). 
Choose xNext ε N(xNow) to satisfy c(xNext) < c(xNow) and terminate if no such xNext can be found. 

The final xNow obtained by a Descent Method is called a local optimum, since it is at least 
as good or better than all solutions in its neighborhood. The evident shortcoming of a Descent Method is that such a local optimum in most cases will not be a global optimum, ie., it usually will not minimize c(x) over all x ε X. 

Randomized procedures such as Monte Carlo methods, which include simulated annealing, similarly can be represented by adding a simple provision to Step 2. 

Monte Carlo Method 

Step 2 (Choice and tennination). 
(A) Randomly select xNext from N(xNow). 
(B) If c(xNext) ≤ c(xNow) accept xNext (and proceed to the Update Step) . 
(C) If c(xNext) > c(xNow) accept xNext with a probability that decreases with increases in the difference c(xNext) -c(xNow). If xNext is not accepted on the current trial by this criterion, return to Step 2(A). 
(D) Terminate by a chosen cutoff rule. 

Monte Carlo methods continue to sample the search space until finally terminating by some form of iteration limit. Normally they use an exponential function to define probabilities, drawing from practice established in engineering and physical science. The Monte Carlo version represented by simulated annealing starts with a high probability for accepting non-improving moves in Step 2(C) and decreases this probability over time as a function of a parameter called the "temperature," which monotonically diminishes toward 0 as the number of iterations grows. Such approaches offer a chance to do better than finding a single local optimum since they effectively terminate only when the probability of accepting a non-improving move in Step 2(C) becomes so small that no such move is ever accepted (in the finite time allowed). Hence, they may wander in and out of various intermediate local optima prior to becoming lodged in a final local optimum, when the temperature becomes small. 

Another randomizing approach to overcome the limitation of the Descent Method is simply to re-start the method with different randomly selected initial solutions, and run the method multiple times. Such a random restart approach (sometimes called Iterated Descent), may be contrasted with a random perturbation approach, which simply chooses moves randomly for a period after reaching each local optimum, and then resumes a trajectory of descent. Alternating threshold methods indicated in Section 2.7.1 provide a refinement of this idea. 

2.4 Tabu Search Characteristics 

Tabu search, in contrast to the preceding methods, employs a somewhat different philosophy for going beyond the criterion of terminating at a local optimum. Randomization is de-emphasized, and generally is employed only in a highly constrained way, on the assumption that intelligent search should be based on more systematic forms of guidance. Randomization (pseudo- randomization) thus chiefly is assigned the role of facilitating operations that are otherwise cumbersome to implement or whose strategic implications are unclear. (In the latter case, a supplementary learning approach of target analysis (Glover and Laguna, 1997) customarily is employed to determine if such implications can be sharpened.) Accordingly, many tabu search implementations are largely deterministic. An exception occurs for the variant called probabilistic tabu search, which selects moves according to probabilities based on the status and evaluations assigned to these moves by the basic tabu search principles. 

2.4.1 Special TS Uses of Memory: Modifying Neighborhood Structures 

The notion of exploiting certain forms of adaptive memory to control the search process is the central theme underlying tabu search. The effect of such memory may be envisioned by stipulating that TS maintains a selective history H of the states encountered during the search, and replaces N(xNow) by a modified neighborhood which may be denoted N(H, xNow). History therefore determines which solutions may be reached by a move from the current solution, selecting xNext from N(H, xNow). 

In the TS strategies based on short term considerations, N(H, xNow) characteristically is a subset of N(xNow), and the tabu classification serves to identify elements of N(xNow) excluded from N(H, xNow). In the intermediate and longer term strategies, N(H, xNow) may contain solutions not in N(xNow), generally consisting of selected elite solutions (high quality local optima) encountered at various points in the solution process. Such elite solutions typically are identified as elements of a regional cluster in intermediate term intensification strategies, and as elements of different clusters in longer term diversification strategies. In addition, elite solution components, in contrast to the solutions themselves, are included among the elements that can be retained and integrated to provide inputs to the search process. 

TS also uses history to create a modified evaluation of currently accessible solutions. This may be expressed formally by saying that TS replaces the objective function c(x) by a function c(H, x), which has the purpose of evaluating the relative quality of currently accessible solutions. (An illustration is provided by the use of frequency based memory in the example of Section 2.1.) The relevance of this modified function occurs because TS uses aggressive choice criteria that seek a best xNext, ie., one that yields a best value of c(H, xNext), over a candidate set drawn from N(H, xNow). Moreover, modified evaluations often are accompanied by systematic alteration of  N(H,xNow), to include neighboring solutions that do not satisfy customary feasibility conditions (i.e., that strictly speaking do not yield x ε X). Reference to c(x) and feasibility is retained for determining whether a move is improving or leads to a new best solution. 

For large problems, where N(H, xNow) may have many elements, or for problems where these elements may be costly to examine, the aggressive choice orientation of TS makes it highly important to isolate a candidate subset of the neighborhood, and to examine this subset instead of the entire neighborhood. This can be done in stages, allowing the candidate subset to be expanded if alternatives satisfying aspiration levels are not found. Because of the significance of the candidate subset's role, we refer to this subset explicitly by the notation Candidate_N (xNow). Then the tabu search procedure may be expressed in the following manner. 

Tabu Search Method 

Step 1 (Initialization). 
Begin with the same initialization used by Neighborhood Search, and start with the history record H empty. 
Step 2 (Choice and termination). 
Determine Candidate_N(xNow) as a subset of N(H, X~Ow). Select xNext from Candidate_N(xNow) to minimize c(H, x) over this set (xNext is called a highest evaluation element of Candidate_N(xNow).) Terminate by a chosen iteration cutoff  rule. 
Step 3 (Update). 
Perform the update for the Neighborhood Search Method, and additionally update the history record H. 

Formally the tabu search method is quite straightforward to state. The essence of the method depends on how the history record H is defined and utilized, and on how the candidate neighborhood Candidate_N(xNow) and the evaluation function c(H, x) are determined. 
In the simplest cases we may imagine Candidate_N (xNow) to constitute all of N(H, xNow), and take c(H, x) = c(x), disregarding neighborhood screening approaches and the longer term considerations that introduce elite solutions into the determination of moves. However, candidate list strategies that reduce the space of moves considered are enormously important for effective implementation (Glover and Laguna, 1997). 

2.5 Tabu Search Memory 

2.5.1 Attribute Based Memory 

An attribute of a move from xNow to xNext, or more generally of a trial move from xNow to a tentative solution xTrial, can encompass any aspect that changes as a result of the move. Natural types of attributes are as follows. 

Illustrative Move Attributes for a Move xNow to xTrial 

 (AI) Change of a selected variable xj from 0 to 1. 
(A2) Change of a selected variable xk from 1 to O. 
(A3) The combined change of (AI) and (A2) taken together.  
(A4) Change of a function g(xNow) to g(xTrial) (where g may represent a function that occurs naturally in the problem formulation or a function that is created strategically). 

A single move evidently can give rise to multiple attributes. For example, a move that changes the values of two variables simultaneously may give rise to each of the three attributes (AI), (A2), and (A3), as well as to other attributes of the form indicated. 

When we refer to assigning alternative values to a selected variable x. of x, and particularly to assigning values 0 and 1 to a binary variable, we will understand by our previous conventions that this can refer to a variety of operations such as adding or deleting edges from a graph, assigning or removing a facility from a particular location, changing the processing position of a job on a machine, and so forth. Such coding conventions can be extended to include the creation of supplementary variables that represent states of subservient processes. For example, x. = 0 or 1 may indicate that an associated variable is nonbasic or basic in an extreme point 
J 
solution procedure, as in the simplex method and its variants for linear and nonlinear programming. 

2.5.2 Uses of Move Attributes 

Recorded move attributes are often used in tabu search to impose constraints, called tabu restrictions, that prevent moves from being chosen that would reverse the changes represented by these attributes. More precisely, when a move from xNow to xNext is performed that contains an attribute e, a record is maintained for the reverse attribute which we denote bye, in order to prevent a move from occuning that contains some subset of such reverse attributes. Examples of kinds of tabu restrictions frequently employed are as follows. 

Illustrative Tabu Restrictions 

A move is tabu if: 
(RI) xj  changes from 1 to 0 (where xj previously changed from 0 to I). 
(R2) xk changes from 0 to 1 (where xk previously changed from 1 to 0). 
(R3) At least one of (RI) and (R2) occur. (This condition is more restrictive than either (RI) or (R2) separately -i.e., it makes more moves tabu.) 
(R4) Both (RI) and (R2) occur. (This condition is less restrictive than either (RI) or (R2) separately -i.e., it makes fewer moves tabu.) 

2.5.3 The Role of Tabu Status 
A tabu restriction typically is activated only in the case where its attributes occurred within a limited number of iterations prior to the present iteration (creating a recency based restriction) or occurred with a certain frequency over a longer span of iterations (creating a frequency based restriction). More precisely, a tabu restriction is enforced only when the attributes underlying its definition satisfy certain thresholds of recency or frequency. To exploit this notion, we define an attribute to be tabu-active when its associated reverse (or duplicate) attribute has occurred within a stipulated interval of recency or frequency in past moves. An attribute that is not tabu-active is called tabu-inactive.
 
The condition of being tabu-active or tabu-inactive is called the tabu status of an attribute. Sometimes an attribute is called tabu or not tabu to indicate that it is tabu-active or tabu-inactive. It is important to keep in mind in such cases that a "tabu attribute" does not correspond to a tabu move. As the preceding examples show, a move may contain tabu-active attributes, but still may not be tabu if these attributes are not of the right number or kind to activate a tabu restriction. 

The most common tabu restrictions, whose attributes are the reverse of those defining these restrictions, characteristically have a goal of preventing cycling and of inducing vigor into the search. It should be pointed out that cycle avoidance is not an ultimate goal of the search process. In some instances, a good search path will result in revisiting a solution encountered before. The broader objective is to continue to stimulate the discovery of new high quality solutions. In general, a common type of restriction operates by selecting some subset of attributes and declaring the move to be tabu if a certain minimum number (e.g., one or all) are tabu-active. 

2.6 Recency Based Tabu Memory Functions 

To keep track of the status of move attributes that compose tabu restrictions, and to determine when these restrictions are applicable, several basic kinds of memory functions have been found useful. Two common examples of recency based memory functions are specified by the arrays TabuStart(e) and TabuEnd(e), where ε ranges over attributes relevant to a particular application. These arrays respectively identify the starting and ending iterations of the tabu tenure for attribute e, thus bracketing the period during which ε is tabu-active. 

The rule to identify appropriate values for TabuStart(e) and TabuEnd(e) results by keeping track of the attributes at each iteration that are components of the current move. In particular, on iteration i, if ε is an attribute of the current move, and tabu status is defined to avoid reversals, then we set TabuStart(e) = i + 1, indicating that the reverse attribute e’ begins its tabu- active status at the start of the next iteration. (For example, if e represents "from xj = p" then e’ can represent "to xj = p.") Attribute e’ will retain this status throughout its tabu tenure, which we denote by t. Then this yields TabuEnd(e) = i + t, so that the tenure for e’ ranges over the t iterations from i + 1 to i + t. 

As a result, it is easy to test whether an arbitrary attribute e’ is tabu-active, simply by checking to see if TabuEnd(e) ~ CurrentIteration. Initializing TabuEnd(e) = 0 for all attributes assures that TabuEnd(e) < CurrentIteration, and hence that attribute ε is tabu-inactive, until the update previously specified is performed. This suggests we need to keep only the single array TabuEnd(e) to provide information about tabu status. However, we will see that situations arise where it is valuable to keep TabuStart(e), and either to infer TabuEnd(e) by adding an appropriate value of t (currently computed, or preferably extracted from a pre-stored sequence), or to maintain TabuEnd(e) as a separate array.
 
Memory often can be further simplified when attributes represent binary alternatives, such as changing from xj = 0 to xj = 1. Then, instead of recording a separate value TabuStart(e) for each of these attributes, it suffices simply to record a single value TabuStart(j). We automatically know whether TabuStart(j) refers to changing from xj = 0 to xj = 1 or the reverse, by taking account of the value of xj in the current solution. If cwrently xj  = 1, for example, the most recent change was from xj = 0 to xjj = 1. Then the reverse attribute, derived from changing xj from 1 to 0, is the one whose tenure is represented by the value of TabuStart(j). (We assume that the latest tabu tenure assigned to an attribute takes precedence over all others.) 
Regardless of the data structure employed, the key issue for creating tabu status using recency based memory is to determine a "good value" of t. Rules for determining t are classified as static or dynamic. Static rules choose a value for t that remains fixed throughout the search. Dynamic rules allow the value of t to vary. Examples of these two kinds of rules are as follows. 

Illustrative Rules to Create Tabu Tenure 
(Recerx:y Based) 

Static rules: 

Choose t to be a constant such as t = 7 or t = SquareRoot(n). where n is a measure of problem dimension. 

Dynamic rules: 

Simple dynamic: Choose t to vary (randomly or by systematic pattern) between bounds tMin and tMax. such as tMin = 5 and tMax = 11 or tMin = .9SquareRoot(n) and tMax = 1.1SquareRoot(n)

Attribute-dependent dynamic: Choose t as in the Simple Dynamic rule, but determine tMin and tMax to be larger for attributes that are more attractive, e.g., based on quality or influence considerations. 

The indicated values such as 7 and SquareRoot(n) are only for purposes of illustration, and represent parameters whose preferred values should be set by experimentation for a particular class of problems. It often is appropriate to allow different types of attributes defining a tabu restriction to be given different values for the tenure t. For example, some attributes can contribute more strongly to a tabu restriction than others, and should be given a briefer tabu tenure to avoid making the restriction too severe. To illustrate, consider a problem of identifying an optimal subset of m items from a much larger set of n items. (E.g., such a problem may involve identifying a subset of m edges from an n-edge graph to create a traveling salesman tour, or a subset of m locations from n available sites to establish distribution centers, or a subset of m nodes from an n-node complex to serve as telecommunication switching centers, etc.) Suppose each move consists of exchanging one or a small number of items in the subset with an equal number outside the subset, to create a new subset of m items. Accompanying this, also suppose a tabu restriction is used that forbids a move if it contains either an item recently added or an item recently dropped, where the tabu tenure provides the meaning of "recently." 

If the tenure for added and dropped items is the same, the preceding restriction can become very lopsided. In particular, when other factors are equal, preventing items in the subset from being dropped is much more restrictive than preventing items not in the subset from being added, since there are far fewer contained in the subset contained outside. In addition, preventing elements added to the subset from being dropped for a relatively long time can significantly inhibit available choices, and hence the tenure for these elements should be made small by comparison to the tenure for preventing elements dropped from the subset from being added, whether by using static or dynamic rules. 

Practical experience indicates that dynamic rules typically are more robust than static rules. Good parameter values for dynamic rules normally range over a wider interval, and produce results comparable or superior to the outcomes produced by static rules. Dynamic rules that depend on both attribute type and quality, where greater tenures are allotted to prevent reversals of attributes that participate in high quality moves, have proved quite effective for difficult problems related to scheduling and routing.

2.7 Aspiration Criteria 

Aspiration criteria are introduced in tabu search to determine when tabu restrictions can be overridden, thus removing a tabu classification otherwise applied to a move. The appropriate use of such criteria can be very important for enabling a TS method to achieve its best performance levels. 

Early applications employed only a simple type of aspiration criterion, consisting of removing a tabu classification from a trial move when the move yields a solution better than the best obtained so far. (Such a rule is illustrated in the example of Section 2.1.) This criterion remains widely used. However, other aspiration criteria can also prove effective for improving the search. 

A basis for one of these criteria arises by introducing the concept of influence, which measures the degree of change induced in solution structure or feasibility. (Influence often is associated with the idea of move distance, i.e., where a move of greater distance is conceived as having greater influence (Glover, 1990).) This notion can be illustrated for a problem of distributing unequally weighted objects among boxes, where the goal is to give each box as nearly as possible the same weight. A high influence move, that significantly changes the structure of the current solution, is exemplified by a move that transfers a heavy weight object from one box to another, or that swaps objects of very dissimilar weights between two boxes. Such a move mayor may not improve the current solution, though it is less likely to yield an improvement when the current solution is relatively good. But high influence moves are important, especially during intervals of breaking away from local optimality, because a series of moves that is confined to making only small structural changes is unlikely to uncover a chance for significant improvement (Such an effect is illustrated in job sequencing problems by exchanging positions of jobs that are close together.) 

Moves of lower influence normally may be tolerated until the opportunities for gain from them appear to be negligible. At such point, and in the absence of improving moves, aspiration criteria should shift to give influential moves a higher rank. Also, once an influential move is made, tabu restrictions previously established for less influential moves should be dropped or "weakened," in a manner to be explained. (Bias that may be employed to favor the choice of other influential moves likewise should be temporarily diminished.) These considerations of move influence interact with considerations of regionality and search direction, as indicated below. 

Aspirations are of two kinds: move aspirations and attribute aspirations. A move aspiration, when satisfied, revokes the move's tabu classification. An attribute aspiration, when satisfied, revokes the attribute's tabu-active status. In the latter case the move mayor may not change its tabu classification, depending on whether the tabu restriction can be activated by more than one attribute. 

The following criteria determine the admissibility of a trial solution, xTrial, as a candidate for consideration (potentially to become xNext), where xTrial is generated by a move that ordinarily would be classified tabu. The first of these criteria is rarely applicable, but is understood automatically to be part of any tabu search procedure. 

Illustrative Aspiration Criteria 

Aspiration by Default:
 If all available moves are classified tabu, and are not rendered admissible by some other aspiration criteria, then a "least tabu" move is selected. (For example, select a move that loses its tabu classification by the least increase in the value of CurrentIteration, or by an approximation to this condition.) 

Aspiration by Objective: 
Global form (customarily used): A move aspiration is satisfied, permitting xTrial to be a candidate for selection, if c(xTrial) < BestCost. 
Regional form: Subdivide the search space into regions R ε X, identified by bounds on values of functions g(x) (or by time intervals of search). Let BestCost(R) denote the minimum c(x) for x found in R. Then, for xTrial ε R, a move aspiration is satisfied (for moving to xTrial) if c(xTrial) < BestCost(R). 

Aspiration by Search Direction:
 Let direction(e) = improving if the most recent move containing ε was an improving move, and direction(e) = nonimproving, otherwise. (direction(e) and TabuEnd(e) are set to their current values on the same iteration.) An attribute aspiration for ε is satisfied (making ε tabu-inactive) if direction(e) = improving and the current trial move is an improving move, i.e., if c(xTrial) < c(x_nDw). 

Aspiration by Influence:
 Let influence(e) = 0 or 1 according to whether the move that establishes the value of TabuStart(e) is a low influence move or a high influence move. (influence(e) is set at the same time as setting TabuStart(e).) Also, let latest(L), for L = 0 or I, equal the most recent iteration that a move of influence level L was made. Then an attribute aspiration for ε is satisfied if influence(e) = 0 and TabuStart(e) < latest(1). (e is associated with a low influence move, and a high influence move has been performed since establishing the tabu status for e.) For multiple influence levels, L = 0, 1,2, ..., the aspiration for ε is satisfied if there is an L > influence(e) such that TabuStart(e) < latest(L). 

The preceding aspiration criteria include several useful strategies for tabu search that have not yet been widely examined and that warrant fuller investigation. For example, a special case of the Regional Aspiration by Objective occurs by defining R = (x: g(x) = r}, where g(x) is a hash function created to distinguish among different x vectors according to the value assigned to g(x). (E.g., g(x) can be an integer-valued function defined modulo p, taking the values r = 0, 1, ..., p -1.) Then BestCost(R) is conveniently recorded as BestCost(r), identifying the minimum c(x) found when g(x) = r. The "regionality" defined by R in this case provides a basis for integrating the elements of aspiration and differentiation. (A g(x) hash function also can be treated as an attribute function, and incorporated into tabu restrictions as described earlier. Or in reverse, a hash function can be treated as an attribute function, and incorporated into tabu restrictions as described earlier. Or in reverse, a hashing function can be defined over attributes, with particular emphasis on those that qualify as influential.) 

Aspiration by Search Direction and Aspiration by Influence provide attribute aspirations rather than move aspirations. In most cases attribute and move aspirations are equivalent. (Among the tabu restrictions of Section 2.5.2, only (R3) can provide conditions where these two types of aspirations differ, i.e., where an attribute may be tabu-inactive without necessarily revoking the tabu classification of the associated move.) Nevertheless, different means are employed for testing these two kinds of aspirations. 

2.7.1 Aspiration Criteria Refinements.

Refinements of the criteria illustrated above provide an opportunity to enhance the power of tabu search for applications that are more complex, or that offer a large reward for solutions of very high quality. We identify some of the possibilities for achieving this in the following. 

Creating a tabu status that varies by degrees, rather than simply designating an attribute to be tabu-active or tabu-inactive, leads to an additional refinement of Aspiration by Search Direction and Aspiration by Influence. Graduated tabu status is implicit in the penalty function and probabilistic variants of tabu search, where status is customarily expressed as a function of how recently or frequently an attribute has become tabu-active. However, to employ this idea to enhance the preceding aspiration criteria, we create a single additional intermediate tabu state that falls between the two states of tabu-active and tabu-inactive. In particular, when an aspiration is satisfied for an attribute that otherwise is tabu-active, we call it a pending tabu attribute.
 
A move that would be classified tabu if its pending tabu attributes are treated as tabu-active, but that would not be classified tabu otherwise, correspondingly is called a pending tabu move. A pending tabu move can be treated in one of two ways. In the least restrictive approach, such a move is not prevented from being selected, but is shifted in status so that it will only be a candidate for selection if no improving moves exist except those that are tabu. In the more moderate approach, a pending tabu move additionally must be an improving move to qualify for selection. (This will occur automatically for Aspiration by Search Direction, since in this case a move can only become a pending tabu move when it is improving.) 

An Aspiration Consequence for Strong Admissibility. The preceding notions lead to an additional type of aspiration. Define a move to be strongly admissible if: (1) it is admissible to be selected and does not rely on aspiration criteria to qualify for admissibility, or (2) it qualifies for admissibility based on the Global Aspiration by Objective, by satisfying c(xTrial) < BestCost. 

Aspiration by Strong Admissibility: 
Let LastNonimprovement equal the most recent iteration that a nonimproving move was made, and let LastStronglyAdmissible equal the most recent iteration that a strongly admissible move was made. Then, if LastNonimprovement < LastStronglyAdmissible, re-classify every improving tabu move as a pending tabu move (thus allowing it to be a candidate for selection if no other improving moves exist). 

The inequality LastNonimprovement < LastStronglyAdmissible of the preceding aspiration condition implies two things: fIrst that a strongly admissible improving move has been made since the last nonimproving move, and second that the search currently is generating an improving sequence. (The latter results since only improving moves can occur on iterations more recent than LastNonimprovement, and the set of such iterations is nonempty.) 

This type of aspiration insures that the method will always proceed to a local optimum whenever an improving sequence is created that contains at least one strongly admissible move. In fact, condition (2) defining a strongly admissible move can be removed without altering this effect, since once the criterion c(xTria/) < BestCost is used to justify a move selection, then it will continue to be satisfied by all improving moves on subsequent iterations until a local optimum is reached. 

Because of its extended ability to override tabu status, the Aspiration by Strong Admissibility may be predicated on the requirement that a move with a high influence level has been made since the end of the most recent (previous) improving sequence. Specifically, such a high influence move should have occurred on an iteration greater than the most recent iteration prior to LastNonimprovement on which an improving move was executed. This added requirement is applicable whether or not Aspiration by Influence is used. 

These ideas can be used to generate an alternating TS method related to the tabu thresholding approach of Glover (1992). Such a method results by adding a further condition to the Aspiration by Strong Admissibility, stipulating that once a non-improving move is executed, then no improving move is allowed unless it is strongly admissible, thereby generating what may be called an alternating tabu path. The consequence is that each improving sequence in such an alternating tabu path terminates with a local optimum. (An Aspiration by Default must also be considered a strongly admissible move to assure this in exceptional cases.) 

The effect of tabu status in this alternating approach can be amplified during a non-improving phase by interpreting the value TabuEnd(e) to be shifted to a larger value for all attributes e, until a strongly admissible move is executed and the phase ends.2.7.2 Special Considerations for 

Aspiration by Influence 

The Aspiration by Influence criterion can be modified to create a considerable impact on its effectiveness for certain types of applications. The statement of this aspiration derives from the observation that a move characteristically is influential by virtue of containing one or more influential attributes (jobs with large set up or processing times, warehouses with large capacities, circuits with multiple switches, etc.). Under such conditions, it is appropriate to consider levels of influence defined over attributes, as expressed by influence(e). In other cases, however, a move may derive its influence from the unique combination of attributes involved, and Aspiration by Influence then preferably translates into a move aspiration rather than an attribute aspiration. (In some instances the attribute orientation can be maintained by defining influence(e) to be the influence of the trial move that contains e.) 

More significantly, in many applications influence depends on a form of connectivity, causing its effects to be expressed primarily over a particular range. We call this range the sphere of influence of the associated move or attribute. For example, in the problem of distributing weighted objects among boxes, a move that swaps objects between two boxes has a relatively narrow sphere of influence, affecting only those future moves that transfer an object into or out of one of these two boxes. Accordingly, under such circumstances Aspiration by Influence should be confined to modifying the tabu status of attributes, or the tabu classification of moves, that fall within an associated sphere of influence. In the example of swapping objects between boxes, the attributes rendered tabu-inactive would be restricted to FromAttributes associated with moving an object out of one of the two boxes and ToAttributes associated with moving an object into one of these boxes. The change of tabu status continues to depend on the conditions noted previously. The influence of the attribute (or move containing it) must be less than that of the earlier move, and the iteration TabuStart(e) for the attribute must precede the iteration on which the earlier influential move occuued. These conditions can be registered by setting a flag for TabuStart(e) when the influential move is executed, without having to check again later to see if ε is affected by such a move. When TabuStart(e) becomes reassigned a new value, the flag is dropped. 

As the preceding observations suggest, effective measures of move influence and associated characterizations of spheres of influence are extremely important. In addition, it should be noted that influence can be expressed as a function of tabu search memory components, as where a move containing attributes that have neither recently nor frequently been tabu-active may be classified as more highly influential (because executing the move will change the tabu status of these attributes more radically). This encourages a dynamic definition of influence, which varies according to the current search state. These multiple aspects of move influence are likely to constitute a more significant area for future investigation in tabu search. 

2.8 Frequency Based Memory 

Frequency based memory provides a type of information that complements the information provided by recency based memory, broadening the foundation for selecting preferred moves. Like recency, frequency often is weighted or decomposed into subclasses by taking account of the dimensions of solution quality and move influence. 

For our present purposes, we conceive frequency measures to consist of ratios, whose numerators represent counts of the number of occurrences of a particular event (e.g., the number of times a particular attribute belongs to a solution or move) and whose denominators generally represent one of four types of quantities: (I) the total number of occurrences of all events represented by the numerators (such as the total number of associated iterations), (2) the sum of the numerators, (3) the maximum numerator value, and (4) the average numerator value. Denominators (3) and (4) give rise to what may be called relative frequencies. The meaning of these different types of frequencies will be clarified by examples below. In cases where the numerators represent weighted counts, some of which may be negative, denominators (3) and (4) are expressed as absolute values and denominator (2) is expressed as a sum of absolute values (possibly shifted by a small constant to avoid a zero denominator). 

Let x(I), x(2), ..., x(CurrentIteration) denote the sequence of solutions generated to the present point of the search process, and let S denote a subsequence of this solution sequence. We take the liberty of treating S as a set as well as an ordered sequence. Elements of S are not necessarily consecutive elements of the full solution sequence. (For example, we sometimes will be interested in cases where S consists of different subsets of high quality local optima.) 

Notationally, we let S(xj = p) denote the set of solutions in S for which xj = p, and let #S(xj = p) denote the cardinality of this set (hence the number of times xj receives the value p over x ε  S). Similarly, let S(xj = p to xj  = q) denote the set of solutions in S that result by a move that changes xj = p to xj = q. Finally, let S(from xj = p) and S(to xj = q) denote the sets of solutions in S that respectively contain xj = p as a FromAttribute or Xj = q as a ToAttribute (for a move to the next solution, or from the preceding solution, in the sequence x(I), ..., x(CurrentIteration). In general, if SolutionAttribute represents any attribute of a solution that can take the role of a FromAttribute or a ToAttribute for a move, and if MoveAttribute represents an arbitrary move attribute denoted by (FromAttribute, ToAttribute), then 

S(SolutionAttribute) S(MoveAttribute) S(FromAttribute) S(ToAttribute) 

= {x ε S: x contains SolutionAttribute} 
= {x ε S: x results by a move containing MoveAttribute} = {x ε S: x initiates a move containing 
FromAttribute} = {x ε S: x results by a move containing ToAttribute}. 

The quantity #S(xj  = p) constitutes a residence measure, since it identifies the number of times the attribute xj = p resides in the solutions of S. Correspondingly, we call a frequency that results by dividing such a measure by one of the denominators (1) to (4) a residence frequency. For the numerator #S(xj = p), the denominators (1) and (2) both correspond to #S, while denominators (3) and (4) respectively are given by Max(#S(xk = q): all k, q) and by Mean(#S(xk = q): all k, q). 

The quantities #S(xj =  to xj = q), #S(from xj = p) and #S(to xj = q) constitute transition measures, since they identify the number of times xj changes from and/or to specified values. Likewise, frequencies based on such measures are called transition frequencies. Denominators for creating such frequencies from the foregoing measures include #S, the total number of times the indicated changes occur over S for different j, p and/or q values, and associated Max and Mean quantities. 

Distinctions Between Frequency Types. Residence frequencies and transition frequencies sometimes convey related information, but in general carry different implications. They are sometimes confused (or treated identically) in the literature. A noteworthy distinction is that residence measures, by contrast to transition measures, are not concerned with whether a particular solution attribute of an element x(i) in the sequence S is aFromAttribute or a ToAttribute, or even whether it is an attribute that changes in moving from x(i) to x(i+l) or from x(i-l) to x(i). It is only relevant that the attribute can be aFromAttribute or a ToAttribute in some future move. Such measures can yield different types of implications depending on the choice of the subsequence S. 

A high residence frequency, for example, may indicate that an attribute is highly attractive if S is a subsequence of high quality solutions, or may indicate the opposite if S is a subsequence of low quality solutions. On the other hand, a residence frequency that is high (or low) when S contains both high and low quality solutions may point to an entrenched (or excluded) attribute that causes the search space to be restricted, and that needs to be jettisoned (or incorporated) to allow increased diversity. 

From the standpoint of computational simplification, when S consists of all solutions generated after a specified iteration, then a residence measure can be currently maintained and updated by reference to values of the TabuStart array, without the need to increment a set of counters at each iteration. For a set S whose solutions do not come from sequential iterations, however, residence measures are calculated simply by running a tally over elements of S. 

Transition measures are generally quite easy to maintain by performing updates during the process of generating solutions (assuming the conditions defining S, and the attributes whose transition measures are sought, are specified in advance). This results from the fact that typically only a few types of attribute changes are considered relevant to track when one solution is replaced by the next, and these can readily be isolated and recorded. The frequencies in the example of Section 2.1 constitute an instance of transition frequencies that were maintained in this simple manner. Their use in this example, however, encouraged diversity by approximating the type of role that residence frequencies are usually better suited to take. 

As a fmal distinction, a high transition frequency, in contrast to a high residence frequency, may indicate an associated attribute is a "crack filler," that shifts in and out of solution to perform a fine tuning function. Such an attribute may be interpreted as the opposite of an influential attribute, as considered earlier in the discussion of Aspiration by Influence. In this context, a transition frequency may be interpreted as a measure of volatility. 

Examples and Uses of Frequency Measures. lllustrations of both residence and transition frequencies are as follows. (Only numerators are indicated, understanding denominators to be provided by conditions (1) to (4).) 

Example Frequency Measures (Numerators) 

(FI) #S(xj = p) 
(F2) #S(xj = p for some xj  
(F3) #S(to xj = p) 
(F4) #S(Xj changes), i.e., #S(From-or-To Xj = p for some p)
 (F5) ∑(c(x): x ε S(xj = p))/#S(xj = p)
 
Measure (F5) may be interpreted as the average c(x) value over S when xj = p. This quantity can be directly compared to other such averages or can be translated into a frequency measure using denominators such as the sum or maximum of these averages.
 
Attributes that have greater frequency measures, just as those that have greater recency measures (ie., that occur in solutions or moves closer to the present), can initiate a tabu-active status if S consists of consecutive solutions that end with the current solution. However, frequency based memory typically fmds its most productive use as part of a longer term strategy, which employs incentives as well as restrictions to determine which moves are selected. In such a strategy, restrictions are translated into evaluation penalties, and incentives become evaluation enhancements, to alter the basis for qualifying moves as attractive or unattractive. 

To illustrate, an attribute such as xj = p with a high residence frequency may be assigned a strong incentive ("profit") to serve as a FromAttribute, thus resulting in the choice of a move that yields xj  ≠ p. Such an incentive is particularly relevant in the case where TabuStart(xj ≠ p) is small, since this value identifies the latest iteration that xj  ≠ p served as a FromAttribute (for avoiding reversals), and hence discloses that xj  = p has been an attribute of every solution since. 

Frequency based memory therefore is usually applied by introducing graduated tabu states, as a foundation for defining penalty and incentive values to modify the evaluation of moves. A natural connection exists between this approach and the recency based memory approach that creates tabu status as an all-or-none condition. If the tenure of an attribute in recency based memory is conceived as a conditional threshold for applying a very large penalty, then the tabu classifications produced by such memory can be interpreted as the result of an evaluation that becomes strongly inferior when the penalties are activated. It is reasonable to anticipate that conditional thresholds should also be relevant to determining the values of penalties and incentives in longer term strategies. Most applications at present, however, use a simple linear multiple of a frequency measure to create a penalty or incentive term. 

2.9 Frequency Based Memory in Simple Intensification and Diversification Processes 

The roles of intensification and diversification in tabu search are already implicit in several of the preceding prescriptions, but they become especially relevant in longer term search processes. Intensification strategies undertake to create solutions by aggressively encouraging the incorporation of "good attributes." In the short term this consists of incorporating attributes receiving highest evaluations by the approaches and criteria previously described, while in the intermediate to long term it consists of incorporating attributes of solutions from selected elite subsets (implicitly focusing the search in subregions defined relative to these subsets). Diversification strategies instead seek to generate solutions that embody compositions of attributes significantly different from those encountered previously during the search. These two types of strategies counterbalance and reinforce each other in several ways. 

We examine simple forms of intensification and diversification approaches that make use of frequency based memory. These approaches will be illustrated by reference to residence frequency measures, but similar observations apply to the use of transition measures, taking account of contrasting features previously noted. 

For a diversification strategy we choose S to be a significant subset of the full solution sequence; for example, the entire sequence starting with the first local optimum, or the subsequence consisting of all local optima. (For certain strategies based on transition measures, S may usefully consist of the subsequence containing each maximum unbroken succession of non-improving moves that immediately follow a local optimum, focusing on S(ToAttribute) for these moves.)
 
For an intensification strategy we choose S to be a small subset of elite solutions (high quality local optima) that share a large number of common attributes, and secondarily whose members can reach each other by relatively small numbers of moves, independent of whether these solutions lie close to each other in the solution sequence. For example, collections of such subsets S may be generated by clustering procedures, followed by employing a parallel processing approach to treat each selected S separately. 

For illustration purposes, suppose that a move currently under consideration includes two move attributes, denoted ε and/, which further may be expressed as e = (eFrom, eTo) and f = (fFrom, fTo). We provide rules for generating a penalty or incentive function, PI, based on the frequency measures of the attributes ε and/, which applies equally to intensification and diversification strategies. However, the function PI creates a penalty for one strategy (intensification or diversification) if and only if it creates an incentive for the other. To describe this function, we let F(eFrom) and F(eTo), etc., denote the frequency measure for the indicated FromAttributes and ToAttributes, and let TI, T2, ..., T6 denote selected positive thresholds, whose values depend on the case considered. 

Illustrative Penalty/Incentive Function PI tor ToAttributes 
================================================================
Choose PI as a monotonic non-decreasing function of one of the following quantities, where PI is positive when the quantity is positive, and is 0 otherwise. (PI yields a penalty in a diversification strategy and an incentive in an intensification strategy.) 

(1) Min(F(eTo).F(fTo)) –T1
(2) Max(F(eTo),  F(fTo)) -T2 
(3) Mean(F(eTo), F(fTo)) -T3

Illustrative Penalty/Incentive Function PI for FromAttributes 
================================================================

Choose PI as a monotonic non-decreasing function of one of the following quantities, where PI is positive when the quantity is positive, and is 0 otherwise. (PI yields an incentive in a diversification strategy and a penalty in an intensification strategy.)

(4) Min(F(eFrom),F(fFrom)) -T4 
(5) Max(F(eFrom), F(fFrom)) -T5 
(6) Mean(F(eFrom), F(fFrom» -T6 

The preceding conditions for defining PI are related to those previously illustrated to identify conditions in which attributes become tabu-active. For example, specifying that (1) must be positive to make PI positive corresponds to introducing a tabu penalty (or incentive) when both measures exceed their common threshold. If a measure is expressed as the duration since an attribute was most recently made tabu-active, and if the threshold represents a common limit for tabu tenure, then (1) can express a recency based restriction for determining a tabu classification. 

Assigning different thresholds to different attributes in (1) corresponds to establishing attribute- dependent tabu tenures. Similarly, the remaining values (2) through (7) may be interpreted as analogs of values that define recency based measures for establishing a tabu classification, implemented in this case by a penalty. 

From these observations, it is clear the frequency measure F may be extended to represent combined measures of both recency and frequency. Note that recency based memory, by storing TabuStart dates, also can refer to changes that have occurred farther in the past as well as those that have occurred more recently. Although these measures are already implicitly combined when penalties and incentives based on frequency measures are joined with tabu classifications based on recency measures, as a foundation for selecting current moves, it is possible that other forms of combination are superior. For example, human problem solving appears to rely on combinations of these types of memory that incorporate a time discounted measure of frequency. Such considerations may lead to the design of more intelligent functions for capturing preferred combinations of these memory types. 

3. Broader Aspects of Intensification and Diversification 

Intensification and diversification approaches that utilize penalties and incentives represent only one class of such strategies. A larger collection emerges by direct consideration of intensification and diversification goals. We examine several approaches that have been demonstrated to be useful in previous applications, and also indicate approaches we judge to have promise in applications of the future. To begin, we make an imponant distinction between diversification and randomization. 

Diversification versus Randomization. When tabu search seeks a diversified collection of solutions, is much different than seeking a randomized collection of solutions. In general, we are interested not just in diversified collections but also in diversified sequences, since often the order of examining elements is important in tabu search. This can apply, for example, where we seek to identify a sequence of new solutions (not seen before) so that each successive solution is maximally diverse relative to all solutions previously generated. This includes possible reference to a baseline set of solutions, such as x ε S, which takes priority in establishing the diversification objective (ie., where the first level goal is establish diversification relative to S, and then in turn relative to other solutions generated). The diversification concept applies as well to generating a diverse sequence of numbers or a diverse set of points from the vertices of a unit hypercube. 

Let Z(k) = (z(1), z(2), ..., z(k)) represent a sequence of points drawn from a set Z. For example, Z may be a line interval if the points are scalars. We take z(1) to be a seed point of the sequence. (The seed point may be excepted from the requirement of belonging to Z.) Then we define Z(k) to be a diversified sequence (or simply a diverse sequence), relative to a chosen distance metric d over Z by requiring each subsequence Z(h) of Z(k), h <: k, an each associated point z = z(h+ 1) to satisfy the following hierarchy of conditions: 

(A) z maximizes the minimum distance d(z, z(i)) for i ≤ h; 
(B) subject to (A), z maximizes the minimum distance d(z, z(i)) for 1 < i ≤ h, then for 2 < i ≤ h, ..., etc. (in strict priority order). 
(C) subject to (A) and (B), z maximizes the distance d(z, z(i) for i = h, then for i = h -1, ..., and finally for i = 1. (Additional ties may be broken arbitrarily.) 

To handle diversification relative to an initial baseline set Z* (such as a set of solutions x ε S), the preceding hierarchy of conditions is preceded by a condition stipulating that z fIrst maximizes the minimum distance d(z, z*) for z* ε Z*. A useful (weaker) variant of this condition simply treats points of z* as if they constitute the last elements of the sequence Z(h). 

Variations on (A), (B), and (C), including going deeper in the hierarchy before: arbitrary tie breaking, are evidently possible. Such conditions make it clear that a diverse sequence is considerably different from a random sequence. Further, they are computationally very demanding to satisfy. Even by omitting condition (B), and retaining only (A) and (C), if the elements z(t} refer to points on a unit hypercube, then by our present state of knowledge the only way to generate a diverse sequence of more than a few points is to perform comparative enumeration. (However, a diverse sequence of points on a line interval, particularly if z(l) is an endpoint or midpoint of the interval, can be generated with much less difficulty.) Because of this, it can sometimes be useful to generate sequences by approximating the foregoing conditions. Taking a broader view, an extensive effort to generate diverse sequences can be performed in advance, independent of problem solving efforts, so that such sequences are pre-computed and available as needed. Further, a diverse sequence for elements of a high dimensional unit hypercube may be derived by reverse projection techniques ("lifting" operations) from a sequence for a lower dimensional hypercube, ultimately making reference to sequences from a line interval. 

Biased diversification, just as biased random sampling, is possible by judicious choices of the set Z. Also, while the goals of diversification and randomization are somewhat different, the computational considerations share a feature in common. To generate a random sequence by the strict definition of randomness would require massive effort. Years of study have produced schemes for generating sequences that empirically approximate this goal, and perhaps a similar outcome may be possible for generating diversified sequences. The hypothesis of tabu search, in any case, is that recourse to diversification is more appropriate (and more powerful) in the problem solving context than recourse to randomization. 

We note these observations can be applied in a setting, as subsequently discussed, where the device of producing a solution "distant from" another is accomplished not by reference to a standard distance metric, but rather by a series of displacements which involve selecting a move from a current neighborhood at each step. (In this case the metric may derive from differences in weighted measures defined over FromAttributes and ToAttributes.) An application of these ideas is given in Kelly, Laguna, and Glover (1994), and we also discuss a special variation under the heading of "Path Relinking" below. This stepwise displacement approach is highly relevant to those situations where neighborhood structures are essential for preserving desired properties (such as feasibility). 

Reinforcement by Restriction. One of the early types of intensification strategies, characterized in terms of exploiting strongly determined and consistent variables in (Glover, 1977), begins by selecting a set S as indicated for determining a penalty and incentive function, i.e., one consisting of elite solutions grouped by a clustering measure. Instead of (or in addition to) creating penalties and incentives, with the goal of incorporating attributes into the current solution that have high frequency measures over S, the method of reinforcement by restriction operates by narrowing the range of possibilities allowed for adding and dropping such attributes. For example, if Xj = P has a high frequency over S for only a small number of values of p, then moves are restricted to allow Xj to take only one of these values in defining a ToAttribute. 

Thus, if Xj is a 0-1 variable with a high frequency measure over S for one of its values, then this value will become fixed once an admissible move exists that allows such a value assignment to be made. Other assignments may be permitted, by a variant of Aspiration by Default, if the current set of restricted alternatives is unacceptable. 

Initial consideration suggests such a restriction approach offers nothing beyond the options available by penalties and incentives. However, the approach can accomplish more than this for two reasons. First, explicit restrictions can substantially accelerate the execution of choice steps by reducing the number of alternatives examined. Second, and more significantly, many problems simplify and collapse once a number of explicit restrictions are introduced, allowing structural implications to surface that permit these problems to be solved far more readily. 

Reinforcement by restriction is not limited to creating an intensification effect Given finite time and energy to explore alternatives, imposing restrictions on some attributes allows more variations to be examined for remaining unrestricted attributes than otherwise would be possible. Thus, intensification with respect to selected elements can enhance diversification over other elements, creating a form of selective diversification. Such diversification may be contrasted with the exhaustive diversification created by the more rigid memory structures of branch and bound. In an environment where the finiteness of available search effort is dwarfed by the number of alternatives that exist to be explored exhaustively, selective diversification can make a significant contribution to effective search. 

Path Relinking. Path relinking is initiated by selecting two solutions x' and x" from a collection of elite solutions produced during previous search phases. A path is then generated from x' to x", producing a solution sequence x' = x'(l), x'(2), ..., x'(r) = x", where x'(i+ 1) is created from x'(i) at each step by choosing a move that leaves the fewest number of moves remaining to reach x". (A choice criterion for approximating this effect is indicated below.) Finally, once the path is completed, one or more of the solutions x'(z) is selected as a solution to initiate a new search phase. 

This approach provides a fundamental means for pursuing the goals of intensification and diversification when its steps are implemented to exploit strategic choice rule variations. A number of alternative moves typically will qualify to produce a next solution from x'(i) by the "fewest remaining moves" criterion, consequently allowing a variety of possible paths from x' to x". Selecting unattractive moves relative to c(x) at each step will tend to produce a final series of strongly improving moves, while selecting attractive moves will tend to produce lower quality moves at the end. (The last move, however, will be improving, or leave c(x) unchanged, since x" is a local optimum.) Thus, choosing best, worst or average moves, using an aspiration criterion to override choices in the last two cases if a sufficiently attractive solution is available, provide options that produce contrasting effects in generating the indicated sequence. (Arguments exist in favor of selecting best moves at each step, and then repeating the process by interchanging x' and x".) 

The issue of an appropriate aspiration more broadly is relevant to selecting a preferred x'(i) for launching a new search phase, and to terminating the sequence early. The choice of one or more solutions x'(z) to launch a new search phase preferably should depend not only on c(x'(i» but also on the values c(x) of those solutions x that can be reached by a move from x'(i). In particular, when x'(z) is examined to move to x'(i+l), a number of candidates for x = x'(i+ 1) will be presented for consideration. The process additionally may be varied to allow solutions to be evaluated other than those that yield x'(i+ 1) closer to x". 

Let x*(i) denote a neighbor of x'(i) that yields a minimum c(x) value during an evaluation step, excluding x*(z) = x'(i+ 1). (If the choice rules do not automatically eliminate the possibility x*(z) = x'(h) for h < i, then a simple tabu restriction can be used to do this.) Then the method selects a solution x*(i) that yields a minimum value for c(x*(i)) as a new point to launch the search. If only a limited set of neighbors of x'(i) are examined to identify x*(i), then a superior least cost x'(z), excluding x' and x", may be selected instead. Early termination may be elected upon encountering an x*(i) that yields c(x*(i» < Min(c(x'), c(x"), c(x'(P», where x'(P) is the minimum cost x'(h) for all h ≤ i. (The procedure continues without stopping if x'(i), in contrast to x*(i), yields a smaller c(x) value than x' and x", since x'(z) effectively adopts the role of x'.) 

Variation and Tunneling. A variant of the path relinking approach proposed in (Glover, 1991c) starts both endpoints x' and x" simultaneously, producing two sequences x' = x'(l), ..., x'(r) and x" = x"(1), ..., x"(s). The choices are designed to yield x'(r) = x"(s), for final values of r and s. To progress toward this outcome when x'(r) ≠ x"(s), either x'(r) is selected to create x'(r+ 1), by the criterion of minimizing the number of moves remaining to reach x"(s), or x'(s) is chosen to create x"(s+1), by the criterion of minimizing the number of moves remaining to reach x'(r). From these options, the move is selected that produces the smallest c(x) value, thus also determining which of r or s is incremented on the next step. 

The path relinking approach can benefit by a tunneling approach that allows a different neighborhood structure to be used than in the standard search phase. In particular, it often is desirable to periodically allow moves for path relinking that normally would be excluded due to creating infeasibility. Such a practice is less susceptible to becoming "lost" in an infeasible region than other ways of allowing periodic infeasibility, since feasibility evidently must be recovered by the time x" is reached. The tunneling effect thus created offers a chance to reach solutions that might otherwise be bypassed. In the variant that starts from both x' and x", at least one of x'(r) and x"(s) may be kept feasible. 

Path relinking can be organized to place greater emphasis on intensification or diversification by choosing x' and x" to share more or fewer attributes in common. Similarly choosing x' and x" from a clustered set of elite solutions will stimulate intensification, while choosing them from two widely separated sets will stimulate diversification. 

Extrapolated Relinking. An extension of the path relinking approach, which we call extrapolated relinking, goes beyond the path endpoint x"( or alternatively x'), to obtain solutions that span a larger region. The ability to continue beyond this endpoint results by a method for approximating the move selection criterion specified for the standard path relinking approach, which seeks a next solution that leaves the fewest moves remaining to reach x". Specifically, let A(x) denote the set of solution attributes in x, and let DropA denote the set of solution attributes that are dropped by moves performed to reach the current solution x'(i), i.e., the attributes that have served as FromAttributes in these moves. (Some of these may have been reintroduced into x'(i), but they also remain in DropA.) Then we seek a move at each step to maximize the number of ToAttributes that belong to A(x") -A(x'(i)), and subject to this to minimize the number that belong to DropA -A(x"). Such a rule generally can be implemented very efficiently, by data structures limiting the examination of moves to those containing to- attributes of A(x") -A(x'(i)) (or permitting these moves to be examined before others).
 
Once x'(r) = x" is reached, the process continues by modifying the choice rule as follows. The criterion now selects a move to maximize the number of its ToAttributes not in DropA minus the number of its ToAttributes that are in DropA, and subject to this to minimize the number of its FromAttributes that belong to A(x"). (The combination of these criteria establishes an effect analogous to that achieved by the standard algebraic formula for extending a line segment beyond an endpoint However, the secondary minimization criterion is probably less important.) The path then stops whenever no choice remains that permits the maximization criterion to be positive. 

For neighborhoods that allow relatively unrestricted choices of moves, this approach yields an extension beyond x" that introduces new attributes, without reincorporating any old attributes, until no move remains that satisfies this condition. The ability to go beyond the limiting points x' and x" creates a form of diversification not available to the path that "lies between" these points. At the same time the exterior points are influenced by the trajectory that links x' and x". 

Solutions Evaluated but Not Visited. Intensification and diversification strategies may profit by the fact that a search process generates information not only about solutions actually visited, but also about additional solutions evaluated during the examination of moves not taken. One manifestation of this is exploited by reference to the solutions x*(i) in the path relinking approach. From a different point of view, let S* denote a subset of solutions evaluated but not visited (e.g., taken from the sequence x(l), ..., x(CurrentIteration)) whose elements x yield c(x) values within a chosen band of attractiveness. It is relatively easy to maintain a count such as #S*(to xj =p), which identifies the number of times xj = p is a ToAttribute of a trial move leading to a solution of S*. Such a count may be differentiated further by stipulating that the trial move must be improving, and of high quality relative to other moves examined on the same iteration. (Differentiation of this type implicitly shrinks the composition of S*.) Then an attribute that achieves a relatively high frequency over S*, but that has a low residence frequency over solutions actually visited, is given an incentive to be incorporated into future moves, simultaneously serving the goals of bOth intensification and diversification. Recency and frequency interact in this approach by disregarding the incentive if the attribute has bee:n selected on a recent move. 

Interval Specific Penalties and Incentives. A useful adjunct to the preceding ideas extends the philosophy of Aspiration by Search Direction and Aspiration by Strong Admissibility. By these aspiration criteria, improving moves are allowed to escape a tabu classification under certain conditions, but with the result of lowering their status so that they are treated as inferior improving moves. An extension of this preserves the improving/non-improving distinction when penalties and incentives are introduced that are not intended to be preemptive. For this extension, evaluations again are divided into the intervals of improving and non-improving. Penalties and incentives then are given limited scope, degrading or enhancing evaluations within a given interval, but without altering the relationship between evaluations that lie in different intervals. 

Incentives granted on the basis of influence similarly are made subject to this restricted shift of evaluation. Since an influential move usually is not improving in the vicinity of a local optimum, maintaining the relationship between evaluations in different intervals implies such moves usually will be selected only when no improving moves exist, other than those classified tabu. But influential moves also have a recency based effect. Just as executing a high influence move can cancel the tabu classification of a lower influence move over a limited span of iterations, it also should reduce or cancel the incentive to select other influential moves for a corresponding duration. 

Candidate List Procedures. Section 2.4.1 stressed the importance of procedures to isolate a candidate subset of moves from a large neighborhood, to avoid the computational expense of evaluating moves from the entire neighborhood. Procedures of this form have been used in optimization methods for almost as long as issues of reducing computational effort have been taken seriously (since at least the 1950's and probably much earlier). Some of the more strategic forms of these procedures came from the field of network optimization (Glover, et al., 1974; Mulvey, 1978; Frendewey, 1983). In such approaches, the candidate subset of moves is referenced by a list that identifies their defining elements (such as indexes of variables, nodes, or arcs), and hence these approaches have acquired the name of candidate list strategies. 

A simple form of candidate list strategy is to construct a single element list by sampling from the neighborhood space at random, and to repeat the process if the outcome is deemed unacceptable. This is the foundation of Monte Carlo methods, as noted earlier. Studies from network optimization, however, suggest that approaches based on more systematic designs produce superior results. Generally, these involve decomposing a neighborhood into critical subsets, and using a rule that assures subsets not examined on one iteration become sc:heduled for examination on subsequent iterations. For subsets appropriately determined, best outcomes result by selecting highest quality moves from these subsets, either by explicit examination of all alternatives or by using an adaptive threshold to identify such moves (see Glover, Glover, and Klingman, 1986). 

Another kind of candidate list strategy periodically examines larger portions of the neighborhood, creating a master list of some number of best alternatives found. The master list is then consulted to identify moves (derived from or related to those recorded) for additional iterations until a threshold of acceptability triggers the creation of a new master list.

Candidate list strategies implicitly have a diversifying influence by causing different parts of the neighborhood space to be examined on different iterations. This suggests there may be benefit from coordinating such strategies with other diversification strategies, an area that remains open for investigation. Candidate list strategies also lend themse1ves very naturally to parallel processing, where forms of neighborhood decomposition otherwise examined serially are examined in parallel. Moves can be selected by choosing the best candidate from several processes, or instead each process can execute its own preferred move, generating parallel solution trajectories that are periodically coordinated at a higher level. These latter approaches hold considerable promise. 

Compound Neighborhoods. Identifying an effective neighborhood for defIning moves from one solution to another can be extremely important For example, an attempt to solve a linear programming problem by choosing moves that increment or decrement problem variables, versus choosing moves that use pivot processes or directional search, obviously can make a substantial difference in the quality of the final solution obtained. The innovations that have made linear programming a powerful optimization tool rely significantly on the discovery of effective neighborhoods for making moves. 

For combinatorial applications where possibilities for creating neighborhoods are largely confined to various constructive or destructive processes, or to exchanges, improvements often result by combining neighborhoods to create moves. For example, in sequencing applications such as the one illustrated in Section 2.1, it generally is preferable to combine neighborhoods consisting of insert moves and swap moves, allowing both types of moves to be considered at each step. Another way of combining neighborhoods is to generate compound mo~'es, where a sequence of simpler moves is treated as a single more complex move. 

A special type of approach for creating compound moves results by a succession of steps in which an element is assigned to a new state, with the outcome of ejecting some other element form its current state. The ejected element then in turn is assigned to a new state, thus ejec:ting another element, and so forth, creating a chain of such operations. For example, such a process occurs in a job sequencing problem by moving a job to a new position occupied by another job, thereby ejecting this job from its position. The second job then is moved to a new position to eject yet another job, and so on, fmally ending by inserting the last ejected job between two jobs that are currently adjacent. This type of approach, called an ejection chain strategy, includes the ejection of links between elements (such as jobs) rather than ejecting the elements themselves, and also applies to aggregated elements and links. Ejection chain strategies have useful applications for problems of many types, particularly in connection with scheduling, routing, clustering, and partitioning (Glover, 1991a, 1992b; Domdorf and Pesch, 1994). A tabu search method incorporating ejection chains has proved highly successful for generalized assignment problems (Laguna, et al., 1991; Yagiura, Ibaraki and Glover, 2003), and also for traveling salesman problems (Rego and Glover, 2002) suggesting the relevance of these strategies for creating compound neighborhoods in other tabu search applications. 

Strategic Oscillation. The strategic oscillation approach is closely linked to the origins of tabu search, and provides an effective interplay between intensification and diversification over the intermediate to long term. Strategic oscillation operates by moving until hitting a boundary, represented by feasibility or a stage of construction, that normally would represent a point where the method would stop. Instead of stopping, however, the neighborhood definition is extended, or the evaluation criteria for selecting moves is modified, to permit the boundary to be crossed. The approach then proceeds for a specified depth beyond the boundary, and turns around. At this point the boundary again is approached and crossed, this time from the opposite direction, proceeding to a new turning point. The process of repeatedly approaching and crossing the boundary from different directions creates a form of oscillation that gives the method its name. Control over this oscillation is established by generating modified evaluations and rules of movement, depending on the region currently navigated and the direction of search. The possibility of retracing a prior trajectory is avoided by standard tabu mechanisms. 

A simple example of this approach occurs for the multidimensional knapsack problem, where values of zero-one variables are changed from 0 to 1 until reaching the boundary of feasibility. The method then continues into the infeasible region using the same type: of changes, but with a modified evaluator. Mter a selected number of steps, direction is reversed by changing variables from 1 to O. Evaluation criteria to drive toward improvement (or smallest disimprovement) vary according to whether the movement is from more-to-less or less-to-more feasible (or infeasible), and are accompanied by associated restrictions on admissible changes to values of variables. An implementation of such an approach by Freville and Plateau (:1986, 1990) has generated particularly high quality solutions for multidimensional knapsack problems. 

A somewhat different type of application occurs for the problem of finding an optimal spanning tree subject to inequality constraints on subsets of weighted edges. One type of strategic oscillation approach for this problem results by a constructive process of adding edges to a growing tree until it is spanning, and then continuing to add edges to cross the boundary defined by the tree construction. A different graph structure results when the current solution no longer constitutes a tree, and hence a different neighborhood is required, yielding modified rules for selecting moves. The rules again change in order to proceed in the opposite direction, removing edges until again recovering a tree. In such problems, the effort required by different rules may make it preferable to cross a boundary to different depths on different sides. An option is to approach and retreat from the boundary while remaining on a single side, without crossing (i.e., electing a crossing of "zero depth"). In this example, additional types of boundaries may be considered, derived from the inequality constraints. 

The use of strategic oscillation in applications that alternate constructive and destructive processes can be accompanied by exchange moves that maintain the construction at a given level. A proximate optimality principle, which states roughly that good constructions at one level are likely to be close to good constructions at another, motivates a strategy of applying exchanges at different levels, on either side of a target structure such as a spanning tree, to obtain refined constructions before proceeding to adjacent levels. 

Finally, we remark that the boundary incorporated in strategic oscillation need not be defined in terms of feasibility or structure, but can be defined in terms of a region where the search appears to gravitate. The oscillation then consists of compelling the search to move out of this region and allowing it to return.  

4. Tabu Search Applications 

The range of tabu search applications is already immense. As mentioned in the introduction, a substantial range of applications can be found by looking at the website www.tabusearch.net. Even so, new areas of application are continuing to emerge. For example, only very rececently have researchers begun to apply TS to areas of electrical engineering and biocomputing, resulting in more effective solution methods for a variety of critical problems in these domains. 

Somewhat surprisingly, many of these applications use forms of TS that do not take advantage of many of its ideas and strategies (such as discussed in this chapter). As stressed in Glover and Laguna (1997), of particular relevance are intelligently designed candidate list strategies, uses of advanced aspiration criteria, and careful attention to the interplay between intensification and diversification -- as well as the adoption of the compound moves and associated TS processes described in the preceding sections. It seems likely that even greater successes will result as more TS methods are implemented that embrace these fundamental strategic elements.

Bibliography 

Glover, F. and M. Laguna (1993).  Tabu Search. Modern Heuristic Techniques for Combinatorial Problems, C. Reeves, ed., Blackwell Scientific Publishing, pp. 71-140.

Glover, F. and M. Laguna (1997).  Tabu Search, Kluwer Academic Publishers.

Rego, C. and F. Glover (2002). Local Search and Metaheuristics for the Traveling Salesman Problem. The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Eds.,  Kluwer Academic Publishers, pp. 309-368.

Yagiura, M., T. Ibaraki and F. Glover (2003). An Ejection Chain Approach for the Generalized Assignment Problem. To appear in INFORMS Journal on Computing.