Debarpan Debnath supervised by Prof. Praveen Paruchuri received his Master of Science by Research in  Computer Science and Engineering (CSE). Here’s a summary of his research work on Solving the Travelling Salesman Problem with Self Improvement Learning

The Travelling Salesman Problem (TSP) is a fundamental NP-hard challenge in Combinatorial Optimization (CO) with widespread applications across logistics, circuit design, and robotics. While traditional exact solvers and heuristic methods are effective, they often struggle with exponential computation times or rely heavily on domain-specific manual engineering. Consequently, Machine Learning (ML), particularly Neural Combinatorial Optimization, has emerged as a promising data-driven paradigm for solving the TSP. Neural approaches primarily relying on autoregressive (AR) solution construction are computationally expensive and scale poorly during both training and inference, as each step of the solution construction requires a full forward pass through the neural network. To address this, Non-Autoregressive (NAR) methods have been proposed, offering the promise of generating complete solution representations (probability heatmaps) in a single network pass. Despite this theoretical advantage, existing NAR approaches have heavily depended on computationally expensive search techniques, such as Monte Carlo Tree Search (MCTS) to convert these heatmaps into near-optimal tours, or iterative diffusion processes to even generate the heatmaps. This reliance severely bottlenecks inference latency and demands significant computational resources, negating the inherent speed advantages of NAR architectures. To overcome these limitations, we propose NARSIL (Non-Autoregressive Self-Improvement Learning), a highly efficient NAR framework that generates high-quality TSP solutions with significantly improved speedups. NARSIL leverages a Transformer-based architecture to predict edge probability heatmaps in a single forward pass. Tours are then constructed using an edge-by-edge greedy decoding strategy and subsequently refined with a lightweight 2-opt local search. Crucially, NARSIL is trained in a completely unsupervised manner. By utilizing Self-Improvement Learning (SIL) combined with geometric data augmentation, the model iteratively improves its own predictions using self-generated pseudo-labels, entirely eliminating the need for expensive optimal solutions generated by exact solvers. Crucially, the extreme speed of our generation pipeline makes this continuous self-labelling computationally viable; without it, generating pseudo-labels on-the-fly would create a severe training bottleneck, especially for massive graphs. Extensive empirical evaluations demonstrate that NARSIL establishes a new state-of-the-art in the speed-accuracy trade-off for neural TSP solvers. On standard benchmark instances, NARSIL achieves remarkably low optimality gaps of 0.420% on TSP-500 and 0.916% on TSP-1000. It delivers a 8– 11× speed-up over the previous fastest neural baseline and a 112–268× speed-up over high-accuracy autoregressive models, while maintaining comparable or superior solution quality. Furthermore, the model exhibits strong generalization capabilities to both unseen problem sizes and out-of-distribution spatial distributions. By combining near-optimal accuracy, unsupervised training, and ultra-low latency inference, NARSIL presents a highly practical solution for large-scale and real-time applications. 

June 2026