Over the weekend, I spent some time looking up different TSP solvers to use. It was actually quite challenging for me to find good TSP solvers to use. It takes a good Googler to sniff out the software worth pursuing. Over the last few years, I’ve realized that searching for things online is a skill that’s become increasingly handy to hone. It’s pretty amazing how much information one can get online, if one only knows how to search for it – and remembers to search for it. Anyway, this is something I’ve become better at over time, but in this case, I was initially only able to find two to three basic implementations, which did quite a poor job at solving some example TSP graphs that I tested.

NOTE: When testing an algorithm for an optimization problem which finds approximate solutions, there’s often a trade-off between runtime and solution optimality. Of course, ideally, we’d prefer an algorithm that both runs fast and finds very-close-to optimal solutions, but it can be difficult to come across one like this. Usually, some algorithms will take really long to run but give you solutions very close to optimal, while others will give very loose approximations but run quickly. The type of algorithm you want to use will depend on what you’re using it for. For our purposes, we definitely wanted one that ran fairly quickly (we don’t want our complete pipeline which finds a path to take too long).

Out of the first two TSP solvers I tested, one ran incredibly fast, but found very sub-optimal solutions, and the other found optimal solutions for small-to-medium sized graphs but wouldn’t finish running when I increased graph sizes to 100 nodes or larger (suggesting that this algorithm was always finding optimal solutions), so neither of them were ideal. After talking to my mentor about this, he spent some time searching himself, and suggested a few other options for me to try. The new options were more official software built by teams of engineers (for example, one solver used Google OR Tools) and so set forth a new set of installations and academic certifications in order to do some small testing.

This testing led to some compatibility issues that were a bit frustrating to deal with. Since this is a remote internship, I’m mostly limited to using my local machine, which is Windows. A few of the executables used for getting TSP solutions didn’t have executables that run on Windows, and some of the wrapper code for one solver was written to work for Linux systems. Initially, however, I didn’t realize these were the issues, and spent a few bewildered hours trying to figure out what was going on. When talking to my dad and my mentor about these issues, I learned about Windows subsystems and dual booting – two methods (of varying difficulty) to use a Linux kernel on a Windows computer. Dual booting actually requires quite a bit of tinkering on your computer and it’s pretty easy to accidentally wipe data from your computer when trying to do so. I decided against this option for the current time; I installed an Ubuntu terminal environment which ended up working pretty well!

After I was able to get over some of these operating system issues, I was able to compare all of the different TSP solvers (at this point, I was looking at 9 different solvers) across a range of testing examples (graphs of varying sizes) for their runtimes and solution optimality. At this point, one algorithm started emerging as a clear winner. The Lin-Kernighan heuristic is an effective heuristic that can be used for solving symmetric TSPs and getting very close-to-optimal solutions. One of the solvers efficiently implemented this heuristic and so both runtime and optimality were good.

I talked to my mentor about this result, and we discussed how to properly show this using experiments. I had used 5-6 examples to develop an intuition about which of the solvers did the best, but we would need more than those to have a decent argument for the claim that the LKH solver was better than the others. Using just a few examples doesn’t statistically determine anything, and a lot of solvers also use some amount of randomness in finding solutions, meaning that just a few tests weren’t going to be enough.

To be more meticulous, I decided to randomly generate 100 examples each of adjacency matrices of graphs at different node sizes (ranging from 5 nodes to 5000 nodes). Using the same examples for each solver, I would run each matrix 10 times and average results across all the runs. Tabulating and graphing these results will hopefully exhibit a more definite and clear pattern.