Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 400 papers for “parallel tabu search”

Parallel tabu search versus parallel evolution strategies

Ivanoe De Falco, R. Del Balio, Ernesto Tarantino et al. · 2002

There exists in scientific, industrial and financial communities a very strong request for techniques able to efficiently solve complex optimization problems. Because of this, several techniques are being currently investigated. Among them evolutionary algorithms and tabu search seem very interesting, not only for their intrinsic features but also because they both are easily parallelizable, so that they can take advantage of the parallel machines available on the market. A new parallel approach to tabu search (PTS) is introduced and compared against parallel evolution strategies on classical optimization problems taken from literature. The experimental results have shown the superiority of the PTS in both the solution quality and the convergence time.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 3

Parallel skeletons for Tabu search method

Blesa Aguilera, Maria Josep, Hernàndez, Lluis, Xhafa Xhafa, Fatos · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2000

In this paper we present two parallel skeltons for Tabu Search\n\t\t\t\t method --a well known meta-heuristic designed for finding\n\t\t\t\t approximate solution of combinatorial optimization problems.\n\t\t\t\t Our parallel skeletons are designed and implemented using the generic\n\t\t\t\t parallel programming paradigm. The first skeleton is based on\n\t\t\t\t independent runs while the second in the classical master-slave\n\t\t\t\t model. Our starting point is the design and implementation\n\t\t\t\t of a sequential skeleton that is used later as basis for\n\t\t\t\t the two parallel skeletons. Both skeletons provide the user with the\n\t\t\t\t followings: (a) permit to obtain parallel implementations of tabu\n\t\t\t\t search method for concrete combinatorial optimization problems from\n\t\t\t\t existing sequential implementations; (b) there is no need for the user\n\t\t\t\t to know neither parallel programming nor communication libraries;\n\t\t\t\t (c) the parallel implementation for\n\t\t\t\t a concrete problem is obtained automatically from a sequential\n\t\t\t\t implementation of the problem. The skeletons, however, require\n\t\t\t\t from the user a sequential instantiation of tabu search method for the\n\t\t\t\t problem at hand. The\n\t\t\t\t skeletons are implemented in C++ using MPI as a communication library\n\t\t\t\t and offer several properties such as a genericity, flexibility,\n\t\t\t\t component reuse, robustness and time savings, mainly due to the\n\t\t\t\t generic programming and object oriented programming paradigms. We have\n\t\t\t\t instantiated the two skeletons for the 0-1 Multidimensional Knapsack\n\t\t\t\t problem\n\t\t\t\t and have observed the claimed properties of the skeletons

Cited by 0Open access

Parallel skeletons for tabu search method

María J. Blesa, Lluis Hernàndez, Fatos Xhafa · QRU Quaderns de Recerca en Urbanisme · 2002

We present two generic parallel skeletons for the tabu search method-a well known meta-heuristic for approximately solving combinatorial optimization problems. The first skeleton is based on independent runs while the second in the classical master-slave model. Our starting point is the design and implementation of a sequential skeleton that is used later as basis for the two parallel skeletons. Both skeletons provide the user with the following: a permit to obtain parallel implementations of the tabu search method for concrete combinatorial optimization problems from existing sequential implementations; there is no need for the user to know either parallel programming or communication libraries; and the parallel implementation of tabu search for a concrete problem is obtained automatically from a sequential implementation of tabu search for the problem. The skeletons, however, require from the user a sequential instantiation of the tabu search method for the problem at hand. The skeletons are implemented in C++ using MPI as the communication library and offer genericity, flexibility, component reuse, robustness and time savings. We have instantiated the two skeletons for the 0-1 multidimensional knapsack problem, among others, for which we report computational results.

Cited by 10Open access

Generic parallel implementations for Tabu Search

Blesa Aguilera, Maria Josep, Petit Silvestre, Jordi, Xhafa Xhafa, Fatos · RECERCAT (Consorci de Serveis Universitaris de Catalunya) · 2005

Tabu Search (TS) is a meta-heuristic for solving combinatorial optimization problems. A review of existing implementations for TS reveals that, on the one hand, these implementations are ad hoc and, on the other hand, most of them run in a sequential setting. Indeed, the reported parallel implementations are few as compared to the sequential implementations. Due to increase in computing resources, especially in LAN environments, it is quite desirable to obtain parallel implementations of TS for solving problems arising in fields others than computer science, such as biology, control theory, etc., in which researchers and practitioners are less familiar with parallel programming. In this work we present a generic implementation of TS able to be run in sequential and parallel settings. The key point in our approach is the design and implementation in C++ of an algorithmic skeleton for TS embedding its main flow as well as several parallel implementations for the method. This is achieved through a separation of concerns: elements related to TS are provided by the skeleton, whereas the problem-dependent elements are expected to be provided by the user according to a fixed interface using purely sequential constructs. Thus, the skeleton has a unique interface but is expected to have many instantiations for concrete problems, all of them being able to run in a straightforward way using different parallel implementations. In order to assess the effectiveness of our approach, we have applied it to several NP-hard combinatorial optimization problems. We have considered developing time, flexibility and easiness of use, quality of solutions and computation efficiency. We have observed that our approach allows fast developing of problem instantiations. Moreover, the skeleton allows the user to configure and implement in different ways internal methods related to TS. Furthermore, the results obtained by our generic parallel implementations are efficient and report good quality results compared to the ones reported by ad hoc implementations. We exemplify our approach through the application to the 0-1 Multidimensional Knapsack problem. The experimental results obtained for standard benchmarks of this problem show that, in spite of the genericity and flexibility of our implementation, the resulting program provides high quality solutions very close to the optimal ones.

Cited by 0Open access

Parallel Tabu Search for Irregular Cutting

Jacek Błażewicz, Janusz Kaczmarek, R. Walkowiak · 1994

The problem of cutting figures of various shapes out from the rectangular area is considered. The paper is devoted to the development of the earlier versions of the original method presented in [2,3]. A new approach is different from the previous one in the following points:

Cited by 0

HPTS: heterogeneous parallel tabu search for VLSI placement

A.A. Al-Yamani, Sadiq M. Sait, Hassan Barada · 2003

Parallelizing any algorithm on a cluster of heterogeneous workstations is not easy, as each workstation requires different wall clock time to execute the same instruction set. In this work, a parallel tabu search algorithm for heterogeneous workstations is presented using PVM. Two parallelization strategies, i.e., functional decomposition and multi-search thread strategies are integrated. The proposed algorithm is tested on the VLSI standard cell placement problem, however, the same algorithm can be used on any combinatorial optimization problem. The results are compared ignoring heterogeneity and are found to be superior in terms of execution time.

Cited by 5

Towards a Taxonomy of Parallel Tabu Search Heuristics

Teodor Gabriel Crainic, Michel Toulouse, Michel Gendreau · 1995

In this paper we present a classification of parallel tabu search metaheuristics based, on the one hand, on the control and communication strategies used in the design of the parallel tabu search procedures and, on the other hand, on how the search space is partitionned. These criteria are then used to review the parallel tabu search implementations described in the literature. The taxonomy is further illustrated by the results of several parallelization implementations of a tabu search procedure for multicommodity location-allocation problems with balancing requirements. Key words: Tabu search metaheuristics, Parallelization strategies, Taxonomy R&amp;apos;esum&amp;apos;e Nous pr&amp;apos;esentons un sch&amp;apos;ema de classification des algorithmes parall`eles de recherche avec tabous. La taxonomie est bas&amp;apos;ee, d&amp;apos;une part, sur les strat&amp;apos;egies de controle et de communication des algorithmes parall`eles de recherche avec tabous et, d&amp;apos;autre part, sur les r`egles de partitionnement du domaine. Ces crit`eres sont ensuite ut...

Cited by 0

Parallel Adaptive Tabu Search for Large Optimization Problems

E. G. Talbi, Z. Hafidi, J-M. Geib · 1997

This paper presents a new approach for parallel tabu search based on adaptive parallelism. Adaptive parallelism demonstrates that massively parallel computing using a hundred of heterogeneous machines is feasible to solve large optimization problems. The parallel tabu search algorithm includes different tabu list sizes and new intensification/diversification mechanisms. Encouraging results have been obtained in solving the quadratic assignment problem. We have improved the best known solutions for some large real-world problems. 1 Motivation and goals Many interesting combinatorial optimization problems are NP-hard, and then they cannot be solved exactly within a reasonable amount of time. Consequently, heuristics must be used to solve real-world problems. Tabu search (TS) is a general purpose heuristic (meta-heuristic) that has been proposed by Glover [1]. TS has achieved widespread successes in solving practical optimization problems in different domains (resource management, proces...

Cited by 0

Parallel Heuristic Search - New Approaches to Parallel Simulated Annealing and Tabu Search (Extended Abstract)

Per S. Laursen · 2007

) Per S. Laursen Department of Computer Science University of Copenhagen Universitetsparken 1 2100 Copenhagen , Denmark e-mail: svalle@diku.dk 1 Introduction A large number of combinatorial optimization problems can presently only be solved to proven optimality if they are of very moderate size. This fact motivates the interest in approximation algorithms and heuristics. The former class of algorithms are able to guarantee the quality of the produced (suboptimal) solutions within certain bounds, while heuristics usually only have empirical evidence of their problem solving abilities. Many of these heuristics are tailored to a specific problem type. There exists however a small family of more generally applicable heuristics (metaheuristics), which with a little effort can be turned into a heuristic for a variety of problems. Belonging to this family are Simulated Annealing [3] and Tabu Search [3]. Even though heuristics offer the ability to find good solutions in moderate time,...

Cited by 0

Two-stage Tabu Search for Solving Parallel Machine Problems

Yuedong Xu, Yajie Tian, Nobuo Sannomiya · Transactions of the Society of Instrument and Control Engineers · 2002

Two-stage tabu search is proposed to solve parallel machine problems. At the first stage the candidate list is employed and the jobs assigned to each machine are ordered by NEH. At the second stage the best solution obtained at the first stage is improved by enlarging its neighborhood.

Cited by 3Open access

A Parallel Tabu Search Algorithm Based on Partitioning Principle

For Tsps, Yi He, Guangyuan Liu et al. · 2006

We presented a parallel tabu search (PTS) algorithm for the traveling salesman problem (TSP), which is NP-hard. To parallelize tabu search (TS) algorithm efficiently, the search space decomposition based on partition principle was used to balance the computing load, while exploitation in subspace had been boosted by an adaptive search strategy of intensification and diversification. Numerical results illustrated this algorithm was efficient and easy to implement. Key words: Parallel Tabu Search, Meta-heuristic, TSP

Cited by 0

Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching

Michel Gendreau, François Guertin, Jean‐Yves Potvin et al. · Transportation Science · 1999

An abundant literature about vehicle routing and scheduling problems is available in the scientific community. However, a large fraction of this work deals with static problems where all data are known before the routes are constructed. Recent technological advances now create environments where decisions are taken quickly, using new or updated information about the current routing situation. This paper describes such a dynamic problem, motivated from courier service applications, where customer requests with soft time windows must be dispatched in real time to a fleet of vehicles in movement. A tabu search heuristic, initially designed for the static version of the problem, has been adapted to the dynamic case and implemented on a parallel platform to increase the computational effort. Numerical results are reported using different request arrival rates, and comparisons are established with other heuristic methods.

Cited by 446

A Parallel Tabu Search Alglorithm for the Quadratic Assignment Problem

Samuel Gabrielsson · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2008

A parallel version of the tabu search algorithm is implemented and used to optimize the solutions for a quadratic assignment problem (QAP). The instances are taken from the qaplib website 1 and we mainly concentrate on solving and optimizing the instances announced by Sergio Carvalho derived from the “Microarray Placement Problem ” 2 where one wants to find an arrangement of the probes (small DNA fragments) on specific locations of a microarray chip. We briefly explain combinatorics including graph theory and also the theory behind combinatorial optimization, heuristics and metaheuristcs. A description of some network optimization problems are also introduced before we apply our parallel tabu search algorithm to the quadratic assignment problem. Different approaches like Boltzmann selection procedure and random restarts are used to optimize the solutions. Through our experiments, we show that our parallel version of tabu Search do indeed manage to further optimize and even find better solutions found so far in the litterature. We try out a communication protocol based on sequentially generating graphs, where each node in the graph corresponds to a CPU or tabu search thread. One of the main goals is to find out if communication helps to further optimize the best known solution found so far for each instace.

Cited by 2Open access