TO COMBINATORIAL OPTIMISATION

This Memorandum is a draft version of a review paper which will be submitted to the Bulletin of the Institute of Mathematics and its Applications. Three new approaches to combinatorial optimisation have been described recently. They are based on analogies with physical and biological systems. The first, Kirkpatrick's Optimisation by Simulated Annealing method, has already proved useful in engineering optimisation problems such as Layout and. " routing in VLSI chip design. At present, this is probably the most powerful * general optimisation method for use on conventional serial computers., The second, Brady's evolution-based approach, has yet to receive a thorough numerical study, However,,it seems likely to provide powerful optimisation methods for parallel SIMD computer architectures of which the most widely distributed example in the UK is the ICL DAP. The third method, Hopfield and Tank's Optimisation via networks of amplifiers, is the most revolutionary and may lead to a new generation of chips with mixed analog/digital functions for rapid optimisation.-. J,!1A L IT Y-'S PLCT T