Bachelor's Thesis
Refine
Year of publication
Document Type
- Bachelor's Thesis (69) (remove)
Is part of the Bibliography
- no (69)
Keywords
- Benchmark (1)
- Flow Visualization (1)
- HDFS (1)
- Hadoop (1)
- Primal Heuristics, MIP, mixed integer programming, ZI Round, Shift-and-Propagate, optimization (1)
- Uncertainty quantification, Gaussian random fields, ridge, feature detection (1)
- XtreemFS (1)
- distributed storage systems (1)
- dynamic reconfiguration (1)
- replication (1)
Institute
- Mathematical Optimization (28)
- Numerical Mathematics (14)
- Visual Data Analysis (14)
- Visual and Data-centric Computing (14)
- Distributed Algorithms and Supercomputing (8)
- Computational Molecular Design (5)
- Mathematical Optimization Methods (4)
- Therapy Planning (4)
- Visual Data Analysis in Science and Engineering (4)
- Bioinformatics in Medicine (2)
Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.
Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, für gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschränkungen, die zu erfüllen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrplänen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabläufen.
Mathematisch können diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur Lösung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zunächst die notwendigen graphentheoretischen Grundlagen und das PESP eingeführt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Dafür ist eine weitere Nebenbedingung nötig.
Im fünften Kapitel behandeln wir die Lösung des teildualisierten PESP. Eine Möglichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschränken. Eine weitere Möglichkeit ist ein Algorithmus, derähnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet.
Common models and solving approaches for the problem of periodic timetabling, that is, determining periodic arrival and departure times of a given public transportation network’s lines so that the total weighted travel time of all passengers is minimized, fail to take passenger behavior into account. Current research is attempting to resolve this issue and first results show a positive impact on solution quality. This thesis aims to give a brief overview of literature on the topic of timetabling and to then state a heuristic approach to Integrated Timetabling by blending passenger behavior into the Modulo Network Simplex algorithm, which is part of the research carried out by the author’s study group at the Zuse Institut Berlin in the framework of MATHEON’s research project MI-3 supported by the Einstein Foundation Berlin.
Prediction and Analysis of Drugs Inducing Liver Injury (DILI) using ProTox-II Computational-Tool
(2019)
In order to better understand the relationship between shape of the nasal cavity and to find objective classification for breathing obstruction, a population of 25 cases of healthy nasal cavity and 27 cases with diagnosed nasal airway obstruction (NAO) was examined for correlations between morphological, clinical and CFD parameters. For this purpose a workflow was implemented in Tcl to perform automatic measurements of morphological parameters of nasal cavity surfaces in Amira, which has as output a table with all estimated values. Furthermore, the statistical analysis was designed using Python to find the most probable subset of parameters that are predictors of nasal cavity pathology and consisted of correlation analysis, the selection of the best possible subset of parameters that could be used as predictors of clinically stated pathology of the nasal cavity by a logistic regression classifier. As a result, 10 most promising parameters were identified: mean distance between the two isthmuses, left isthmus contour, area ratio between the two isthmuses, left isthmus height, height ratio between the two isthmuses, left isthmus width, right isthmus width, right isthmus hydraulic diameter, mean distance of septal curvature between the septum enclosing walls of the nasal cavity, velocities volume average by expiration. As it turns out, most parameters refer to the isthmus region. This was to be expected since this region
plays an important role in the airflow system of the nasal cavity.
In this thesis, I want to analyze how neural networks trained to resemble a given function based on particular values react to additional knowledge about the function in terms of a differential equation that the function satisfies.
In the first chapter, I will recall the definition of initial value problems and discuss the existence and uniqueness of their solutions, as well as touch on a method to numerically approximate them. Furthermore, I will give a mathematical introduction to neural networks.
Then, I will consider a system of two first-order differential equations and test how their solution will be approximated by a neural net. In the next step, I want to see how added noise to the training data and the influence of the differential equation on the loss functional of the neural net will affect the error of the predicted solution against the exact data. Furthermore, I will test if this influence can help reduce the amount of necessary data points in order to reach similar degrees of accuracy.
This thesis deals with a new algorithm for finding Shortest Paths on Airway Networks. It is about a Bidirectional A* Search, a Greedy algorithm exploring a network from two sides instead of one. We will use it to solve the so-called 'Horizontal Flight Trajectory Problem', where one searches for an aircraft trajectory between two airports of minimal costs on an Airway Network. The given network will be modeled as a directed graph and in order to reflect reality we concentrate on the dynamic version. Here a timedependent cost function for all arcs is integrated, that shall represent the winds blowing. This way we model the Horizontal Flight Trajectory Problem mathematically as a Time-Dependent Shortest Path Problem.
The basic algorithm idea derives from the algorithm presented in 'Bidirectional A* Search on Time-Dependent Road Networks' [1], where a similar setting is elaborated for road networks. The algorithm procedure bears on a modified generalization of Dijkstra's algorithm, made bidirectional and improved in several aspects. As for the backwards search the arrival times are not known in advance, the reversed graph it occurs on has to be weighted by a lower bound. Contrary to the static case the forwards search still has to go on, when they 'meet' in one node. In the static case, the shortest path would have been found at this point.
For road networks the TDSPP is well-studied, for airway networks cannot be found as much in literature. In order to test efficiency, we implement Dijkstra's algorithm, unidirectional A* Search and Bidirectional A* Search. We draw up how potential functions for the static case could look like and that with a suitable potential A* Search with works approx. 7 times faster than Dijkstra in the dynamic case. Our computations lead also to the result, that the unidirectional A* Search works even better on the network than our new bidirectional approach does. On average it labels fewer nodes and also yields 1,7 times faster to the solutions.
For assessing the efficiency of the different algorithms we compare the running times and to exclude processor characteristics we consider also the set labels relative to the labels on the resulting optimal path. In addition, we present examples of routes visually
and explain shortly why there appear local differences regarding performance of A* Search and Bidirectional A* Search.
The aim of multimodal routing is to extract the best integrated journey of multiple
transportation networks. The integration of bike rental networks is challenging
particularly with respect to recognizing a valid path dependent on real-time
availability of bike boarding and alighting places. In this work a common model
for station-based bike rental networks extended with boarding possibilities for
free floating bikes is presented. Moreover a new model for alighting inside a free
floating area is introduced. In addition, a prototype of multimodal routing with
a bike rental network in Berlin is developed by extending the OpenTripPlanner
software. Due to recent public dispute about bike rental networks in Berlin, an
examination about speed-up potential of an integrated bike rental network in the
public transit of Berlin is provided.
Das Wind-Interpolation-Problem (WIP) ist ein bisher selten diskutiertes Problem der Flugplanungsoptimierung, bei dem es darum geht, Wind-Komponenten auf einer Luftstraße zu approximieren. Anhand von Winddaten, die vektoriell an den Gitterpunkten eines den Globus umspannenden Gitters vorliegen, soll bestimmt werden, wie viel Wind entlang der Luftstraße und quer zu ihr weht. Thema dieser Arbeit ist ein Spezialfall des WIP, nämlich das statische WIP auf einer Planfläche (SWIPP). Dazu wird zuerst ein Algorithmus besprochen, der das SWIPP zwar löst, aber einem Ansatz zugrunde liegt, der bei genauerem Hinsehen nicht sinnvoll erscheint: hier wird Wind zwischen vier Punkten interpoliert, wozu es keine triviale Methode gibt. Ähnlich zu diesem Algorithmus, der heute als State-of-the-Art gilt, wird als Ergebnis dieser Arbeit ein neuer Algorithmus vorgestellt, der das SWIPP akkurater und schneller löst. Hier wird deutlich seltener
auf die Interpolation zwischen vier Punkten zurückgegriffen - stattdessen wird fast immer linear zwischen zwei Punkten interpoliert. Die Algorithmen zum Lösen des SWIPP werden auf ihre Genauigkeit,
asymptotische Laufzeit und Geschwindigkeit untersucht und verglichen. Als Testareal dienen zum einen echte Wetterdaten sowie das Luftstraßennetz, das die Erde umspannt, und zum anderen ein eigens generiertes Windfeld und fiktive Luftstraßen. Es wird gezeigt, dass der hier vorgestellte Algorithmus die State-of-the-Art-Variante in allen genannten Aspekten übertrifft.
Mit dem Voranschreiten der Technologie erhalten die öffentlichen Verkehrsmittel eine größere Bedeutung. Die Beförderung mehrerer Personen eröffnet der Gesellschaft viele Möglichkeiten, unter Anderem den Vorteil der Zeitersparnis. Die Dauer des Verkehrswegs mit öffentlichen Verkehrsmitteln ist häufig geringer, als die mit individuellen Verkehrsmitteln. Jedes öffentliche Transportmittel ist mit einem Fahrplan versehen. Dieser bietet Passagieren, die öffentliche Verkehrsmittel öfter nutzen, eine Strukturierung und Planung ihrer Zeit. Dabei lassen sich Taktfahrpläne aufgrund ihres periodischen Verhaltens leicht einprägen. Dieses periodische Verhalten ist durch mathematische Modellierungen darstellbar. Das persönliche Nutzverhalten vieler Bürger im Personenverkehr ist auf die öffentlichen Verkehrsmittel beschränkt. Diese beinhalten im Gegensatz zum individuellen Verkehrsmittel eine Wartezeit. Dabei stellt sich die Frage, ob man anhand mathematischer Modelle diese Wartezeit minimieren kann. Eine bekannte mathematische Modellierung dieses Problems ist das Periodic Event Scheduling Problem (PESP). Die optimale Planung eines periodischen Taktfahrplanes steht im Vordergrund.
Während ich dieses Problem betrachtet habe, wurde ich auf das Rechnen mit linearen Gleichungssystemen modulo T aufmerksam. Bei periodischen Taktfahrplänen wird ein einheitliches zeitliches Muster, welches sich nach T Minuten wiederholt, betrachtet. Das dabei zu betrachtende Lösungsproblem eröffnet ein Teilgebiet der Mathematik, welches bislang nicht im Vordergrund stand: Das Lösen linearer Gleichungen modulo T, wobei T für die Zeit in Minuten steht und somit 60 ist. Da 60 keine Primzahl ist, kann – wie im Laufe der Arbeit präsentiert – das lineare Gleichungssystem nicht mehr über einen Körper gelöst werden. Lineare Gleichungssysteme werden nun über Nicht-Körpern betrachtet. Die Literatur weist sowohl im deutschsprachigem als auch im englischsprachigen Raum wenig Umfang bezüglich linearer Gleichungssysteme über Nicht-Körper auf. Der Bestand an Fachliteratur bezüglich den Themen lineare diophantische Gleichungssysteme, Hermite-
Normalform und Smith-Normalform ist zurzeit gering, dennoch erreichbar, beispielsweise in [1], welches in dieser Bachelorarbeit genutzt wurde. Insbesondere wurde ich bei der Suche nach geeigneter Literatur zu linearen Gleichungssystemen über Restklassenringe, die keinen Körper bilden, nicht fündig. Dabei recherchierte ich sowohl in den Universitätsbibliotheken als auch in webbasierenden Suchmaschinen.
Aufgrund dem geringen Bestand an Fachliteratur in diesem Kontext, war ich gezwungen, an vielen Stellen eigene logische Verknüpfungen zu konzipieren und zu beweisen. Dies brachte viele Schwierigkeiten mit sich, die mit bestmöglichem Verständnis bearbeitet wurden.
Abseits der Zugänglichkeit der Literatur, finde ich es sehr überraschend, dass sich viele Professoren der Mathematik mit diesem Themenbereich nicht beschäftigten. Insbesondere gingen von den Dozenten, die ich um Literaturempfehlung bat, kein Werk aus. Damit
wurde das Thema "Lineare Gleichungssysteme Modulo T" einerseits eine große Herausforderung, andererseits eine große Motivation, da ich mit dieser Bachelorarbeit vielen Interessenten der Mathematik als Sekundärliteratur dienen kann.
Der Einfluss von Langzahlarithmetik auf das Gewichtsraumpolyeder in mehrkriterieller Optimierung
(2018)
Die Arbeit befasst sich mit einem gewichtsraumbasierten Algorithmus, der ganzzahlige und lineare Optimierungsprobleme mit mehreren Zielfunktionen
löst und die Menge der unterstützt nicht dominierten Punkte ermittelt. Die dabei erzeugten Gewichtsraumpolyeder sind das entscheidende Mittel, um die gesuchte Lösungsmenge zu bestimmen. Aus softwaretechnischer Sicht sind numerische Ungenauigkeiten potentielle Fehlerquellen, die sich negativ auf das Endergebnis auswirken. Aus diesem Grund untersuchen wir anhand von Zuweisungs- und Rucksackinstanzen mit 3 Zielfunktionen, inwieweit der Gebrauch von Langzahlarithmetik die Gewichtsraumpolyeder und die damit verbundene Menge der unterstützt nicht dominierten Punkte beeinflusst.
I consider models of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, my aim is to identify from a set of operation modes those that are infeasible or redundant. For this, I investigate optimization and network reduction based procedures. Ultimately, these procedures may be employed for data preprocessing in the context of gas network optimization.
Moderne CPU-Architekturen erfordern die Verwendung von Vektorinstruktionen, um die vorhandene Leistung vollständig auszuschöpfen. Aktuelle Compiler bieten Möglichkeiten zur automatischen Vektorisierung von Programmcode. Im Rahmen dieser Arbeit werden an Testfällen verschiedene Compiler auf ihre Fähigkeiten zur Autovektorisierung getestet und evaluiert, um Stärken und Schwächen der jeweiligen Compiler aufzuzeigen. Es werden Laufzeitergebnisse und Vektorisierungsvermögen miteinander verglichen und eine Empfehlung in Abhängigkeit des jeweiligen Anwendungsfalls gegeben.
Diese Bachelorarbeit beschäftigt sich mit der Entwicklung eines allgemeinen Verfahrens, welches die Dicke der mineralisierten Schicht von Haikieferelementen automatisch bestimmt. Dabei soll das Verfahren die Dicke näherungsweise im zweidimensionalen (2D) Raum sowie im dreidimensionalen (3D) Raum anhand von Computertomografie-Scans berechnen (im Folgenden als zweidimensionaler bzw. dreidimensionaler Fall bezeichnet).
Es werden drei mögliche Verfahren eingeführt und im Anschluss auf ihre Verwendbarkeit analysiert. Für die Implementierung zur Dickenbestimmung wird der Kern der Rayburst Sampling Methode verwendet und im Weiteren für den 2D-Raum durch kleinere Optimierungen verbessert. Die Überprüfung der Genauigkeit des für den zweidimensionalen Fall entwickelten Programms erfolgt manuell. Für einen Vergleich im 3D-Raum wird ein zweites Verfahren programmiert, das auf der Berechnung der Isoflächen basiert.
Diese Arbeit ist in den Bereich der angewandten Mathematik mit dem Schwerpunkt Informatik einzuordnen. Das entwickelte Programm wird im Anschluss Anwendung im Bereich der Biologie am Max-Planck-Institut für Grenzflächen- und Kolloidforschung Potsdam-Golm finden.
Scientific conferences play an important role in almost all areas of today’s science and
research. They offer a wide platform for international researchers and developers for
communication and scientific exchange of current problems, experiences and knowledge
in nearly all fields of research. Such conferences usually consist of talks about different
topics that are given by authorized speakers. The planning process of a conference
includes the creation of a scientific program schedule, that means a local and temporal
allocation of all available talks.
As the number of talks can grow into thousands for large-scale conferences, the
conference scheduling becomes a complex challenge. Furthermore there exist a great
bandwidth on various and individual requirements on the allocation of the talks. In this
thesis we discuss the major problems that occur during the development of a conference
schedule and provide a framework how proper conference schedules can be generated
computationally. For that, we use Mixed-Integer-Programming techniques to find sched-
ules that respect the difficult range of additional constraints.
The basis of this thesis was the development of an optimized conference schedule
of the International Symposium on Mathematical Programming 2012 (ISMP 2012) in
Berlin, Germany. The ISMP is one of the largest conferences in the field of applied
mathematics and mathematical optimization and constitutes a great attraction for in-
ternational mathematicians and researchers. We will present our results based on the
problem instance that we used for the ISMP 2012.