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 Dive into the research topics of 'A Tail of 2n Cities: Performing Combinatorial Optimisation using Linked Lists on Special Purpose Computers'. Together they form a unique fingerprint.

  • 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