Hybrid TSP Solver: Combining Traditional Optimization Techniques and Neural Networks

The purpose of this thesis is twofold. First, it aims to analyze and demonstrate the relationship between two fields that may appear to be very far apart: combinatorial optimization and machine learning. Second, it seeks to combine these two fields to create an hybrid solver for the TSP problem. To accomplish these goals, the thesis is divided into three parts, each covering a specific topic: - Part I: this section demonstrates how classical optimization techniques are widely used in deep learning. It includes an extensive discussion of descent methods used to train neural networks; - Part II: this section highlights how recent deep learning models have attempted to improve the classical resolution of NP-hard problems, such as the TSP; - Part III: this section explains the idea and the implementation of an hybrid TSP solver that combines a classical branch and bound algorithm for the symmetric TSP with Graph Neural Networks. The thesis concludes with considerations on potential future work and improvements.