Mark Velednitsky Finds Short Proof For Traveling Salesman Problem

IEOR graduate student Mark Velednitsky has reduced a twenty-eight page proof for the traveling salesman problem (TSP) to just a few lines.

Velednitsky’s proof titled “Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem” was recently published in Operations Research Letters, and will make learning this particular TSP proof much easier for future students.

“For someone with a background in the traveling salesman problem, this is a really short proof that I could explain in just a few minutes,” said Velednitsky, “Having it in this much more compact form makes it accessible to more people.”

The TSP is a classic problem in operations research, named because the problem typically is posed as something like this: if a salesperson needs to travel to x number of cities, how can we calculate the most efficient route for them to take? The problem is of continued great interest due to its wide application in industries such as logistics, transportation, and many other fields.

But the problem is difficult — typically the more cities one adds, the more time it will take a computer to calculate the solution. Depending on the number of cities and their configuration, the problem quickly becomes intractable — meaning that in some configurations even with the fastest computers available today, it would take an eternity to compute the most efficient route for the salesman to take.

Not every way of posing the traveling salesman problem to a computer is the same. One way was proposed by George Dantzig (IEOR Professor, 1960-1966), Ray Fulkerson, and Selmer Johnson (DFJ) and another was proposed by Miller, Tucker, and Zemlin (MTZ). Experimentally, it seemed like the DFJ formulation worked better than the MTZ formulation, but no one knew if it always performed better until a paper proved it in 1990. Velednitsky’s paper shows this same fact, but much more succinctly.

In a story that resembles the famous George Dantzig story at UC Berkeley (which later inspired a scene in the movie Good Will Hunting), Velednitsky initially worked on the proof as a homework problem.

“They were kind of expecting us to do one of these [long] proofs,” said Velednitsky, “And everyone had been stuck on it. I eventually came up with this one, and [the other students] were like ‘Wow, I actually understand it and enjoy proving this now.’”