Bucknell Students Take a Crack at Infamous Math Problem

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 while 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 the Traveling Salesman Problem (TSP) so intriguing to Professor Sam Gutekunst, the John D. and Catherine T. MacArthur Assistant Professor of Data Science, and his impressive cohort of student researchers.

Supported by a National Science Foundation grant, Gutekunst conducted research on the famously challenging problem, employing the help of Asta Rustad '23, Yacine Bouabida '24 and Austin Beal '24.

The group plans to publish their findings, which they presented at the world's largest mathematics gathering, the Joint Mathematics Meeting, in early 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. And from concert tours to circuit boards, the most efficient route is more sought after than one might expect.

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 on the Circulant TSP, a special case with more mathematical structure."

Beal and Bouabida picked up the problem in summer 2022. They took Rustad's lead, working to simplify the problem before running thousands of simulations and digging into both the theoretical and computational work. "One of our big focuses became trying to understand the different cases of the problem — understanding scenarios and restrictions where Circulant TSP could be more easily solved," Beal says.

The pair 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. "Drew lots of graphs, bounced ideas around and got frustrated."

They embraced the challenge as an opportunity, recognizing the long-term impact the research could have on their careers and appreciating how the experience could advance their reasoning skills. "I've always really enjoyed the computational aspect of math and computer science, but I also really enjoy the thinking part," Beal says. "The TSP is about as thinking-related to those fields as you could get. It's like taking something that I just learned and learning how to think about it on a really deep level."

"I could have gotten an internship where I was fetching coffee for people, or I could have worked on a really hard problem," Bouabida says. "Once, Sam casually shared that this is Ph.D.-level research. I don't even have my B.A., yet Sam trusted us. He gave us the tools and guidance that 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."

The Power of Primes

In problems of this magnitude, it's a common practice to abandon the quest for a perfect solution and instead start with the next best thing: a perfect solution to as many cases as possible.

"What makes this problem so interesting is that we're really pushing the limits of what we can solve," says Beal. "Are we ever going to be able to come to that definitive solution for this entire problem? I don't think we've come to that conclusion yet."

So how is progress made? "We needed an idea that was fundamentally different — an idea that no one else had before," says Gutekunst. "My students had one of those ideas this summer and found perfect solutions to a whole class of Circulant TSP problems. We now know how to solve them optimally because my students thought about the problem in a way that no one else had before."

The students' solution was the first new progress on general Circulant TSP instances in decades. In the 1970s, it was shown that the problem could be exactly and efficiently solved whenever the number of cities was prime. Beal, Bouabida and Rustad made the first new breakthrough since that result: 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, which occur when two prime numbers are separated by only two digits, like three and five. "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 excited — for now."