Machine Learning Algorithms for Combinatorial Optimization

Une variété de tâches de décision dans la science et l'industrie modernes sont des problèmes d'optimisation combinatoire. Pour résoudre ces problèmes difficiles, des recherches étonnantes ont été menées dans le domaine au cours des dernières décennies. Bien que les méthodes et les techniques d'optimisation développées aient conduit à une multitude d'outils d'optimisation et aient été appliquées avec succès pour résoudre régulièrement un grand nombre de problèmes, il existe encore de nombreux cas pratiques où les techniques existantes ne sont pas adéquates et il est toujours impératif de concevoir et de mettre en œuvre de nouveaux algorithmes et stratégies d'optimisation combinatoire. L'apprentissage automatique est un sous-domaine de l'intelligence artificielle. Ces dernières années, l'application des techniques d'apprentissage automatique dans l'optimisation combinatoire est devenue un domaine de recherche émergent. Dans cette thèse, nous visons à renforcer cette direction et nous soutenons que l'apprentissage automatique est un complément prometteur à l'optimisation combinatoire. Plus précisément, nous étudions différents paradigmes pour appliquer l'apprentissage automatique en combinaison avec l'optimisation combinatoire et présentons trois contributions ci-dessous. Tout d'abord, nous considérons un problème d'optimisation combinatoire spécifique et proposons un cadre pour l'apprentissage d'heuristiques constructives produisant des solutions de haute qualité. Les résultats montrent que notre approche d'apprentissage atteint des performances de généralisation remarquables sur des graphes de plus grande taille et d'une distribution différente. Deuxièmement, nous considérons l'application de l'apprentissage automatique pour les décisions au sein d'algorithmes d'optimisation combinatoire et proposons un cadre d'apprentissage pour prédire et pour adapter la taille du voisinage de l'heuristique, le branchement local, pour la programmation en nombres entiers. Nous montrons informatiquement que les décisions algorithmiques critiques au sein de l'heuristique peuvent en effet être apprises par apprentissage automatique. L'algorithme résultant se généralise bien à la fois au niveau de la taille de l'instance et, remarquablement, entre les instances. Enfin, nous présentons une contribution méthodologique pour l'intégration de l'apprentissage automatique dans les métaheuristiques pour la résolution de problèmes généraux d'optimisation combinatoire. Plus précisément, nous proposons un cadre général d'apprentissage automatique pour la génération de voisins dans la recherche de métaheuristiques. La clé de la méthodologie proposée réside dans la définition et la génération de voisinages de solutions prometteuses. Nous proposons un cadre de classification qui exploite les propriétés structurelles du problème et des solutions de haute qualité et qui sélectionne un sous-ensemble de variables pour définir un voisinage de recherche prometteur pour la recherche métaheuristique. Nous démontrons l'efficacité de notre cadre sur deux schémas métaheuristiques, et les résultats expérimentaux indiquent que notre approche permet d'apprendre un compromis satisfaisant entre l'exploration d'un espace de solutions plus large et l'exploitation de régions locales prometteuses.

Abstract

A variety of decision tasks in modern science and industry are Combinatorial Optimization (CO) problems. To solve challenging CO problems, there has been stunning researches in the f ield over the past decades. Although the optimization methods and techniques developed have led to a vast library of optimization tools and have been successfully applied to routinely solve a large number of CO problems, there are still many practical cases where existing optimization techniques are not adequate and it is always compelling to design and implement new CO algorithms and strategies. In recent years, the application of Machine Learning (ML) techniques in CO became an emerging research area. In this thesis, we aim to reinforce this direction and we argue that ML is a promising complement to CO. Specifically, we study different paradigms for applying ML in combination with CO and present three contributions. First, we consider a specific CO problem, the chordal extension of a graph, and propose a framework for learning heuristic strategies that yield high-quality solutions. In particular, we propose an imitation learning scheme for learning constructive heuristics. The experimental results demonstrate that our approach achieves remarkable generalization performance on graphs of larger size and from a different distribution. Second, we consider the application of ML for making decisions within CO algorithms and propose a learning framework for adapting the crucial parameters of the Local Branching (LB) heuristic for Mixed-Integer Linear Programming (MILP). The resulting ML strategies are integrated into the LB algorithm and interact with the MILP solver. We computationally show that the critical algorithmic decisions within a CO algorithm can indeed be learned by ML, and the resulting algorithms generalize well both with respect to the instance size and, remarkably, across instances. Finally, we present a methodological contribution for integrating ML into metaheuristics (MHs) for solving general CO problems. Specifically, we propose a general ML framework for neighbor generation in MH search. The key of the proposed methodology lies in the definition and generation of promising solution neighborhoods. We propose a framework that exploits structural properties from the problem and from its high-quality solutions, and apply the learned knowledge to define promising neighborhoods for MH search. We validate the effectiveness of our framework on two MH schemes: Tabu Search and Large Neighborhood Search. The experiments show that our approach is able to learn a good trade-off between the exploration of a larger solution space and the exploitation of promising local regions.