C-BRIC Researchers Work to Solve Large-Scale Travelling Salesman Problems

Sourav Sanyal and Kaushik Roy of Purdue University are working to solve Large-Scale Travelling Salesman Problems (TSP). In their recent publication “Neuro-Ising: Accelerating Large Scale Travelling Salesman Problems via Graph Neural Network,” they tackled the issue of performance degradation in large problems. Their work will be published in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems journal.

 

Using Graph Neural Networks (GNN) and Ising models, Sanyal and Roy proposed Neuro-Ising. Neuro-Ising is a machine learning framework that uses Ising models to find clusters of near-optimal partial solutions of large-scale TSPs and combines those solutions by employing a supervised data-driven mechanism, which the researchers model as a Graph Neural Network (GNN). The proposed approach was able to generalize to unseen problems while avoiding the runtime complexity otherwise required if the solution was built from scratch. Experiments using the simulation framework revealed that Neuro-Ising is able to accelerate TSPs with respect to Concorde – the best-known exact solver, by ~396x with an acceptable 20% degradation in solution quality across 15 problems from the TSPLib benchmark suite.