This thesis presents an exploration into the topic of decision-focused learning (DFL) for network design. The approach represents a novel experiment combining machine learning (ML) with mathematical optimization. In recent years, the progress of DFL has demonstrated success in key optimization problems such as the Knapsack problem. However, the vast amount of existing research deals with optimization structures where unknown parameters are found in the objective function. The primary contribution of this study is to apply a DFL framework to an optimization problem where unknown parameters are found in the constraints. The aim is to apply a DFL approach to the multi-commodity network design (MCND) problem.
We aim to explore the ability of DFL to predict the demand for commodities in the MCND. The study focuses on special loss functions such as Smart Predict then Optimize (SPO) and evaluates how a model makes predictions while accounting for the
downstream optimization where target variables are in the constraints. Through computational experimentation and modifications, we demonstrate the performance of the framework. SPO tends to artificially underpredict demand such that it designs networks that increase operation costs due to its reliance on overflow penalties for realized demands. The underprediction of demand stems from the SPO loss function that focuses on decreasing regret more than prediction errors in this setting. It is clear from the results that SPO is able to learn how to reduce the cost of networks low demand
predictions but does not accurately represent the true demand. In conclusion, this thesis explores the use of DFL in the MCND context. Our research highlights potential developments that DFL could have in mathematical optimization with a motivating example while also testing one of the popular DFL approaches, SPO. While the approach we used was not able to show very promising results, it suggests that DFL does have potential in these types of problems if approaches can be better
customized. / Cette thèse présente une exploration du thème de l’apprentissage centré sur la décision
(DFL) pour la conception de réseaux. L’approche représente une nouvelle solution combinant
l’apprentissage automatique et la programmation mathématique. Ces dernières
années, les progrès de l’apprentissage axé sur les décisions ont été couronnés de succès
dans des problèmes d’optimisation clés tels que le problème du sac à dos. Cependant,
la plupart des recherches existantes traitent des structures d’optimisation où des paramètres
inconnus se trouvent dans la fonction objectif. La principale contribution de cette
étude est d’appliquer un cadre DFL à un problème d’optimisation où des paramètres inconnus
se trouvent dans les contraintes. Plus précisement, l’objectif est d’appliquer une
approche DFL au problème Multi-Commodity Network Design (MCND).
L’étude se concentre sur des fonctions de perte spéciales telles que Smart Predict
then Optimize (SPO) et évalue comment un modèle fait des prédictions tout en tenant
compte de l’optimisation en aval où les variables cibles sont dans les contraintes.
Nous démontrons les performances de ce cadre par le biais d’expérimentations et de
modifications informatiques. SPO a tendance à sous-estimer artificiellement la demande,
de sorte qu’il conçoit des réseaux qui augmentent les coûts d’exploitation en raison de
sa dépendance à l’égard des pénalités de débordement pour les demandes réalisées. La
sous-estimation de la demande est due à la fonction de perte SPO qui se concentre sur
la diminution du regret plutôt que sur les erreurs de prédiction dans ce contexte. Les
résultats montrent clairement que SPO est capable d’apprendre à réduire le coût des
réseaux en prédisant une faible demande, mais qu’il ne représente pas fidèlement la
demande réelle.
En conclusion, cette thèse explore l’utilisation du DFL dans le contexte de SPO pour
MCND. Notre recherche met en évidence les développements potentiels que la DFL
pourrait avoir pour des problèmes de conception de réseau avec un exemple illustratif
tout en testant l’une des approches DFL populaires, SPO. Bien que l’approche que nous
avons utilisée n’ait pas été en mesure de montrer des résultats très prometteurs, elle
suggère que le DFL a du potentiel dans ces types de problèmes si les approches peuvent
être mieux adaptés.
Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/32353 |
Date | 08 1900 |
Creators | Sugiarta, Wisang |
Contributors | Frejinger, Emma |
Source Sets | Université de Montréal |
Language | English |
Detected Language | French |
Type | thesis, thèse |
Format | application/pdf |
Page generated in 0.0029 seconds