Size Generalization of Learning-Based Approaches for the Travelling Salesperson Problem

This thesis focuses on learning-based approaches for the Travelling Salesperson Problem (TSP). While these techniques achieve comparable performance to classical solvers on small sizes, they fail to generalize the learned strategies to larger instances. In particular, Graph Neural Network (GNN) architectures with non-autoregressive (NAR) decoding scheme show notably poor performance when applied to graph sizes beyond those seen during training. However, leveraging the efficiency of NAR models through the compositional paradigm has led to some of the top-performing learning-based methods in the literature. Even though such approaches had a lot of success by breaking down the original problem into subproblems, they ignore the potential to combine direct and compositional generalization. We address this by leveraging the direct size generalization improvements in the compositional setting. In particular, our model achieves competitive performance compared to previous methods, having 9 times fewer parameters than the current architecture used in the same framework. Moreover, during our exploration of direct NAR generalization, we also tested SizeShiftReg, a novel regularization method originally designed for the graph classification task. To the best of our knowledge, this is the first application of SizeShiftReg to learning-based methods in the Combinatorial Optimization (CO) domain. We obtain a 7.4% reduction in the average optimality gap on the test dataset, which indicates the potential of SizeShiftReg to improve the direct generalization of learning-based approaches for the TSP. However, further experimentation with significantly more computational resources is required to scale the application of SizeShiftReg to the amount of data used in state-of-the-art models.