A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems

Marcus Randall, David Abramson

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

Tahu Search (TS) is a meta-heuristic search algorithm that is easy to parallelise. Efficient parallelisation 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 real-time applications due to its parallel scala­bility and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are pre­sented that show that good parallel speedup is achieved while efficient solutions to hard COPs are obtained.
Original languageEnglish
Title of host publicationPART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999
EditorsWilson C. H. Cheng, A. S. M. Sajeev
Place of PublicationSingapore
PublisherSpringer
Pages68-79
Number of pages12
ISBN (Print)9814021598
Publication statusPublished - 1999

Fingerprint

Tabu search
Combinatorial optimization
Scalability

Cite this

Randall, M., & Abramson, D. (1999). A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems. In W. C. H. Cheng, & A. S. M. Sajeev (Eds.), PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999 (pp. 68-79). Singapore: Springer.
Randall, Marcus ; Abramson, David. / A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems. PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999. editor / Wilson C. H. Cheng ; A. S. M. Sajeev. Singapore : Springer, 1999. pp. 68-79
@inproceedings{cf5e4ee717c1414fa04442784f3f5156,
title = "A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems",
abstract = "Tahu Search (TS) is a meta-heuristic search algorithm that is easy to parallelise. Efficient parallelisation 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 real-time applications due to its parallel scala­bility and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are pre­sented that show that good parallel speedup is achieved while efficient solutions to hard COPs are obtained.",
author = "Marcus Randall and David Abramson",
year = "1999",
language = "English",
isbn = "9814021598",
pages = "68--79",
editor = "Cheng, {Wilson C. H.} and Sajeev, {A. S. M.}",
booktitle = "PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999",
publisher = "Springer",
address = "Germany",

}

Randall, M & Abramson, D 1999, A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems. in WCH Cheng & ASM Sajeev (eds), PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999. Springer, Singapore, pp. 68-79.

A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems. / Randall, Marcus; Abramson, David.

PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999. ed. / Wilson C. H. Cheng; A. S. M. Sajeev. Singapore : Springer, 1999. p. 68-79.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems

AU - Randall, Marcus

AU - Abramson, David

PY - 1999

Y1 - 1999

N2 - Tahu Search (TS) is a meta-heuristic search algorithm that is easy to parallelise. Efficient parallelisation 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 real-time applications due to its parallel scala­bility and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are pre­sented that show that good parallel speedup is achieved while efficient solutions to hard COPs are obtained.

AB - Tahu Search (TS) is a meta-heuristic search algorithm that is easy to parallelise. Efficient parallelisation 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 real-time applications due to its parallel scala­bility and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are pre­sented that show that good parallel speedup is achieved while efficient solutions to hard COPs are obtained.

M3 - Conference contribution

SN - 9814021598

SP - 68

EP - 79

BT - PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999

A2 - Cheng, Wilson C. H.

A2 - Sajeev, A. S. M.

PB - Springer

CY - Singapore

ER -

Randall M, Abramson D. A General Parallel Tabu Search Algorithm for Combinatorial Optimisation Problems. In Cheng WCH, Sajeev ASM, editors, PART '99: Proceedings of the 6th Australasian Conference on Parallel and Real-Time Systems, Melbourne, Australia, 29 November - 1 December 1999. Singapore: Springer. 1999. p. 68-79