Skip to main content
main-content

1997 | Buch

Tabu Search

verfasst von: Fred Glover, Manuel Laguna

Verlag: Springer US

share
TEILEN
insite
SUCHEN

Über dieses Buch

Faced with the challenge of solving hard optimization problems that abound in the real world, classical methods often encounter great difficulty - even when equipped with a theoretical guarantee of finding an optimal solution. Vitally important applications in business, engineering, economics and science cannot be tackled with any reasonable hope of success, within practical time horizons, by solution methods that have been the predominant focus of academic research throughout the past three decades (and which are still the focus of many textbooks). The impact of technology and the advent of the computer age have presented us with the need (and opportunity) to solve a range of problems that could scarcely have been envisioned in the past. Weare confronted with applications that span the realms of resource planning, telecommunications, VLSI design, fmancial analysis, scheduling, space planning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management, mineral exploration, biomedical analysis, environmental conservation and scores of others.

Inhaltsverzeichnis

Frontmatter
1. Tabu Search Background
Abstract
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.
Fred Glover, Manuel Laguna
2. Tabu Search Foundations: Short Term Memory
Abstract
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 xX, 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 xX, 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.
Fred Glover, Manuel Laguna
3. Tabu Search Foundations: Additional Aspects of Short Term Memory
Abstract
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.
Fred Glover, Manuel Laguna
4. Tabu Search Foundations: Longer Term Memory
Abstract
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.
Fred Glover, Manuel Laguna
5. Tabu Search Principles
Abstract
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
Fred Glover, Manuel Laguna
6. Tabu Search in Integer Programming
Abstract
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.
Fred Glover, Manuel Laguna
7. Special Tabu Search Topics
Abstract
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.
Fred Glover, Manuel Laguna
8. Tabu Search Applications
Abstract
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.
Fred Glover, Manuel Laguna
9. Connections, Hybrid Approaches and Learning
Abstract
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.
Fred Glover, Manuel Laguna
10. Neglected Tabu Search Strategies
Abstract
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.
Fred Glover, Manuel Laguna
Backmatter
Metadaten
Titel
Tabu Search
verfasst von
Fred Glover
Manuel Laguna
Copyright-Jahr
1997
Verlag
Springer US
Electronic ISBN
978-1-4615-6089-0
Print ISBN
978-0-7923-8187-7
DOI
https://doi.org/10.1007/978-1-4615-6089-0