A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers

David Abramson, Paul Logothetis, Marcus Randall, Adam Postula

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

Abstract

This paper addresses the development of general purpose meta-heuristic based combinatorial optimisation algorithms. With this system, a user can specify a problem in a high level algebraic language based on linked list data structures, rather than conventional vector notation. The new formulation is much more concise than the vector form, and lends itself to search heuristics based on local neighbourhood operators . The specification is then compiled into C code, and a unique solver is generated for each particular problem. Currently, search engines for simulated annealing, greedy search and Tabu search have been implemented, and good results have been achieved over a wide range of optimisation problems.
We have also implemented a special purpose computer that solves one particular optimisation problem formulated using this technique, namely the travelling salesman problem. Solvers have been produced for simulated annealing, greedy and Tabu search, and a speedup up to 16 times has been achieved over a high-end workstation.
Original languageEnglish
Title of host publicationInternational Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98)
Subtitle of host publicationProceedings of the 2nd International Conference
EditorsHenry Selvaraj, Brijesh Verma
PublisherWorld Scientific
DOIs
Publication statusPublished - 1998
Externally publishedYes

Fingerprint

Tabu search
Combinatorial optimization
Simulated annealing
High level languages
Traveling salesman problem
Search engines
Data structures
Specifications

Cite this

Abramson, D., Logothetis, P., Randall, M., & Postula, A. (1998). A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers. In H. Selvaraj, & B. Verma (Eds.), International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98): Proceedings of the 2nd International Conference World Scientific. https://doi.org/10.1142/9789814528948
Abramson, David ; Logothetis, Paul ; Randall, Marcus ; Postula, Adam. / A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers. International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98): Proceedings of the 2nd International Conference. editor / Henry Selvaraj ; Brijesh Verma. World Scientific, 1998.
@inproceedings{e4381369d6fd4fc3828057050c847080,
title = "A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers",
abstract = "This paper addresses the development of general purpose meta-heuristic based combinatorial optimisation algorithms. With this system, a user can specify a problem in a high level algebraic language based on linked list data structures, rather than conventional vector notation. The new formulation is much more concise than the vector form, and lends itself to search heuristics based on local neighbourhood operators . The specification is then compiled into C code, and a unique solver is generated for each particular problem. Currently, search engines for simulated annealing, greedy search and Tabu search have been implemented, and good results have been achieved over a wide range of optimisation problems.We have also implemented a special purpose computer that solves one particular optimisation problem formulated using this technique, namely the travelling salesman problem. Solvers have been produced for simulated annealing, greedy and Tabu search, and a speedup up to 16 times has been achieved over a high-end workstation.",
author = "David Abramson and Paul Logothetis and Marcus Randall and Adam Postula",
year = "1998",
doi = "10.1142/9789814528948",
language = "English",
editor = "Henry Selvaraj and Brijesh Verma",
booktitle = "International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98)",
publisher = "World Scientific",
address = "United States",

}

Abramson, D, Logothetis, P, Randall, M & Postula, A 1998, A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers. in H Selvaraj & B Verma (eds), International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98): Proceedings of the 2nd International Conference. World Scientific. https://doi.org/10.1142/9789814528948

A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers. / Abramson, David; Logothetis, Paul; Randall, Marcus; Postula, Adam.

International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98): Proceedings of the 2nd International Conference. ed. / Henry Selvaraj; Brijesh Verma. World Scientific, 1998.

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

TY - GEN

T1 - A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers

AU - Abramson, David

AU - Logothetis, Paul

AU - Randall, Marcus

AU - Postula, Adam

PY - 1998

Y1 - 1998

N2 - This paper addresses the development of general purpose meta-heuristic based combinatorial optimisation algorithms. With this system, a user can specify a problem in a high level algebraic language based on linked list data structures, rather than conventional vector notation. The new formulation is much more concise than the vector form, and lends itself to search heuristics based on local neighbourhood operators . The specification is then compiled into C code, and a unique solver is generated for each particular problem. Currently, search engines for simulated annealing, greedy search and Tabu search have been implemented, and good results have been achieved over a wide range of optimisation problems.We have also implemented a special purpose computer that solves one particular optimisation problem formulated using this technique, namely the travelling salesman problem. Solvers have been produced for simulated annealing, greedy and Tabu search, and a speedup up to 16 times has been achieved over a high-end workstation.

AB - This paper addresses the development of general purpose meta-heuristic based combinatorial optimisation algorithms. With this system, a user can specify a problem in a high level algebraic language based on linked list data structures, rather than conventional vector notation. The new formulation is much more concise than the vector form, and lends itself to search heuristics based on local neighbourhood operators . The specification is then compiled into C code, and a unique solver is generated for each particular problem. Currently, search engines for simulated annealing, greedy search and Tabu search have been implemented, and good results have been achieved over a wide range of optimisation problems.We have also implemented a special purpose computer that solves one particular optimisation problem formulated using this technique, namely the travelling salesman problem. Solvers have been produced for simulated annealing, greedy and Tabu search, and a speedup up to 16 times has been achieved over a high-end workstation.

U2 - 10.1142/9789814528948

DO - 10.1142/9789814528948

M3 - Conference contribution

BT - International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98)

A2 - Selvaraj, Henry

A2 - Verma, Brijesh

PB - World Scientific

ER -

Abramson D, Logothetis P, Randall M, Postula A. A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers. In Selvaraj H, Verma B, editors, International Conference on Computational Intelligence and Multimedia Applications 1998 (ICCIMA '98): Proceedings of the 2nd International Conference. World Scientific. 1998 https://doi.org/10.1142/9789814528948