Algorithmics - The Computing Universe: A Journey through a Revolution - page 95

approach rapidly becomes impractical. We can therefore say that such a brute
force algorithm for the N-city problem is unreasonable . To understand better
what we mean by reasonable and unreasonable , we need to look at how we can
measure the performance of algorithms. Before we do this, we will give a brief
history of attempts at solving the TSP for large numbers of cities.
In 1954, three researchers at the RAND Corporation in Santa Monica,
California - George Dantzig ( B.5.6 ), Ray Fulkerson, and Selmer Johnson - looked
at the problem of finding the shortest path for a tour through all the forty-eight
contiguous U.S. states. Newsweek reported their success:

A

B E

C D

Fig. 5.13. The TSP for our five-city prob-
lem corresponds to finding the shortest
round tour through all of the cities. Note
that to conform to the usual formula-
tion of the TSP problem with all-to-all
paths possible between the cities, we
have added in the missing “direct” paths
between B and D, B and E, and A and
C, taking the distances as the shortest
distances to go between them, going via
an intermediate node.

Finding the shortest route for a traveling salesman - starting from a
given city, visiting each of a series of other cities, and then returning to
the original point of departure - is more than an after-dinner teaser. For
years it has baffled not only goods- and salesman-routing businessmen but
mathematicians as well. If a drummer visits 50 cities, for example, he has 10 62
(62 zeros) possible itineraries. No electronic computer in existence could sort
out such a large number of routes and find the shortest.
Three RAND Corp. mathematicians, using Rand McNally distances between
the District of Columbia and major cities in each of the 48 states, have finally
produced a solution. By an ingenious application of linear programming - a
mathematical tool recently used to solve production-scheduling problems - it
took only a few weeks for the California experts to calculate “by hand” the
shortest route to cover the 49 cities: 12,345 miles. 5

The algorithm the three researchers used to solve the problem was unusual: it
was just a board with pegs at the city locations and a piece of string to try out
possible TSP tours. As the Newsweek blurb recounts, they found the shortest tour
by using a powerful technique called linear programming . Dantzig had devised
the technique as a method to schedule the training, supply, and deployment of
military units when he was working at the Pentagon after World War II.
Linear programming expresses the problem as an economic model with
inputs and outputs as variables subject to a set of constraints. These constraints
can include inequalities, such as requiring some variables to always be greater
than or equal to zero. As the name implies, the variables were combined in a
set of linear equations and the goal was to choose the variables to maximize an
explicit objective. To find the optimal solution to such a linear programming
problem, Dantzig developed an algorithm that was named one of “The Top Ten
Algorithms of the Century” in the year 2000. This is the simplex algorithm,
which is still widely used in industry where the models can have hundreds of
thousands of constraints and variables. A detailed discussion of this algorithm
is beyond the scope of this topic, but it still provides the basis for modern anal-
yses of the TSP. Using linear programming, Dantzig, Fulkerson, and Johnson
were able to prove that their solution was indeed the shortest path, writing:

B.5.6. George Dantzig (1914-2005)
is credited with the development of
the simplex algorithm and numer-
ous other contributions to linear pro-
gramming. His algorithm is used to
solve many real-life problems related
to air traffic scheduling, logistics,
planning processes in oil refineries,
circuit design, and many more.

In this context, the tool of choice is linear programming, an amazingly
effective method for combining a large number of simple rules, satisfied by
all tours, to obtain a single rule of the form “no tour through this point set
can be shorter than X.” The number X gives an immediate quality measure: if
we can also produce a tour of length X then we can be sure that it is optimal. 6