Parallel algorithms for combinatorial optimization on transputer arrays

Problems in combinatorial optimization, whether they are solved exactly or approximately by a heuristic algorithm, tend to be computationally intensive. This thesis investigates ways of utilizing MIMD architectures for two particular problems in combinatorial optimization; the travelling salesman problem and the (Δ D) graph problem. Firstly, some general principles of concurrent programming are described with reference to work done on an array of 1260 transputers. A distributed implementation of simulated annealing for the travelling salesman problem is then described. The problems of producing a general communication harness for a large processor network are discussed and a possible implementation is outlined. Methods of assessing the suitability of particular network topologies for such a harness are described, and a quantitative comparison is made between some networks using a idealized model of the behaviour of a harness. The (Δ, D) graph problem, that of finding the largest graph of given valency and diameter, is an abstract problem in graph theory relevant to the problem of choosing a good network for a multiprocesor computer. A heuristic algorithm to search for solutions to this problem is developed, based on Lin and Kernighan's algorithm for the travelling salesman problem. An incremental method for evaluating the effect of modifying a graph is described which results in a significant speedup of this algorithm. A result of this work has been the discovery of new maximal graphs, improving the records for largest known graphs to 41 for valency 4 and diameter 3, and to 132 for valency 7 and diameter 3.