Least-cost network topology design for a new service

We describe an implementation of the tabu search metaheuristic that effectively finds a low-cost topology for a communications network to provide a centralized new service. Our results are compared to those of a greedy algorithm which applies corresponding decision rules, but without the guidance of the tabu search framework. These problems are difficult computationally, representing integer programs that can involve as many as 10,000 integer variables and 2000 constraints in practical applications. The tabu search results approach succeeded in obtaining significant improvements over the greedy approach, yielding optimal solutions to problems small enough to allow independent verification of optimality status and, more generally, yielding both absolute and percentage cost improvements that did not deteriorate with increasing problem size.This research was partially supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract No. F49629-90-C-0033.     

A user's guide to tabu search

We describe the main features of tabu search, emphasizing a perspective for guiding a user to understand basic implementation principles for solving combinatorial or nonlinear problems. We also identify recent developments and extensions that have contributed to increasing the efficiency of the method. One of the useful aspects of tabu search is the ability to adapt a rudimentary prototype implementation to encompass additional model elements, such as new types of constraints and objective functions. Similarly, the method itself can be evolved to varying levels of sophistication. We provide several examples of discrete optimization problems to illustrate the strategic concerns of tabu search, and to show how they may be exploited in various contexts. Our presentation is motivated by the emergence of an extensive literature of computational results, which demonstrates that a well-tuned implementation makes it possible to obtain solutions of high quality for difficult problems, yielding outcomes in some settings that have not been matched by other known techniques.The research of this paper has been supported in part by the joint Air Force Office of Scientific Research and Office of Naval Research Contract No. F49620-90-C-0033, at the University of Colorado and by the Swiss National Research Council Grant No. 20-27926.89.     

Integrating and accelerating tabu search,simulated annealing,and genetic algorithms

We integrate tabu search, simulated annealing, genetic algorithms, and random restarting. In addition, while simulating the original Markov chain (defined on a state space tailored either to stand-alone simulated annealing or to the hybrid scheme) with the original cooling schedule implicitly, we speed up both stand-alone simulated annealing and the combination by a factor going to infinity as the number of transitions generated goes to infinity. Beyond this, speedup nearly linear in the number of independent parallel processors often can be expected.This research was (partially) supported by the Air Force Office of Scientific Research and the Office of Naval Research Contract #F49620-90-C-0033.     

Iterated tabu search for the car sequencing problem

This paper introduces an iterated tabu search heuristic for the daily car sequencing problem in which a set of cars must be sequenced so as to satisfy requirements from the paint shop and the assembly line. The iterated tabu search heuristic combines a classical tabu search with perturbation operators that help escape from local optima. The resulting heuristic is flexible, easy to implement, and fast. It has produced very good results on a set of test instances provided by the French car manufacturer Renault.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.     

Design and Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling

Using a simple multiprocessor scheduling problem as a vehicle, we explore the behavior of tabu search algorithms using different tabu, local search and list management strategies. We found that random blocking of the tail of the tabu list always improved performance; but that the use of frequency-based penalties to discourage frequently selected moves did not. Hash coding without conflict resolution was an effective way to represent solutions on the tabu list. We also found that the most effective length of the tabu list depended on features of the algorithm being used, but not on the size and complexity of the problem being solved. The best combination of features included random blocking of the tabu list, tasks as tabus and a greedy local search. An algorithm using these features was found to outperform a recently published algorithm solving a similar problem.     

一种改进的禁忌搜索算法及其在选址问题中的应用

本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较.通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性.     

Multistart Tabu Search Strategies for the Unconstrained Binary Quadratic Optimization Problem

This paper describes and experimentally compares five rather different multistart tabu search strategies for the unconstrained binary quadratic optimization problem: a random restart procedure, an application of a deterministic heuristic to specially constructed subproblems, an application of a randomized procedure to the full problem, a constructive procedure using tabu search adaptive memory, and an approach based on solving perturbed problems. In the solution improvement phase a modification of a standard tabu search implementation is used. A computational trick applied to this modification – mapping of the current solution to the zero vector – allowed to significantly reduce the time complexity of the search. Computational results are provided for the 25 largest problem instances from the OR-Library and, in addition, for the 18 randomly generated larger and more dense problems. For 9 instances from the OR-Library new best solutions were found.     

An Application of Tabu Search Heuristic for the Maximum Edge-Weighted Subgraph Problem

The purpose of this article is to describe an efficient search heuristic for the Maximum Edge-weighted Subgraph (MEwS) problem. This problem requires to find a subgraph such that the sum of the weights associated with the edges of the subgraph is maximized subject to a cardinality constraint. In this study a tabu search heuristic for the MEwS problem is proposed. Different algorithms to obtain an initial solution are presented. One neighborhood search strategy is also proposed. Preliminary computational results are reported for randomly generated test problems of MEwS problem with different densities and sizes. For most of test problems, the tabu search heuristic found good solutions. In addition, for large size test problems, the tabu search outperformed the local search heuristic appearing in the literature.     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods

The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper, we present two tabu search implementations, one involving an exhaustive search of the 2-opt neighborhood and the other involving an exhaustive search of the insertion neighborhood. We also present techniques to significantly speed up the search of the two neighborhoods. Our computational experiments show that the speed up techniques are effective, and our tabu search implementations are competitive. Our tabu search implementations improved previously known best solutions for 23 out of the 43 large sized SRFLP benchmark instances.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Tabu search applied to the general fixed charge problem

Recent successes in applying tabu search to a wide variety of classical optimization problems have motivated the investigation of applying tabu search to the well-known general fixed charge problem (GFCP). In this paper, an adaptation of tabu search to GFCP is described and computational results are given. In addition, the computational results are compared with those obtained from SWIFT-2, the most well-known and frequently used heuristic method for GFCP. As will be shown, the results are very encouraging.     

Applying tabu search to the job-shop scheduling problem

In this paper, we apply the tabu-search technique to the job-shop scheduling problem, a notoriously difficult problem in combinatorial optimization. We show that our implementation of this method dominates both a previous approach with tabu search and the other heuristics based on iterative improvements.Partially supported by research contracts MPI 40% and 60% of the Italian Ministry of University and Scientific Research.     

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

Massively parallel analog tabu search using neural networks applied to simple plant location problems

Neural networks and tabu search are two very significant techniques which have emerged recently for the solution of discrete optimization problems. Neural networks possess the desirable quality of implementability in massively parallel hardware while the tabu search metaheuristic shows great promise as a powerful global search method. Tabu Neural Network (TANN) integrates an analog version of the short term memory component of tabu search with neural networks to generate a massively parallel, analog global search strategy that is hardware implementable. In TANN, both the choice of the element to enter the tabu list as well as the maintenance of the decision elements in tabu status is accomplished via neuronal activities. In this paper we apply TANN to the simple plant location problem. Comparisons with the Hopfield-Tank network show an average improvement of about 85% in the quality of solutions obtained.     

A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test problems, size permitting.This research was partially supported by the C.I.C.Y.T. with code tap92-0639.     

Evaluating the performance of tabu search procedures for flow shop sequencing

We address the problem of minimising makespan in a flow shop by using tabu search procedures. By combining different neighbourhood structures, neighbourhood examinations, and stopping conditions we obtain alternative tabu search procedures. Starting from a common initial solution we evaluate the relative performance of such procedures considering both the solution quality and computational effort.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

On the convergence of Newton iterations to non-stationary points

We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, the interaction between the Newton direction and the merit function can prevent the iterates from escaping such non-stationary points. The unconstrained minimization problem is also studied, and conditions under which false convergence cannot occur are presented. Several examples illustrating failure of Newton iterations for constrained optimization are also presented. The paper also shows that a class of line search feasible interior methods cannot exhibit convergence to non-stationary points. This author was supported by Air Force Office of Scientific Research grant F49620-00-1-0162, Army Research Office Grant DAAG55-98-1-0176, and National Science Foundation grant INT-9726199.This author was supported by Department of Energy grant DE-FG02-87ER25047-A004.This author was supported by National Science Foundation grant CCR-9987818 and Department of Energy grant DE-FG02-87ER25047-A004.