The Problem with Salesmen
A TRAVELING SALESMAN stands at a train station in St. Louis, carefully considering his path. He must make stops in Chicago, New Orleans and Mason City, Iowa, among others, before returning home. And he wants to be efficient about it. So how can he plan the best route, visiting each stop only once and traveling the shortest distance?
It’s a question that has existed for centuries — with applications ranging from route planning to DNA sequencing — and each new discovery only provides more possibilities to explore. That’s what makes it so intriguing to Professor Sam Gutekunst, the John D. & Catherine T. MacArthur Assistant Professor of Data Science, and his student researchers.
Supported by a National Science Foundation grant, Gutekunst is exploring the famous Traveling Salesman Problem (TSP) with help from Asta Rustad ’23, Yacine Bouabida ’24 and Austin Beal ’24.
The group plans to publish its findings, which the members presented at the world’s largest mathematics gathering, the Joint Mathematics Meeting, in January. “The impressively large amount of data generated from my students’ computational work, and the new theory and algorithms they’ve developed, give new insights into the TSP, ” Gutekunst says.
The way the problem scales makes it notoriously difficult. “If we have five cities, we can try every single path,” Bouabida says. “But as you add destinations, it becomes infinitely more complex.” Case in point: With just 100 cities, the number of possible routes exceeds the number of atoms in the known universe. That’s a lot of lines on the map.
Always Be Calculating
In spring 2022, Rustad began tackling the TSP, working to break down the complexities of the problem and identify a simplified starting point. “With problems this hard and famous, there’s a community of researchers working together, many of whom work on special cases of the problem,” Gutekunst says. “We’re working with the circulant TSP, a special case with more mathematical structure.” Their work laid the foundation for a breakthrough.
When Beal and Bouabida took over in summer 2022, they developed experiments and ran billions of trials, hoping to create algorithms that worked every time. “We took up a lot of whiteboard space,” Bouabida says. “We drew lots of graphs, bounced ideas around and got frustrated.”
The pair embraced the challenge as an opportunity. “Once, Sam casually shared that this is Ph.D.-level research, and I don’t even have my B.A. yet,” Bouabida says. “Sam prepared us for the type of thinking that we need to employ. Our computational and theoretical work has given me tools to expand the way I think.”
They also found an answer to the problem (a version of the problem, at least). Using a prime-squared number of cities as a limiter, the team identified an algorithm that always determines the best route. “We’ve proven it. We know it works,” Bouabida says. “And since there’s an infinite number of prime numbers, we’ve solved an infinite number of cases.”
The Next Leg of the Journey
Rustad has returned to the problem and is extending the work by focusing on twin primes. “This small twist makes it much harder,” Rustad says. Understandably — the number of twin primes is unknown, with estimates surpassing 800 trillion.
Gutekunst is optimistic that Rustad is on the right track for solving yet another intriguing case of the problem. “If Asta’s work gives an algorithm for over 800 trillion numbers of destinations, I’ll be pretty content — for now.”