Tabu Search

The abundance of difficult optimization problems encountered in practical settings such as telecommunications, logistics, financial planning, transportation, and production has motivated the development of powerful optimization techniques. These techniques are usually the result of adapting ideas from a variety of research areas. The hope is to develop procedures that are efficient and are able to handle the complexity of today’s optimization problems. The ideas that motivate the particular structure of each methodology sometimes come from unexpected connections.

Tabu search can be applied directly to verbal or symbolic statements of many kinds of decision problems, without the need to transform them into mathematical formulations. Nevertheless, it is useful to introduce mathematical notation to express a broad class of these problems, as a basis for describing certain features of tabu search. We characterize this class of problems as that of optimizing (minimizing or maximizing) a function f(x) subject to x ∈ X, where f(x) may be linear or nonlinear, and the set X summarizes constraints on the vector of decision variables x. The constraints may include linear or nonlinear inequalities, and may compel all or some components of x to receive discrete values. While this representation is useful for discussing a number of problem solving considerations, we emphasize again that in many applications of combinatorial optimization, the problem of interest may not be easily formulated as an objective function subject to a set of constraints. The requirement x ∈ X, for example, may specify logical conditions or interconnections that would be cumbersome to formulate mathematically, but may be better be left as verbal stipulations that can be then coded as rules.

We began the discussion of short term memory for tabu search in Chapter 2 by contrasting the TS designs with those of memoryless strategies such as simple or iterated descent, and by pointing out how candidate list strategies are especially important for applying TS in the most effective ways. We have deferred the discussion of such strategies in order to provide an understanding of some of the basic roles played by memory, and to illustrate the aggressive nature of decision criteria that typically are used to reinforce these roles. In this chapter we begin by describing types of candidate list strategies that often prove valuable in tabu search implementations. Then we examine the issues of logical restructuring, which provide important bridges to longer term considerations. Finally, we describe additional short term memory structures that build on the ideas used to apply TS memory to add/drop moves. We show how these ideas can be conveniently adapted to provide related structures for many different kinds of optimization problems, and associated neighborhoods for defining moves for these problems. These structures likewise provide a basis for incorporating longer term considerations.

In some applications, the short term TS memory components are sufficient to produce very high quality solutions. However, in general, TS becomes significantly stronger by including longer term memory and its associated strategies. In the longer term TS strategies, the modified neighborhood produced by tabu search may contain solutions not in the original one, 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 intensification strategies, and as elements of different clusters in 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.

This chapter describes concepts and issues that are important for an effective application of the TS methodology and that merit fuller investigation. We begin by re-examining the notion of influence, followed by considering the generation of compound moves. We also expand the description of the proximate optimality principle and introduce a series of additional principles that are relevant for designing better solution procedures

We have already observed that tabu search can be used to modify decision rules for basis exchange (pivoting) methods, and therefore can be applied to solving mixed zero-one integer programming problems and various nonlinear programming problems by this means. Such applications exploit the fact that optimal solutions to these special zero-one discrete and nonlinear problems can be found at extreme points, and that pivoting methods provide a mechanism to move from one extreme point to another. In addition, however, tabu search can also be applied to solve integer and nonlinear programming problems in other ways. In this section we focus on integer programming (IP) problems, including mixed integer programming (MIP) problems where some variables can take on continuous values, as well as pure IP problems, where all variables must receive integer values.

In this chapter we begin by discussing probabilistic tabu search and the associated approach called tabu thresholding, which operates by reduced reliance on memory. Then we examine specialized memory mechanisms that have been used to enhance the performance of TS methods. We also discuss of approaches not yet widely considered. Finally, we examine basic strategies embodied in ejection chains, vocabulary building and parallel processing.

This chapter provides a collection of “vignettes” that briefly summarize applications of tabu search in a variety of settings. These vignettes are edited versions of reports by researchers and practitioners who are responsible for the applications The TS research summarized in this chapter was contributed by academicians and practitioners from all over the world. A debt of gratitude is owed to the individuals whose contributions have made this summary possible. (Deficiencies in describing their work are solely due to the current editing, and should not be interpreted to reflect shortcomings of the original reports.) In a number of cases, the work cited presents only a small sampling of significant contributions by the authors referenced.

Relationships between tabu search and other procedures like simulated annealing and genetic algorithms provide a basis for understanding similarities and contrasts in their philosophies, and for creating potentially useful hybrid combinations of these approaches. We offer some speculation on preferable directions in this regard, and also suggest how elements of tabu search can add a useful dimension to neural network approaches.

This chapter briefly reviews several key strategies in tabu search that are often neglected (especially in beginning studies), but which are important for producing the best results.