Catálogo de publicaciones - libros

This paper introduces tabu search for the solution of general linear integer problems. Search is done on integer variables; if there are continuous variables, their corresponding value is determined through the solution of a linear program, which is also used to evaluate the integer solution. The complete tabu search procedure includes an intensification and diversification procedure, whose effects are analysed on a set of benchmark problems.

The purpose of this work is to compare the performance of a scatter search (SS) implementation and an implementation of a genetic algorithm (GA) in the context of searching for optimal solutions to permutation problems. Scatter search and genetic algorithms are members of the evolutionary computation family. That is, they are both based on maintaining a population of solutions for the purpose of generating new trial solutions. Our computational experiments with four well-known permutation problems reveal that in general a GA with local search outperforms one without it. Using the same problem instances, we observed that our specific scatter search implementation found solutions of a higher average quality earlier during the search than the GA variants.

We present strategies to design parallel tabu search algorithms and survey developments and results in the area. In the second part of the paper, we focus on multi-search strategies. We discuss general design and implementation principles, point out a number of challenges and pitfalls, and identify trends and promising research directions.

Over the past four years, a Consortium composed of The University of Texas at Austin, the Air Force Institute of Technology and the US Air Force Air Mobility Command has been remarkably successful in developing the theoretical foundations of group theoretic tabu search (GTTS) and applying it to a set of complex military logistics problems. This paper briefly recounts some of those accomplishments and describes the underlying mathematical framework that supported them. The symmetric group on n letters, S_n can be used to build and solve equations whose coefficients and variables are permutations, i.e., elements of S_n. These equations efficiently describe search neighborhoods for combinatorial optimization problems (COPs) whose solutions can be modeled as partitions, orderings, or both (P|O problems). Following the introduction, the second section describes neighborhoods that preserve a cycle solution structure and recounts examples of how group theory has been used to provide new and useful insights into search neighborhoods. The third section describes neighborhoods for multiple cyclic solution structures. Section 4 considers a hybrid move neighborhood that borrows from Sections 2 and 3. The fifth section overviews some highly successful applications of the GTTS approach. The final section contains concluding remarks and offers suggestions for future work. The paper's goals are: (1) to illustrate that move neighborhoods can be cast into a group theoretic context and that new powerful neighborhoods can be easily “hand tailored” using group theory; and (2) to motivate others to consider how the unifying mathematical framework of group theory could be further exploited to gain powerful new understandings of direct search move neighborhoods.

In today's highly competitive global marketplace, the pressure on organizations to find new ways to create value and deliver it to their customers grows ever stronger. In the last two decades, the logistics function has moved to center stage. There has been a growing recognition that effective logistics management throughout the firm and supply chain can greatly assist in the goal of cost reduction and service enhancement. The keys to success in Logistics Management (LM) require heavy emphasis on integration of activities, cooperation, coordination and information sharing throughout the firm and the entire supply chain, from suppliers to customers. To be able to respond to the challenge of integration, modem businesses need sophisticated decision support systems based on powerful mathematical models and solution techniques, together with advances in information and communication technologies. Both industry and academia alike have become increasingly interested in using LM as a means of responding to the problems and issues posed by changes in the logistics function. This paper presents a brief discussion on the important issues in LM and argues that metaheuristics can play an important role in solving complex logistics problems derived from designing and managing logistics activities within the supply chain as a single entity. Among several possible metaheuristic approaches, we will focus particularly on Iterated Local Search, Tabu Search and Scatter Search as the methods with the greatest potential for solving LM related problems. We also briefly present some successful applications of these methods.

In a recent paper, Focacci, Laburthe and Lodi (2002) surveyed the integration between Local Search and Constraint Programming which seems to be suitable to address real-world combinatorial optimization problems. In this paper, we focus on the integration of the machinery developed in the Tabu Search context into incomplete global search algorithms based on CP. The main issue is to reinterpret the techniques developed within Tabu Search for complete solutions so as to apply them to internal nodes of a tree search, i.e., to partial solutions.

When using optimization in the context of a decision support system, a decision maker would often be more interested in seeing a diverse collection of good solutions rather than the one solution that is in some mathematical sense the optimal solution to an approximate problem with imprecise data. A recent paper (Glover, Løkketagen and Woodruff, 2000) describes a method for generating diverse solutions using scatter search. However, very little research has been done on general purpose methods to characterize solution variety. This paper describes and explains desirable characteristics for general purpose methods for characterizing diversity. Field research serves to demonstrate and compare various methods. We provide some fundamental research concerning methods that are fully general and do not rely on any knowledge of the problem.

Recent metaheuristic developments have proved to be successful especially in cases where their fundamental concepts are complemented with pool-oriented approaches such as scatter search. These algorithms maintain a reference set of high quality solutions which are repeatedly used during the search in order to guarantee a fruitful balance between diversification and intensification. However, maintaining such a pool is not a trivial undertaking. The main problem is to find a balance between the attempt to collect a number of high quality solutions, which often results in similar solution properties, and the need to guarantee a certain degree of diversity in the pool. In the present study we highlight the advantage of pool-oriented design while focusing on controlled input and output operations. We analyze the main pool components for metaheuristics and present a review of the literature on relevant strategies in tabu search, scatter search, and path relinking. Additionally, we provide a synthesis of the literature that highlights the critical aspects of effective pool maintenance.

Projection methods, which hold selected variables fixed while manipulating others, have a particularly useful role in metaheuristic procedures, especially in connection with large scale optimization and parallelization approaches. This role is enriched by adaptive memory processes of tabu search, which provide a collection of easily stated strategies to uncover improved solutions during the course of the search. Within the context of pure and mixed integer programming, we show that intensification and diversification processes for adaptive memory projection can be supported in several ways, including the introduction of pseudo-cut inequalities that additionally focus the search. We describe how the resulting procedures can be embedded in constructive multistart methods as well as in progressive improvement methods, and how they can benefit by the application of target analysis.

We propose a new metaheuristic framework embodied in two approaches, Relaxation Adaptive Memory Programming (RAMP) and its primal-dual extension (PD-RAMP). The RAMP method, at the first level, operates by combining fundamental principles of mathematical relaxation with those of adaptive memory programming, as expressed in tabu search. The extended PD- RAMP method, at the second level, integrates the RAMP approach with other more advanced strategies. We identify specific combinations of such strategies at both levels, based on Lagrangean and surrogate constraint relaxation on the dual side and on scatter search and path relinking on the primal side, in each instance joined with appropriate guidance from adaptive memory processes. The framework invites the use of alternative procedures for both its primal and dual components, including other forms of relaxations and evolutionary approaches such as genetic algorithms and other procedures based on metaphors of nature.