Application of Deep Reinforcement Learning to Routing and Scheduling

Récemment, on a assisté à une montée en puissance des techniques d'apprentissage automatique dans le domaine de l'optimisation. Les méthodes d'apprentissage supervisé peuvent exploiter des structures sous-jacentes dans des multitudes de problèmes et utiliser cette expertise pour aider à trouver plus efficacement la solution de nouvelles instances de ces problèmes. Dans l'apprentissage par renforcement (Reinforcement Learning, RL), cependant, un agent interagit avec l'environnement contrôlé par les contraintes d'un problème d'optimisation. Une fonction de récompense qui s'aligne sur la fonction objectif du problème d'optimisation conduit le processus de recherche itératif à prendre de meilleures décisions pour atteindre la politique optimale. Comme les problèmes d'optimisation combinatoire peuvent généralement être formulés comme des problèmes de prise de décision séquentielle, ils peuvent être modélisés comme des processus de décision de Markov (Markov Decision Process, MDP). L'utilisation de méthodes de recherche exhaustive peut devenir prohibitive pour ces problèmes, c'est pourquoi des méthodes d'apprentissage par renforcement peuvent être utilisées pour les résoudre. En raison de la nature combinatoire de ces problèmes, dans de nombreux cas, les algorithmes de programmation en nombres entiers standard des logiciels de programmation mathématique commerciaux ne peuvent pas résoudre efficacement les modèles correspondants. D'un autre point de vue, de nombreux problèmes issus de cas pratiques réels sont de nature online, ce qui signifie que certaines informations ne sont pas disponibles au départ et qu'elles seront révélées au fil du temps. Dans ce cas, l'information des paramètres stochastiques n'est pas connue à l'avance. L'utilisation de la programmation linéaire mixte en nombres entiers pour ce type de problèmes serait coûteuse en termes de calculs. Néanmoins, les méthodes d'apprentissage par renforcement fonctionnent également très bien pour ces problèmes dynamiques. En outre, la majorité des problèmes d'optimisation combinatoire peuvent être définis sur des graphes. Les récentes avancées dans le domaine de l'apprentissage profond, en particulier les réseaux de neurones graphiques, ont permis de remarquer l'application des méthodes d'apprentissage par renforcement à ces problèmes. Les réseaux neuronaux graphiques capturent l'information relationnelle cachée entre tous les éléments (nœuds et arêtes) des graphes pour faire de meilleures prédictions. Dans cette thèse, nous tirons parti de l'apprentissage par renforcement et des réseaux neuronaux graphiques pour développer des algorithmes efficaces pour les problèmes d'optimisation combinatoire dans diverses applications. Dans le premier projet, nous développons une méthode d'apprentissage profond par renforcement pour trouver les meilleures orientations de faisceaux pour irradier les patients sous radiothérapie pour le traitement du cancer en utilisant le système Cyberknife. Nous trouvons simultanément la trajectoire pour les traverser afin de réduire le temps de traitement tout en maintenant la qualité du traitement par rapport à l'utilisation de toutes les orientations possibles du faisceau. En utilisant l'agent entraîné, nous pouvons générer des plans de traitement spécifiques au patient au lieu d'utiliser un ensemble fixe de faisceaux pour chaque patient et chaque site cancéreux. À cette fin, nous représentons le problème par un graphe et appliquons des réseaux neuronaux de graphe pour apprendre une nouvelle représentation du graphe et les caractéristiques de ses éléments correspondants. Grâce à cette méthode, nous pouvons utiliser de nombreuses caractéristiques différentes concernant l'anatomie des patients et les informations dosimétriques. Nous proposons un algorithme de Q-Learning profond pour entraîner un agent à sélectionner un sous-ensemble de faisceaux et l'ordre dans lequel les visiter. Les résultats sont ensuite transmis à un problème d'optimisation directe de l'ouverture où d'autres paramètres de traitement sont calculés. Les résultats montrent que l'utilisation de la méthode proposée réduit le temps de traitement tout en maintenant la qualité du traitement par rapport aux traitements cliniques de base. Dans le deuxième projet, nous proposons un algorithme d'apprentissage par renforcement profond basé sur les réseaux de neurones graphiques pour résoudre le problème de routage dynamique et d'affectation de longueurs d'onde dans un contexte de problème d'optimisation des réseaux de télécommunications. Les demandes de trafic entrant arrivent dynamiquement en suivant une distribution inconnue. Nous modélisons ce problème comme un MDP. En raison de la nature dynamique du problème, nous développons un algorithme RL profond avec l'objectif de maximiser les demandes de trafic admises. Les résultats montrent que l'algorithme proposé est plus performant que les heuristiques largement utilisées (tant dans la littérature de recherche que dans la pratique). En adoptant cet algorithme, nous fournissons un modèle qui résout le routage et l'affectation des ressources (longueurs d'onde) en même temps. Nous considérons un cas d'information parfaite, où toutes les informations sont connues de l'optimiseur, et avons formulé un modèle de programmation mathématique résolu avec des solveurs commerciaux comme base de référence (limite supérieure) pour comparer les résultats de l'algorithme. Dans le troisième projet, nous abordons le problème d'ordonnancement dynamique sous contraintes multi-ressources qui découle d'un problème réel dans l'industrie. Nous considérons un cas où chaque tâche a une date limite spécifique et une date d'expiration. Nous appliquons des Q-Networks avec approximation de fonction pour générer des solutions qui minimisent les coûts totaux de retard et les coûts d'expiration. Nous définissons d'abord le problème comme un graphe et attribuons plusieurs caractéristiques à chaque nœud. Pour capturer toutes les relations latentes entre les éléments, nous appliquons des Graph Attention Networks comme décodeurs pour apprendre une nouvelle représentation du graphe d'entrée à chaque instant de décision. L'agent RL sélectionne une tâche (parmi l'ensemble des tâches arrivées) et lui affecte des ressources afin de minimiser les pénalités cumulées attendues. Nous comparons les résultats avec différentes méthodes de la littérature. Nous formulons également le problème avec une information parfaite à l'aide de la programmation par contraintes, afin d'obtenir une borne inférieure pour les solutions.

Abstract

Recently there has been a surge to benefit from machine learning techniques in the field of optimization. Supervised learning methods can infer the innate patterns in multitudes of problems and use that expertise to help find the solution for new instances of the problems more efficiently. In Reinforcement Learning (RL), however, an agent interacts with the environment that is controlled by the constraints of an optimization problem. A reward function that aligns with the objective function of the optimization problem drives the iterative search process toward making better decisions to reach the optimal policy. Since Combinatorial Optimization (CO) problems can generally be formulated as sequential decision-making problems, they can be modeled as Markov Decision Process (MDP). Employing exhaustive search methods can become prohibitive for these problems, therefore RL methods can be employed to solve them. Because of the combinatorial nature of these problems, in many cases, standard integer programming algorithms in commercial mathematical programming software packages cannot solve the corresponding models effectively. From another point of view, many problems that arise from real practical cases are online in nature, meaning that some of the information is not available at the beginning, and they will be revealed as time goes on. In this case, the information of the stochastic parameters is not known in advance. Using Mixed Integer Linear Programming (MILP) for these kinds of problems would be expensive in terms of computations. Nevertheless, Reinforcement Learning methods perform very well for these dynamic problems as well. In addition, the majority of Combinatorial Optimization problems can be defined over graphs. Recent advances in deep learning in particular Graph Neural Networks (GNN) have led to a noticeable improvement in the application of Reinforcement Learning methods in these problems. GNNs capture the hidden relational information among all the elements (nodes and edges) of the graphs to make better predictions. In this dissertation, we take advantage of RL and GNN to develop efficient algorithms for CO problems in diverse applications. In the first essay, we develop a deep RL method to find the best beam orientations to irradiate the patients undergoing radiation therapy for cancer treatment using the Cyberknife system. We simultaneously find the trajectory to traverse them in order to reduce the treatment time while maintaining the quality of the treatment compared to using all the possible beam orientations. Using the trained agent, we can generate patient-specific treatment plans instead of using a fixed set of beams for every patient and every cancer site. To this end, we represent the problem over a graph and apply GNNs to learn a new representation of the graph and the features of its corresponding elements. Using this method, we can use many different features concerning the anatomy of the patients and the dosimetric information. We propose a deep Q-Learning algorithm to train an agent to select a subset of the beams and the order to visit them. The results are then forwarded to a Direct Aperture Optimization (DAO) problem where other treatment parameters are calculated. The results show that using the proposed method reduces the treatment time while maintaining the quality of the treatment compared to the clinical treatment baselines. In the second essay, a GNN-based deep RL algorithm is proposed to solve the dynamic Routing and Wavelength Assignment (RWA) problem in the context of telecommunications network optimization problems. The incoming traffic requests arrive dynamically following an unknown distribution. We model this problem as a MDP. Due to the dynamic nature of the problem, we develop a deep RL algorithm with the objective of maximizing the admitted traffic requests. The results show that the proposed algorithm outperforms the widely used heuristics (both in the research literature and in practice). By adopting this algorithm, we provide a model that solves the routing and resource (wavelength) assignment at the same time. We consider a case with the perfect information, where all the information is known to the optimizer, formulated a mathematical programming model of this problem, and solved it with commercial solvers as a baseline (upper bound) to compare the results of the algorithm. In the third essay, we address a dynamic multi-resource constrained scheduling problem that arises from a real problem in the industry. We consider a case where each job has a specific deadline and an expiration date. We apply Q-Networks with function approximation to generate solutions that minimize the total tardiness costs and expiration costs. We first define the problem as a graph and assign several features to each node. To capture all the latent relations among elements, we apply Graph Attention Networks as a decoder to learn a new representation of the input graph at each decision time. The RL agent selects a job (from the set of arrived jobs) and assigns resources to it in order to minimize the cumulative expected penalties. We compare the results with different methods in the literature. We also formulate the problem with perfect information with Constraint Programming (CP), to achieve a lower bound for the solutions.