Machine learning accelerated stochastic optimization and applications to railway operations
Thèse ou mémoire / Thesis or Dissertation
Date de publication
Autrices et auteurs
Identifiant ORCID de l’auteur
Contributrices et contributeurs
Direction de recherche
Publié dans
Date de la Conférence
Lieu de la Conférence
Éditeur
Cycle d'études
Doctorat / Doctoral
Programme
Affiliation
Mots-clés
- programmation stochastique
- apprentissage automatique supervisé
- L-shaped method
- stochastic instance generator
- programmation en nombres entiers
- décomposition de Benders
- méthode L-shaped
- générateur d’instances stochastiques
- stochastic programming
- supervised machine learning
- integer programming
- Benders decomposition
Organisme subventionnaire
Résumé
Résumé
Nous proposons des innovations méthodologiques combinant l’apprentissage automatique (AA) et la recherche opérationnelle (RO) où des prédicteurs issus de l’AA supervisé sont entraînés hors-ligne et introduits dans des algorithmes de RO pour accélérer les calculs en-ligne. La synergie entre RO et AA est particulièrement avantageuse pour la programmation stochastique. Nous concentrant sur les problèmes de décision à deux étapes, nous vérifions que des prédictions de la solution de deuxième étape (DE) améliorent considérablement le compromis entre exactitude et vitesse des calculs. Nous éprouvons nos propositions sur des applications réalistes et des problèmes standardisés. La thèse comprend cinq articles: The Load Planning Problem for Double-stack Intermodal Trains traite en contexte réaliste le problème opérationnel déterministe de chargement optimal (PCO) de conteneurs sur des wagons doublement étagés. Il établit en outre les bases des applications de l’AA à la RO examinées dans les deux articles suivants où l’apprentissage se fonde sur des paires entrée-sortie joignant une instance déterministe du PCO à sa solution exacte. Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information emploie l’AA hors-ligne pour accélérer la programmation stochastique à deux étapes lorsque DE est difficile. Les prédictions d’AA de la solution espérée de DE, conditionnelles aux variables de première étape (PE), obvient à la génération de scénarios et au calcul de solutions en DE. Elles produisent des solutions globales avec plus d’exactitude et de vitesse en-ligne que les méthodes alternatives. Une application à une version tactique du PCO est présentée. A Language Processing Algorithm for Predicting Tactical Solutions to an Operational Planning Problem Under Uncertainty démontre l’usage d’un algorithme de traduction neural pour générer des prédictions rapides et fidèles de solutions détaillées d’un problème stochastique de décision. Il décrit comment établir les vocabulaires et les syntaxes, introduire des contraintes portant sur la relation d’entrée-sortie ou sur les sorties. Il définit une mesure de discordance et un prédicteur de référence. Une application au PCO est présentée. Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning présente une matheuristique résolvant un programme stochastique linéaire à deux étapes avec variables mixtes. Il démontre comment la substitution de solutions d’AA au sous-problème de Benders pour le calcul de coupes d’optimalité L-shaped entières et continues permet un compromis avantageux entre exactitude et temps de calcul en-ligne. Les temps sont indépendants du nombre de scénarios et le prédicteur d’AA est valide pour des familles de problèmes paramétrées. Une application à des familles dérivées de problèmes stochastiques standard de localisation de serveurs et de sac-à-dos multiple est présentée. Pseudo-random Instance Generators in C++ for Deterministic and Stochastic Multi-commodity Network Design Problems présente des générateurs simulant une large gamme de problèmes de conception de réseau déterministes et stochastiques avec multiples classes d’objets, capacités et coûts fixes. Il vise à faciliter l’évaluation et la comparaison de méthodes de solution exactes et heuristiques, notamment usant de l’AA, et à favoriser la reproductibilité et la comparabilité de résultats publiés.
We present methodological innovations at the intersection of machine learning (ML) and operations research (OR) where predictions from generic input-output map approximators originating from supervised ML are trained offline and introduced within OR algorithms to accelerate online computations. We demonstrate that the synergy between OR and ML can be highly advantageous for stochastic programming. Concentrating on two-stage stochastic decision problems, we verify that, by introducing at the first stage (FS) predictions about the expected solution of second stage (SS), the trade-off between accuracy and online computational speed attained by the overall solution process can be considerably improved. We test our ideas upon realistic applications and standardized problems. The thesis comprises five articles: The Load Planning Problem for Double-stack Intermodal Trains addresses in a realistic setting the deterministic operational load planning problem (LPP) of optimally loading intermodal containers onto double-stack railcars. While this has intrinsic interest, it also establishes the foundations of the applications of ML to OR considered in the next two articles. There, ML relies on input-output pairs joining a deterministic LPP instance with its exact solution. Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information employs offline ML to accelerate two-stage stochastic programming when the SS is computationally demanding. ML predictions of the expected solution of the SS problem, conditional on FS variables, avoid online SS generation of scenarios and solution and yield overall solutions with greater accuracy and online speed than otherwise achievable. An extensive application to a tactical version of the LPP is examined. A Language Processing Algorithm for Predicting Tactical Solutions to an Operational Planning Problem Under Uncertainty demonstrates the use of a neural machine translation algorithm for generating fast and accurate predictions of solutions to a complex and detailed stochastic discrete decision problem. It describes how to specify the input and output vocabularies and syntaxes, enforce constraints restricting the input-output map or the output, and define a measure of discrepancy and a baseline. An extensive application to the LPP is presented. Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning presents a matheuristic solving linear two-stage stochastic programs where integers appear in both stages. It demonstrates large reductions in online solution time while incurring small reductions in overall accuracy by substituting ML solutions for the Benders subproblems and calculating approximate integer and continuous L-shaped optimality cuts. Computation times are independent of number of scenarios and the ML predictor is valid for parameterized families of problems. An extensive application to families of problems derived from standard classes of stochastic server location and stochastic multi knapsack problems is presented. Pseudo-random Instance Generators in C++ for Deterministic and Stochastic Multi-commodity Network Design Problems fills a gap in the literature on network design, introducing flexible and high-speed generators capable of simulating a wide range of settings for the deterministic and stochastic multi-commodity, capacitated, fixed charge network design problems. We aim to facilitate systematic experimentations, leading to more thorough assessments of performance of exact and heuristic solution methods, and to foster reproducibility and comparability of published research.
We present methodological innovations at the intersection of machine learning (ML) and operations research (OR) where predictions from generic input-output map approximators originating from supervised ML are trained offline and introduced within OR algorithms to accelerate online computations. We demonstrate that the synergy between OR and ML can be highly advantageous for stochastic programming. Concentrating on two-stage stochastic decision problems, we verify that, by introducing at the first stage (FS) predictions about the expected solution of second stage (SS), the trade-off between accuracy and online computational speed attained by the overall solution process can be considerably improved. We test our ideas upon realistic applications and standardized problems. The thesis comprises five articles: The Load Planning Problem for Double-stack Intermodal Trains addresses in a realistic setting the deterministic operational load planning problem (LPP) of optimally loading intermodal containers onto double-stack railcars. While this has intrinsic interest, it also establishes the foundations of the applications of ML to OR considered in the next two articles. There, ML relies on input-output pairs joining a deterministic LPP instance with its exact solution. Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information employs offline ML to accelerate two-stage stochastic programming when the SS is computationally demanding. ML predictions of the expected solution of the SS problem, conditional on FS variables, avoid online SS generation of scenarios and solution and yield overall solutions with greater accuracy and online speed than otherwise achievable. An extensive application to a tactical version of the LPP is examined. A Language Processing Algorithm for Predicting Tactical Solutions to an Operational Planning Problem Under Uncertainty demonstrates the use of a neural machine translation algorithm for generating fast and accurate predictions of solutions to a complex and detailed stochastic discrete decision problem. It describes how to specify the input and output vocabularies and syntaxes, enforce constraints restricting the input-output map or the output, and define a measure of discrepancy and a baseline. An extensive application to the LPP is presented. Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning presents a matheuristic solving linear two-stage stochastic programs where integers appear in both stages. It demonstrates large reductions in online solution time while incurring small reductions in overall accuracy by substituting ML solutions for the Benders subproblems and calculating approximate integer and continuous L-shaped optimality cuts. Computation times are independent of number of scenarios and the ML predictor is valid for parameterized families of problems. An extensive application to families of problems derived from standard classes of stochastic server location and stochastic multi knapsack problems is presented. Pseudo-random Instance Generators in C++ for Deterministic and Stochastic Multi-commodity Network Design Problems fills a gap in the literature on network design, introducing flexible and high-speed generators capable of simulating a wide range of settings for the deterministic and stochastic multi-commodity, capacitated, fixed charge network design problems. We aim to facilitate systematic experimentations, leading to more thorough assessments of performance of exact and heuristic solution methods, and to foster reproducibility and comparability of published research.
Table des matières
Notes
Notes
Autre version linguistique
Ensemble de données lié
Licence
Approbation
Évaluation
Complété par
Référencé par
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Sauf si le document est diffusé sous une licence Creative Commons, il ne peut être utilisé que dans le cadre d'une utilisation équitable et non commerciale comme le prévoit la Loi (i.e. à des fins d'étude privée ou de recherche, de critique ou de compte-rendu). Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.