(NL English translation, with permission from El País, of the article Cómo visitar dos millones de estrellas en el menor tiempo posible published on December 14, 2020, in the “Café y Teoremas” series)
The Gaia project of the European Space Agency (ESA) has cataloged 2,079,471 stars. Could we find a route to visit them all, in the shortest possible time? Recently, a group of researchers have come up with a path that is very close to the answer. These types of questions are studied in an area of mathematics known as mathematical optimization or mathematical programming, of great importance not only theoretically but also for its applications to real life and for its ramifications in other disciplines.
It is about identifying, among all the possibilities to solve a problem, the best one, with respect to an established criterion. We ask ourselves these types of questions when we choose a telephone company (we want to choose the one that offers us a more adequate service at a lower price), when we are going to run errands in our neighborhood (we want to move around spending as little energy and time as possible) or, planning a long walk through the Universe. In all cases, we choose between all the existing possibilities (the set of telephone companies or the various routes through our neighborhood or through the Cosmos) to
optimize an amount (money or time).
The problem of the star ride is an example of the traveling salesmen problem, one of the most important in the field. It is about a network of cities, interconnected by roads. From it we define a graph, that is, an abstract mathematical structure that contains objects (the vertices of the graph) and relationships between them (the edges of the graph). In our case, the vertices would be the cities, and there would be an edge between two cities if they are connected by a road. In addition, we will include the distance between the connected cities giving a weight to the edges, quoted in kilometers, for example.
Now, a traveler looks for a way to visit all cities without repetition, ending the tour in the initial city and using the fewest kilometers possible. In mathematical language, the question is to find what is called a Hamiltonian cycle (a path that begins and ends at the same point that only passes once through each vertex) in the graph under study, in such a way that the sum of weights of its edges is the smallest possible.
For a small number of cities, the account can be done by hand, but the complexity of the problem increases rapidly depending on the cities we are considering. Taking more than 20 cities and assuming that the number of connections is high (the maximum number of roads in this case would be 190, assuming there is a direct road between any pair of towns), the algorithmic problem of calculating all routes becomes an intractable issue. In fact, it is well known that it is a difficult algorithmic problem: finding the solution, even using powerful computers, requires so much computational time that it is considered impractical.
However, modern methods allow finding near-optimal solutions in reasonable calculation times. These are solutions to the problem that do not minimize the number of kilometers, but are very close to it, that is, their difference from the optimum is small. A wide variety of mathematical techniques are used in this search, including the use of heuristics, statistics, probability
and analysis.
Original map of the work by Dantzig, Fulkerson and Johnson.
The study of this problem motivated the development of many of the central ideas in this discipline. The fundamental work,
from 1954, is Solution of a large-scale travelling-sales problem. In it, George Dantzig (father of the algorithm), Delbert R. Fulkerson and Selmer M. Johnson laid the foundations for the formal study of the traveling salesman problem and, incidentally, shaped the entire discipline of mathematical programming (which already received a great boost during World War II). As a curious fact, the authors studied the problem for 48 cities in the United States, and obtained a route to visit them all following a Hamiltonian cycle. The tour length was 12,345 miles.
Currently, and thanks to the algorithmic power of computers, much more complex systems can be studied than in the 1950s and, surprisingly, results very close to the optimal value can be obtained. This is the case of the recent work by Bill Cook (University of Waterloo, Canada) and Keld Helsgaun (Roskilde University, Denmark): they have found, using mathematical optimization techniques, the shortest route to visit the 2,079,471 stars indexed by the Gaia project of the ESA (Star Tours). The study, which can be found here, finds a route to visit all these stars in … 94,208,157.5 light years! And that is also very close to being the optimal solution. This recent and impressive application that shows the mathematical power of the ideas of this discipline.