New TSP Algorithm(?)

[Geoffrey Goodhill]

Below is an article from the Guardian 28.5.94, a UK quality newspaper,
which might be of interest to readers of this list. It's about a new
algorithm for the TSP that claims to be the best yet.  There is
apparently an article forthcoming in the Journal of Neural Computing.

I note two things:

1) Strange though it may seem to those of us who think that the
purpose of publishing in reputable journals is to tell people what one
has done, the article below suggests that the authors may not be going
to tell us what the algorithm is.

2) Given that a number of inflated claims have been made for new TSP
algorithms in the past based on comparisons with poor alternatives,
I'd be interested to see proper comparisons to justify the authors'
assertions.

Geoff Goodhill


********************************************************************


        SCIENCE WELL ON THE ROAD TO SALESMAN SOLUTION
        ---------------------------------------------

Tim Radford reports on a near-answer to a deceptively simple
mathematical question.

A mathematical conundrum called the Travelling Salesman Problem may
have lost its power to baffle, according to British Telecom Scientists.

They admit they have not exactly solved it: just arrived at a way to
make a computer produce the best and fastest solution yet.

The 60-year-old problem is terribly simple, but has occupied some of
the world's most powerful brains - and most powerful computers - for
years. It is this: a salesman wants to visit 3, or 4, or 10, or 100
places. What is the shortest, or fastest, route?

The options multiply dramatically with the number of calls. A journey
to 3 sites involves 6 possible routes. A journey to 10 offers
3,628,800 possible choices. A journey around 100 would involve 10^156.
This is 1 followed by 156 zeros, almost equivalent to the number of
atoms in the universe - squared. 

The almost-optimum solution, by Dr Shara Amin and Dr Jose Luis
Fernandez-Villacanas Martin at the BT laboratories in Martlesham
Heath, near Ipswich, Suffolk, can now be reached in 1.6 seconds for a
100-point journey. The absolute best would take days. Even a
1000-point problem can be solved in less than 3 minutes.

The answer, they say, will be reported in the Journal of Neural
Computing in July. The algorithm they use will not be revealed, but
there will be clues for other mathematicians on how to proceed.

The algorithm - into which planners can slot variables such as a bank
holiday in Oslo or engineering works between Birmingham and London -
will help sales managers and, for that matter, telephone managers with
a choice of calls.

But the technique also has military uses. Imagine, said Professor
Peter Cochrane, of the BT laboratories, a jet pilot under simultaneous
attack from ground-to-air missiles and enemy aircraft. "Now you have a
hyperspace problem. It is this: where do I steer, and who do I shoot
at first, and in what order, to minimise the chances of me getting
killed and maximise the amount of damage I can do to them?"

But the immediate value would be in preparing the patterns on computer
circuits, or searching in information "hyperspace", where the options
can reach astronomical levels.

Professor Cochrane sees the procedure as useful in automatic searches
through networks and data libraries. "We are looking at giving
information on demand, where you could have access to all the
libraries in the world, all the museums in the world".