Enhancing Neural Networks for TSP and VRP: Algorithmic Bias, Hierarchical Structures, and Foundation Models for Efficient Routing
COM1 Level 3
MR1, COM1-03-19
Abstract:
The Traveling Salesman Problem (TSP) and its variants, including Vehicle Routing Problems (VRP), are critical challenges in computer science with significant practical applications in logistics and fleet management. Despite its simple definition, its NP-hard nature has spurred the development of more effective algorithms. The rise of deep learning has led researchers to seek if data-driven learning can be helpful in these NP-hard problems. Unfortunately, the discrete nature and numerous feasible solutions of these combinatorial problems pose significant challenges to deep learning systems. This thesis explores how integrating inductive biases, which favour certain patterns in a learning algorithm, into neural networks can enhance their ability to solve the TSP and VRP. However, identifying useful inductive biases can be challenging due to the vast solution space of these problems. This thesis presents three approaches to embedding useful inductive biases into neural networks, successfully improving their capabilities. We also show that such inductive biases are instrumental when problems are drawn from realistic real-world distributions.
The first approach investigates embedding algorithmic inductive bias in neural networks to solve the TSP. A key constraint of the TSP is that each node has exactly two adjacent connecting edges, representing entry and exit. We observe that the solution to the TSP is also a solution to the assignment problem on a matrix. Given this, we identify two differentiable algorithms for the assignment problem: the Minsum algorithm that enforces assignment constraints and the Sinkhorn algorithm that approximates them. We showcase how to integrate these algorithms with neural networks to encourage favourable outputs for the TSP. Experiments show that enforcing constraints can be detrimental in this case, as even though the solution to the TSP is the solution to the assignment problem, the converse is not necessarily true. Approximating the constraints, however, retains learning flexibility and enhances the model's predictive power. Alternatively, we show in an alternative problem that when the required outputs of the network and algorithm are well-aligned, the network benefits from enforcing constraints.
The second approach explores alternative methods of implementing inductive biases, focusing on effectively representing the set of available nodes for traversal, given that each node should only have two adjacent edges. We present an Expectation-Maximization-inspired algorithm that efficiently identifies and summarizes the set of unvisited nodes in a problem instance. Combined with a locality-focused Hypernetwork, these approaches form a hierarchical problem-solving approach that provides a strong inductive bias of city availability. In particular, we show that incorporating this approach is extremely useful when the TSP is drawn from more realistic distributions.
Strong inductive biases enable the network to leverage patterns in the problem. This, in turn, promotes better generalization. In the third approach, motivated by recent advancements in Large Language Models, we explore foundation models for the VRP. Inspired by regularization to encourage generalization, we propose an adaptive decoder capable of varying its compute according to the problem state, imposing sparsity on the network. We also further develop the soft-clustering approach to enable the construction of rich representations based on various tasks. The overall flexibility of the model enables the training of a powerful foundation model for the highly dynamic and complex Multi-task Multi-distribution Vehicle Routing Problem, where a trained model has to adapt to unseen tasks and distributions concurrently.
Overall, this thesis advances the application of deep learning to solve complex routing problems. By exploring and integrating inductive biases, we demonstrate that neural networks can be effectively enhanced to address the challenges inherent in the TSP and VRP. The approaches presented in this thesis improve the predictive power of neural solvers and increase their adaptability to various unseen tasks and routing problem distributions. These findings open up promising avenues for future research, potentially driving further advancements in deep learning and its application to complex, real-world problems.