Apprentissage machine et génération de colonnes

Au cours des dernières années, l’apprentissage machine (ML - Machine Learning) a connu un développement sans précédent, surtout après l’émergence de l’apprentissage profond. Le domaine a connu des avancées remarquables qui ont suscité beaucoup d’intérêt auprès des chercheurs de plusieurs disciplines, incluant la communauté de recherche opérationnelle. Récemment, plusieurs travaux cherchant à exploiter les méthodes ML pour résoudre des problèmes d’optimisation combinatoire, ou bien pour accélérer le processus de résolution, ont vu le jour. Ceci a mené au développement de nombreuses méthodes qui ont montré un grand potentiel sur différents problèmes d’optimisation. Dans cette thèse, nous nous intéressons particulièrement à la méthode de génération de colonnes (GC), qui est une méthode d’optimisation utilisée pour résoudre efficacement des programmes linéaires comportant un grand nombre de variables (colonnes). Il s’agit d’une méthode itérative qui commence avec un petit sous-ensemble de variables du programme linéaire original, et génère de nouvelles colonnes au besoin jusqu’à atteindre une solution optimale. La méthode a prouvé son efficacité sur plusieurs problèmes industriels, tels que des problèmes de planification, d’ordonnancement, et de transport. Nous présentons dans cette thèse trois approches différentes pour intégrer l’apprentissage machine dans le contexte de la GC, soit pour accélérer l’optimisation et réduire les temps de calcul des méthodes exactes, ou bien pour développer des heuristiques qui produisent de bonnes solutions en des temps raisonnables. L’objectif général est de tirer profit des données qui sont collectées lors des exécutions antérieures afin d’obtenir des modèles de prédiction, qui seront capables de guider l’optimisation et de réduire l’espace de recherche. Dans le premier sujet, nous proposons une méthode de sélection de colonnes qui, à chaque itération de la GC, applique un modèle de prédiction pour sélectionner un sous-ensemble des colonnes générées. L’objectif est de réduire le temps de calcul consacré à la réoptimisation du problème maître restreint en sélectionnant les colonnes les plus prometteuses. Nous traitons ce problème en utilisant de l’apprentissage supervisé, un classifieur binaire est utilisé pour classer les colonnes générées dans une des deux classes : choisie ou rejetée. La méthode est considérée générale et peut être appliquée à divers problèmes d’optimisation, du moment qu’un grand nombre de colonnes est généré à chaque itération. Nous démontrons l’efficacité de cette approche sur deux applications différentes, à savoir le problème de tournées de véhicules avec fenêtres de temps et le problème d’horaires d’équipages et de véhicules en transport public. Les résultats ont montré un gain en temps de calcul allant jusqu’à 30%. Dans le deuxième sujet, nous nous intéressons aux problèmes résolus avec la GC où le sous-problème est défini sur un graphe et correspond à un problème de plus court chemin avec contraintes de ressources ou une de ses variantes, ce qui est le cas de plusieurs problèmes de planification et de transport. Nous proposons une heuristique pour la résolution du sous-problème, qui consiste à réduire la taille du réseau sous-jacent en sélectionnant les arcs qui ont de grandes probabilités de faire partie d’une solution optimale du problème maître. Un modèle de classification binaire est entraîné sur les données des instances précédemment résolues. Le réseau réduit obtenu à partir des prédictions du modèle est utilisé pour générer de nouvelles colonnes à chaque itération. Puisque les prédictions ne sont pas nécessairement parfaites, et afin d’assurer l’optimalité de la solution obtenue pour le problème maître original, le réseau complet est utilisé dans les dernières itérations pour générer les dernières colonnes. Cette nouvelle approche a été testée sur les mêmes problèmes considérés dans le premier sujet (à quelques changements près) et les résultats ont montré des gains atteignant 40% de réduction en temps de calcul. Dans le troisième sujet, nous développons une heuristique pour la réoptimisation d’un problème après un changement mineur de ses paramètres. Plus précisément, nous considérons le cas du problème de tournées de véhicules avec contraintes de capacité, où les clients sont les mêmes mais avec des demandes légèrement différentes. L’objectif est de prédire les parties de la solution qui ont une grande probabilité de rester inchangées. Au lieu de résoudre le problème à partir de zéro, le solveur peut se baser sur ces prédictions pour réduire l’espace de recherche. Cette prédiction partielle de la solution réduit la complexité du problème et accélère sa résolution, tout en produisant des solutions de bonne qualité. L’approche proposée a été expérimentée sur différentes instances et a permis d’obtenir des solutions avec un écart d’optimalité se situant entre 0% et 1,7%, et ce en des temps de calcul raisonnables.

Abstract

In the last few years, machine learning (ML) has experienced a remarkable development, especially after the emergence of deep learning. The field has seen significant advances that have attracted a lot of interest among researchers from several disciplines, including the operations research community. Recently, several studies seeking to exploit ML methods to solve combinatorial optimization problems, or to accelerate the resolution process, have been conducted. This has led to the development of many methods that have shown great potential on different optimization problems. In this thesis, we are particularly interested in the column generation (CG) method, which is an optimization method used to efficiently solve linear programs involving a large number of variables (columns). It is an iterative method that starts with a small subset of variables from the original linear program, and generates new columns as needed until an optimal solution is obtained. The method has proven its effectiveness on several industrial problems, such as routing and scheduling problems. We present in this thesis three different approaches for integrating machine learning in the context of CG. The goal is either to accelerate the optimization and reduce the computing time of existing methods, or to develop new heuristics that produce good quality solutions in reasonable computing times. The overall goal is to take advantage of the data that can be collected from previous executions, in order to obtain prediction models capable of guiding the optimization and reducing the search space.In the first subject, we propose a column selection method that, at each CG iteration, applies a prediction model in order to select a subset of the generated columns. The goal is to reduce the computing time dedicated to the reoptimization of the restricted master problem by selecting the most promising columns. We tackle this problem using supervised learning, a binary classifier is used to classify the generated columns into one of the two classes : chosen or rejected. The method is considered general enough to be applied to various optimization problems, as long as a large number of columns is generated at each iteration. We demonstrate the effectiveness of this approach on two different applications, namely the vehicle routing problem with time windows, and the crew and vehicle scheduling problem. The results have shown a reduction in computing time of up to 30% on instances of different sizes. In the second subject, we focus on problems solved using CG where the subproblem is defined on a graph and corresponds to a shortest path problem with resource constraints or one of its variants, which is the case of several routing and scheduling problems. We propose a heuristic for solving the subproblem, which consists in reducing the size of the underlying network by selecting the arcs that have a high probability of being part of an optimal solution. A binary classification model is trained on the data of previously solved instances. The reduced network resulting from the model predictions is used to generate new columns at each iteration, as long as it generates a satisfactory number of columns. Since the predictions are not always perfect, and in order to ensure the optimality of the solution obtained for the original master problem, the full network is used when the reduced one fails to generate new columns. This novel approach was tested on the applications considered in the first subject (with some changes to the instances), and the results have shown reductions in computing time of up to 40%. In the third subject, we present a learned heuristic for reoptimizing a problem after a minor change in its data. More precisely, we focus on the case of the capacited vehicle routing problem with static clients (i.e., same client locations) but with slightly different demands. The objective is to predict the parts of the solution that have a high probability of remaining unchanged after a perturbation of the instance data. Instead of solving the problem from scratch, the solver can use the obtained predictions in order to reduce the search space. This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution, while producing good quality solutions. The proposed approach has been demonstrated on different instances and has resulted in solutions with an optimality gap ranging from 0% to 1.7% computed in reasonable computing times.