This project was a part of a graduate course that I took in the winter of 2018 taught by Bill Cook, the famous Traveling Salesman Problem (TSP) researcher. The course explored intersections between discrete optimization and machine learning, and mainly consisted of a project.
My group and I decided to try out an idea that I had wanted to explore, which was to attack the problem of variable selection for branching in a branch-and-bound TSP algorithm. Smart variable selection can reduce the number of nodes one needs to explore when executing the algorithm, and current rules have little mathematical basis, so machine learning wasn’t a bad idea.
During the project, I got to implement a TSP solver with a nice visual component, which was a nice visual component. That and the rest of the code can be found here, although the project wasn’t very well organized, so may be difficult to get a sense of where things are.
The final results we got weren’t the most exciting, as our ML algorithm wasn’t able to get enough information from the graph and elsewhere to learn an effective branching rule. Given more time, we could have continued trying new things, but we were necessarily limited. Here is the write-up for our results, which serves as a nice summary: