Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Machine Learning Approaches to Accelerate Column Generation
Organization Unit
Authors
  • Denys Trieskunov
Supervisors
  • Alexander Souza
  • Sven Seuken
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2023
Abstract Text Column Generation is a method in operations research that allows you to solve large-scale optimization problems. It is mostly used when solving the problem with all variables all at once is either too memory/time-consuming. The method can be divided into two distinct parts: solving the master problem and solving sub-problems. The method itself alternates between the two. The master problem is updated with new columns that are solutions of sub-problems, while sub-problems use updated duals from the latest master problem solution. This loop goes on until the master problem is optimized. Due to the nature of the algorithm as well as the problems it is usually being used to solve, Column Generation often requires a large amount of time to converge and uses a large volume of memory. There are different ways to improve the run-time, as well as several research papers that involve using machine learning for doing it. However, the idea of selecting and executing only sub-problems that would lead to reaching the optimum faster was largely unexplored. In this work, we would like to focus on this particular part of the Column Generation algorithm and show that if we find a way to not run the sub-problems that don’t contribute to master problem convergence, the run-time of the algorithm might be improved. Our approach is to use a Logistic regression model to determine which sub-problems we should execute and which should be dismissed. The features that we use for prediction are simple, scalable, transferable features that can be easily extracted dynamically without sacrificing too much run-time. The model, being an LR model makes predictions rather fast as well. The approach was implemented and tested by adapting the existing Column Generation implementation for solving crew diagramming problems. In our implementation, we enhanced the algorithm by adopting the ML model to execute only sub-problems selected by the model. The original algorithm is developed by Algomia GmbH for Swiss Railways. Our approach was implemented and tested on the same Swiss Federal Railways data the original algorithm uses. The reasoning for this is easier data mining and being able to meaningfully compare our approach to the baseline algorithm.
Zusammenfassung Column Generation ist eine Methode aus dem Bereich Operations Research, mit der sich umfangreiche Optimierungsprobleme bewältigen lassen. Sie wird meist verwendet, wenn die Lösung des Problems mit sämtlichen Variablen gleichzeitig zu speicher- oder zeitaufw ändig ist. Die Methode kann in zwei Teile unterteilt werden: die Lösung des Hauptproblems und die Lösung von Teilproblemen. Die Methode selbst alterniert zwischen diesen beiden Teilen. Das Hauptproblem wird mit neuen Spalten aktualisiert, die Lösungen von Unterproblemen sind, während die Unterprobleme aktualisierte Duale aus der letzten Lösung des Hauptproblems verwenden. Dieser Prozess wird so lange fortgesetzt, bis das Hauptproblem optimiert ist. Aufgrund der Beschaffenheit des Algorithmus und der Probleme, für deren Lösung er normalerweise verwendet wird, benötigt die Spaltengenerierung oft einige Zeit für die Konvergenz und verbraucht eine grosse Menge an Speicherplatz. Es gibt verschiedene Möglichkeiten, die Laufzeit zu verbessern, sowie mehrere Forschungsansätze, bei denen maschinelles Lernen hierfür zum Einsatz kommt. Die Idee, nur Teilprobleme auszuwählen und auszuführen, die dazu führen, dass das Optimum schneller erreicht wird, war jedoch weitgehend unerforscht. In dieser Arbeit möchten wir uns auf diesen speziellen Teil des Column Generation Algorithmus konzentrieren. Dabei soll aufgezeigt werden, dass die Laufzeit des Algorithmus verbessert werden kann, wenn ein eine Methode gefunden wird, die Teilprobleme, die nicht zur Konvergenz des Hauptproblems beitragen, nicht auszuführen. Unser Ansatz besteht darin, ein logistisches Regressionsmodell zu verwenden, um zu bestimmen, welche Teilprobleme ausgeführt und welche abgelehnt werden sollten. Für die Vorhersage verwenden wir einfache, skalierbare und übertragbare Merkmale, die zudem dynamisch extrahiert werden können, ohne dass die Laufzeit zu stark beeinträchtigt wird. Dass es sich dabei um ein LR-Modell handelt, verkürzt die Laufzeiten für die Vorhersagen zusätzlich. Der Ansatz wurde implementiert und getestet, indem die bestehende Column GenerationImplementierung für die Lösung von Crew-Diagramming-Problemen angepasst wurde. In unserer Implementierung haben wir den Algorithmus verbessert, indem wir ein MLModell nutzen, um nur vom Modell ausgewählte Teilprobleme auszuführen. Der ursprüngliche Algorithmus wurde von der Algomia GmbH für die Schweizer Bundesbahnen entwickelt. Unser Ansatz wurde mit denselben Daten der Schweizerischen Bundesbahnen implementiert und getestet, die auch dieser Originalalgorithmus verwendet. Der Beweggrund dafür ist das einfachere Data Mining und die Möglichkeit eines sinnvollen Vergleichs unseres Ansatzes mit dem Basisalgorithmus.
PDF File Download
Export BibTeX