The Register Citizen (Torrington, CT)
Win $10K if you can prove this CT researcher wrong
A Connecticut researcher believes he’s solved a math problem that could transform nearly every industry worldwide and is offering $10,000 to anyone who can prove him wrong.
The traveling salesman problem sounds simple. Imagine a traveling salesman who has to reach a certain number of locations only once and then return to his starting point. How do you derive the path the salesman must follow with the minimum of cost?
“Cost” could mean any finite resource, such as time or money or distance. In that way, the traveling salesman problem can be relevant to many situations.
“Every scheduling problem is a sort of traveling salesman problem,” said UConn professor of operations research and operations management Moustapha Diaby.
Or, “Suppose you want to design a circuit board for computer chips, and you need to put dots on the board and you want to do this in the most efficient way,” Diaby said.
It might also benefit airlines that want to schedule flights efficiently, or shipping companies that want to unload containers in the quickest way possible or decide which ships should arrive at a busy port.
“In almost every industrial practice, we encounter issues of scheduling and sequencing,” Diaby said. “So, every sequencing, routing and scheduling problem is rooted in the traveling salesman problem.”
There are also theoretical implications. The famous unsolved theoretical computer science puzzle “P versus NP” — which Lance Fortnow, dean of the College of Computing at the Illinois Institute of Technology, called “the single most important question in all of theoretical computer science and one of the most important in all of mathematics” — is also rooted in the traveling salesman problem.
P versus NP is one of seven so-called Millennium Prize Problems, the solution for each of which is worth $1 million from the Clay Mathematics Institute.
Diaby believes he and his team have found an algorithm that solves the traveling salesman problem and, by extension, has implications for P versus NP, “which people up to now even when you show it to them, they don’t believe it,” he said.
When asked if his solution has the potential to revolutionize almost every industry on Earth, Diaby replied simply: “There is that potential, absolutely.”
There have been other solutions for the traveling salesman problem, but they have been restricted by size. A GPS can quickly determine the shortest distance between two points, but ask a computer to simultaneously determine the shortest route between 100 points and it will take a long time. “It will take a computer more than the number of atoms in the universe to actually come up with an answer,” Diaby said. “It’s a two to the power 100 possibility.”
There are problems that require answers that large, but Diaby said his algorithm is not constrained by “enumeration” and so is “able to do things that no other algorithms can do.”
“The potential impact on industry is just incredible over time,” he said.
Diaby and his team first arrived at a solution years ago, but he’s been refining it to be simpler and more elegant before publishing his findings in a large, well respected journal.
The problem itself is so complex and sought after that academic journals were reluctant to publish until Diaby’s solution had been fully vetted. So it was suggested that Diaby offer a prize to anyone who can prove his algorithm wrong.
“We are even offering a $10,000 prize for anybody who can come up with a TSP that our method cannot solve,” he said.
There is still work to be done before his algorithm can have an effect on practical applications, and it will require other researchers to build on his findings.
“In the history of the field, when you have problems that have special structures like that, people build on each other’s results to a point where you don’t need to follow each of the steps of general linear programming in such a way that you come up with a very fast way to prove a linear programming without going to all the detailed calculation,” he said.
The algorithm itself can be downloaded at Diaby’s UConn web page.