Using Machine Learning to solve Combinatorial Optimization problems

You are cordially invited to attend the PhD Dissertation Defence of Umberto Junior Mele on Thursday 11 April 2024 at 10:30 in room D0.02

Abstract:
Combinatorial Optimization (CO) is experiencing a significant transformation with the emergence of a new generation of Machine Learning (ML) based algorithms. These new algorithms extract patterns from previously solved instances of a problem and apply them to solve new instances more efficiently. In certain circumstances, ML-based approaches have the potential to surpass conventional methods in terms of computational cost and solution quality, as discussed in this Ph.D. dissertation. Here, the author provides an extensive overview of some notable recent algorithms, with a focus on three main approaches: Constructive heuristics, Local Searches, and techniques for reducing search space. A significant innovation detailed in this thesis is the development of the ML-Constructive heuristic, a method crafted to mitigate the biases inherent in typical ML applications. In CO problems, the best solutions often have certain common characteristics. For example, when trying to minimize the distance of vehicle routes (a typical CO problem), cities that are geographically closer to each other are more likely to be paired in the most efficient route. When ML models are trained on datasets with such problems, they tend to learn to prefer these common, shorter connections because they occur more frequently in the data. This creates a bias; the model becomes more likely to ignore less common solutions that involve longer routes, even though these solutions might sometimes be optimal. The bias mentioned here is the ML model's tendency to over-fit to the most common patterns seen in the training data. The ML-Constructive heuristic introduces a novel approach to balance this bias. It integrates ML-derived predictions with optimization strategies to produce solutions that demonstrate less bias and stronger generalizability. This means that even if the heuristic is trained on small-scale instances, it is capable of scaling up and finding high-quality solutions for larger-scale problems as well. By recognizing and incorporating these nuances, the ML-Constructive not only perform exceptionally well in traditional TSP, but also paves the way for innovative solutions in more complex variations of the problem. When this research was introduced, it was among the most advanced methods for applying constructive heuristics to solve the TSP.

Dissertation Committee:
- Prof. Luca Maria Gambardella, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Cesare Alippi, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Piotr Krzysztof Didyk, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Gianni A. Di Caro, CMU (External Member)
- Prof. Olivier Gallay, Université de Lausanne, Switzerland (External Member)