Cities: Performing Combinatorial Optimisation Using Linked Lists On Special Purpose Computers

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. 1 Introductio