Catálogo de publicaciones - libros

Scatter search is an evolutionary method that has proved highly effective in solving several classes of non-linear and combinatorial optimization problems. Proposed early 1970s as a primal counterpart to the dual surrogate constraint relaxation methods, scatter search has recently found a variety of applications in a metaheuristic context. Because both surrogate constraint methods and scatter search incorporate strategic principles that are shared with certain components of tabu search methods, scatter search provides a natural evolutionary framework for adaptive memory programming. The aim of this paper is to illustrate how scatter search can be effectively used for the solution of general permutation problems that involve the determination of optimal cycles (or circuits) in graph theory and combinatorial optimization. In evidence of the value of this method in solving constrained optimization problems, we identify a general design for solving vehicle routing problems that sets our approach apart from other evolutionary algorithms that have been proposed for various classes of this problem.

The algorithm described here, called OptQuest/NLP or OQNLP, is a heuristic designed to find global optima for pure and mixed integer nonlinear problems with many constraints and variables, where all problem functions are differentiable with respect to the continuous variables. It uses OptQuest, a commercial implementation of scatter search developed by OptTek Systems, Inc., to provide starting points for a gradient-based local NLP solver. This solver seeks a local solution from a subset of these points, holding discrete variables fixed. The procedure is motivated by our desire to combine the superior accuracy and feasibility-seeking behavior of gradient-based local NLP solvers with the global optimization abilities of OptQuest. Computational results include 144 smooth NLP and MINLP problems due to Floudas et al, most with both linear and nonlinear constraints, coded in the GAMS modeling language. Some are quite large for global optimization, with over 100 variables and many constraints. Global solutions to almost all problems are found in a small number of NLP solver calls, often one or two.

The Covering Tour Problem (CTP) is a generalization of the Traveling Salesman Problem (TSP) which has several practical applications in the area of distribution network design. Given an undirected graph, the problem asks to identify a minimum cost cycle passing through a subset of vertices such that every vertex not in the cycle lies within a given distance from at least one node in the cycle. Being a generalization of the TSP, CTP is NP-hard. This paper presents three original Scatter Search heuristic algorithms for the CTP. Computational results are reported.

Synchronous Optical Network (SONET) in North America and Synchronous Digital Hierarchy (SDH) in Europe and Japan are the current transmission and multiplexing standards for high speed signals within the carrier infrastructure. The typical topology of a SONET network is a collection of rings connecting all the customer sites. We deal with a design problem in which each customer has to be assigned to exactly one ring and these rings have to be connected through a single federal ring. A capacity constraint on each ring is also imposed. The problem is to find a feasible assignment of the customers minimizing the total number of rings used. A Tabu Search method is proposed to solve the problem. The key elements are the use of a variable objective function and the strategic use of two neighborhoods. We have also implemented other techniques such as Path Relinking, eXploring Tabu Search and a Scatter Search. Extensive computational experiments have been done using two sets of benchmark instances. The performances of the proposed algorithms have also been compared with those of three multistart algorithms involving greedy methods previously proposed for the problem, and of the CPLEX solver. The computational experiments show the effectiveness of the proposed Tabu Search.

This paper deals with the classic job-shop scheduling problem with makespan criterion. Some new properties of the problem associated with blocks are presented and discussed. These properties allow us to propose a new, very fast local search procedure based on a tabu search approach. The central concepts are lower bounds for evaluations of the moves, and perturbations that guide the search to the more promising areas of solution space, where "good solutions" can be found. Computational experiments are given and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed solves the job-shop instances with high accuracy in a very short time. The presented properties and ideas can be applied in many local search procedures.

This article reviews some of the most important tabu search heuristics for the vehicle routing problem. Some of the main tabu search features are first described: neighbourhood structures, short term memory, long term memory, intensification. The tabu search algorithms are then described, followed by computational results and the conclusion.

This paper deals with a classic job-shop scheduling problem with the makespan criterion. Some properties of the fast algorithm TSAB of Nowicki and Smutnicki, as well as properties of the solution space, have been discussed and examined. Next, by introducing the original method of diversification, TSAB has been embedded in more advanced algorithmic framework i -TSAB, which has far analogy to path relinking technique. Newly proposed algorithm is faster and has better accuracy than TSAB, runs within time of minutes on a PC and already in preliminary tests provides 23 new upper bounds among 35 unsolved yet common Taillard's benchmarks.

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. The heuristic procedure uses tabu search to guide the solution process when evolving from one solution to another in order to search for an optimal solution. A move is defined to be the closing or opening of a facility. The net change in the total cost resulting from a move is used to measure the attractiveness of a move. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal solutions for test problems with known optimal solutions from the literature. Solutions obtained with this tabu search procedure completely dominate those obtained with the Lagrangian method for randomly generated test problems.

Satisfiability problems (SAT) are capable of representing many important real-world problems, like planning, scheduling, and robotic movement. Efficient encodings exist for many of these applications and thus having good solvers for these problems is of critical significance. We look at how adaptive memory and surrogate constraint processes can be used as search guidance for both constructive and local search heuristics for satisfiability problems, and how many well-known heuristics for SAT can be seen as special cases. We also discuss how adaptive memory learning processes can reduce the customary reliance on randomization for diversification so of ten seen in the literature. More specifically, we look at the tradeoff between the cost of maintaining extra memory search guidance structures and the potential benefit they have on the search. Computational results on a portfolio of satisfiability problems from SATLIB illustrating these tradeoffs are presented.

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s and were based on formulations, dating back to the 1960s, for combining decision rules and problem constraints. The method uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems. This paper presents a number of findings (lessons) from the application of scatter search to combinatorial optimization problems (e.g., production scheduling and the linear ordering problem) and nonlinear optimization problems (e.g., multi-modal functions and neural network training). We describe our findings and the context in which we have learned each lesson. We believe that some of our findings are not context specific and therefore may benefit future applications of scatter search.