A General Parallel TABU Search Algorithm For Combinatorial Optimisation Problems

Publication
Randall, M. and Abramson, D “A General Parallel TABU Search Algorithm for Combinatorial Optimisation Problems”, Proceedings of 1999 Parallel and Real Time Conference (PART-99), December 1999, Melbourne, pp 68 - 79.
Abstract
Tabu Search (TS) is a meta-heuristic search algorithm that is easy to parallise. Efficient parallelistion is of TS can represent a significant saving in the real-time required to solve a problem over an equivalent sequential algorithm. In this study, a general parallel TS algorithm for solving combinatorial optimisation problems (COPs) is presented. The unique feature of our approach is that the TS solves a wide range of COPs expressed in a high level syntax. The benefit of this general code is that it can be used in real0time applications due to its parallel scalability and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are presented that show a good parallel speedup is achieved while efficient solutions to hard COPs are obtained.
Download
gentabu.pdf