Accession Number:

ADA169547

Title:

Physics for Travelling Salesmen: Some New Approaches to Combinatorial Optimisation.

Descriptive Note:

Memorandum rept.,

Corporate Author:

ROYAL SIGNALS AND RADAR ESTABLISHMENT MALVERN (ENGLAND)

Personal Author(s):

Report Date:

1986-03-01

Pagination or Media Count:

22.0

Abstract:

Three new approaches to combinatorial optimisation have been described recently. They are based on analogies with physical and biological systems. The first, Kirkpatricks 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 probably the most powerful general optimization method for use on conventional serial computers. Although the second, Bradys evolution-based approach, has yet to receive a thorough numerical study, 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 Tanks Optimisation via networks of amplifiers, is the most revolutionary and may lead to a new generation of chips with mixed analogdigital functions for rapid optimisation.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE