Jaziri W. (ed.) Local Search Techniques. Focus on Tabu Search

InTech, 2008, -294 p.
Digest of articlesIn real-world optimization applications, stakeholders require multiple and complex constraints, which are difficult to satisfy and make complicated to find satisfactory solutions. In the most cases, we face over-constrained optimization problems (no satisfactory solution can be found) because of the stakeholders’ multiple requirements and the various and complex constraints to be satisfied. Solving over-constrained problems is based on the relaxation of some constraints according to values of preferences in order to favour the satisfaction of the most relevant. In addition, some methods have been developed, such as Branch and Bound method and Filtering techniques, which allow avoiding an enumeration of all potential solutions but are very expensive in computation times.
Two types of actors are involved in the optimization problems: the stakeholders who express their needs and the analyst who models and manages these needs. The choice of appropriate resolution methods depends on the stakeholders’ needs and the number of criterion to take into account. The definition and the formulation of stakeholders needs are among the major preoccupations to resolve an optimization problem. The quality of a solution depends on the efficiency of this step, which must model all aspects of the problem, in particular those related to the objectives of the application. However, in majority of optimization works, the interest concerns the choice and the development of appropriate optimization approaches rather than the modeling of the stakeholders’ needs.
An optimisation approach consists in exploring the search space to find the best solution according to an objective function and satisfying some constraints. It expresses a value of cost to reduce or of benefit to maximize. The optimization framework is adapted to the problems with multiple solutions. In traditional optimization problems, the objective function comprises a single criterion able to determine the optimum. Otherwise, the objective consists in finding a good compromise regarding multiple criteria.
The problem is then a case of multicriteria optimization. In practice, optimization problems can reach a high complexity and require considerable computation times because of the number of potential solutions. The approximate methods are generally used to resolve this class of problems. These methods are based on an iterative exploration of the search space to find a solution of good quality in reasonable computation times. Among the most known approximate methods, we mention the neighbourhood methods, such as Local Search, Simulated Annealing, Threshold Algorithms, Noising Method and Tabu Search as well as the algorithms based on the evolution approach, such as Evolutionary Programming, Strategies of Evolution, Genetic Algorithms and Genetic Programming.
In the last decade, optimization problems have been among the most studied problems and they are still an active area of research. Algorithmic advances as well as the needs to solve complex real-world optimization problems have provided an excellent framework on which to develop and design new optimization techniques. The field of Neighborhood search methods has grown considerably. Researchers have demonstrated the ability of these methods to solve hard combinatorial problems within reasonable computation times. Neighborhood search methods are iterative procedures, which consist in constructing from a current solution a next solution with a better quality regarding an objective function. Among the Neighborhood search methods, Tabu Search is one of the most prominent, widely used, and successful approaches for solving optimization problems from artificial intelligence and operations research. Tabu Search is a meta-heuristic algorithm, which can be used for solving combinatorial optimization problems. Tabu Search has found its usefulness in a vast area of applications such as scheduling, vehicle routing problems, resources planning, regional development, location problems, integer programming problems, traveling salesman, graph coloring, knapsack problems, network design etc. Tabu Search has now become a reputable optimization technique and has proved highly effective in solving a wide range of optimization problems. Several works presenting applications of Tabu Search to various combinatorial problems have proved that Tabu Search provides good solutions very close to optimality. These successes have made Tabu Search extremely popular among those interested in finding good solutions to the large combinatorial problems encountered in many practical settings.
Tabu Search uses a local search procedure to iteratively move from a current solution x to a neighbor solution x' in the neighborhood of x, until some stopping criterion has been satisfied. The search process starts with an initial solution and moves from neighbor to neighbor as long as possible while improving the objective function value. Tabu Search improves the performance of the search process by using memory structures: the last explored configurations are kept in a short-term memory (Tabu list) in order to prohibit moves that lead to one of them.
Overall objective of the book
The goal of this book is to report original researches on algorithms and applications of Tabu Search to real-world problems as well as recent improvements and extensions on its concepts and algorithms. The book’ Chapters identify useful new implementations and ways to integrate and apply the principles of Tabu Search, to hybrid it with others optimization methods, to prove new theoretical results, and to describe the successful application of optimization methods to real world problems. Chapters were selected after a careful review process by reviewers, based on the originality, relevance and their contribution to local search techniques and more precisely to Tabu Search.AudienceThe book Local Search Techniques: Focus on Tabu Search provides a broad spectrum of advances in applied optimization with a focus on Tabu Search. It is designed to be useful and accessible to researchers, engineers, graduate students and all scientists and practitioners in computer science, operations research and artificial intelligence as well as other applications specialists who need local search techniques to model and solve combinatorial optimization problems.