90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
- 2021 (5) (remove)
Document Type
- Master's Thesis (5) (remove)
Language
- English (5)
Is part of the Bibliography
- no (5)
Keywords
Institute
Learning to Use Local Cuts
(2021)
We propose a machine learning approach to address a specific algorithmic question that arises during the solving process of a mixed-integer linear programming problem, namely, whether to use cutting planes only at the root node or also at internal nodes of the branch-and-bound search tree, or equivalently, whether to run a cut-and-branch or rather a branch-and-cut algorithm. Within a supervised regression framework, we develop three machine learning models, Linear Model, Random Forest and Neural Network, for predicting the relative performance between the two methods, local-cut and no-local-cut. Hence, through an extensive computational study conducted with FICO Xpress over a large test bed of problems, we evaluate the produced strategies, and we show that they are able to provide, upon the existing policies, a significant improvement to the performance of the solver.
In fact, a variant of the random forest suggested in the present work has already been implemented by the development team of Xpress, and released with version 8.13 of the software.
Die Planung vom Zugumläufen ist eine der wichtigsten Aufgaben für Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle für die Sicherheit und Zuverlässigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und löst — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn für den Schienenpersonenfernverkehr.
Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem beschäftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung präsentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zunächst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gelöst werden und diese Lösung dann verwendet wird, um auf effiziente Art und Weise eine Lösung für das ursprüngliche Problem zu finden. Zur Wartungsplanung nutzt Reuther einen Fluss im Hypergraphen, der den Ressourcenverbrauch der Fahrzeuge modelliert. In der linearen Relaxierung des Modells führt dies dazu, dass die Zahl der notwendigen Wartungen systematisch unterschätzt wird. Dadurch bleibt in vielen Fällen eine große Lücke zwischen dem Zielfunktionswert einer optimalen Lösung des ganzzahligen Problems und der untere Schranke, die uns die lineare Relaxierung liefert.
Wir nehmen uns in dieser Arbeit dieses Problems an. Wir entwickeln ein auf Pfaden basierendes ganzzahliges Modell für das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder schärfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu lösen, entwickeln wir einen Algorithmus, der Spaltengenerierung mit dem Coarse-to-Fine-Ansatz von Reuther verbindet. Weiterhin entwickeln wir eine Spaltenauswahlregel zur Beschleunigung des Algorithmus. Das Modell und alle in der Arbeit vorgestellten Algorithmen wur- den im Rahmen der Arbeit implementiert und mit Anwendungsszenarien der DB Fernverkehr AG getestet. Unsere Tests zeigen, dass unser Modell für fast alle Szena- rien deutlich schärfere untere Schranken liefert als das Modell von Reuther. In den getesteten Instanzen konnten wir durch die Verbesserung der unteren Schranke bis zu 99% der Optimalitätslücke schließen. In einem Drittel der Fälle konnten wir durch unseren Ansatz auch für das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen
For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.
We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic
ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.