Institut für Theoretische Informatik, Algorithmik

Forschungsseminar

Wintersemester 2021

Minimum-Width Triangulations of Upward Planar Graphs

  • Datum: Di, 8 Mär 2022, 13:30
  • Ort: SR 301
  • Vortragende(r): Liran Dattner, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Partitioning Geometric Graphs into Plane Subgraphs

  • Datum: Di, 8 Mär 2022, 13:00
  • Ort: SR 301
  • Vortragende(r): Jonathan Dransfeld, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Die Anzahl maximaler Cliquen in geometrischen Zufallsgraphen

  • Datum: Fr, 17 Dez 2021, 14:30
  • Vortragende(r): Niko Lemke, ITI Bläsius, Intro-Talk Bachelorarbeit
  • Inhalt: In Nikos Kurzvortrag für seine Bachelorarbeit geht es darum abzuschätzen, wie viele Inklusionsmaximale Cliquen unterschiedliche Varianten von geometrischen Zufallsgraphen haben. Der Zoomlink gilt auch für Chris Vortrag um 14:00.

An Efficient Branch-and-Bound Solver for Hitting Set (ALENEX rehearsal)

  • Datum: Fr, 17 Dez 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Chris, I am great
  • Inhalt: The hitting set problem asks for a collection of sets over a universe $U$ to find a minimum subset of $U$ that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instances from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.

On Minus labellings, A directed variant of sum labellings

  • Datum: Fr, 3 Dez 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Matthew Akram, ITI Bläsius, Intro-Talk Bachelorthesis
  • Inhalt: A graph G=(V,E) is a sum graph if there is a labelling lambda:V->mathbb{Z} such that there is an edge between vertices u and v if and only if there is a vertex with the label lambda(u)+lambda(v). In this bachelor thesis we investigate directed variants of such labelling schemes. We call a graph a minus graph if there is a labelling as above such that there is an edge from u to v if and only if there is a vertex with label lambda(u)­-lambda(v). In this talk we give an overview of our preliminary results, including some basic properties, a classification of rooted-trees and more.

Solving Dynamic Macroeconomic Models with an Entrepreneurial Sector

  • Datum: Fr, 26 Nov 2021, 14:00
  • Ort: SR 301 (tentatively)
  • Vortragende(r): Henriette Kissling, ITI Bläsius + Chair of Macroeconomics; Abschlussvortrag Bachelorarbeit
  • Inhalt: In this thesis, we make two contributions: first, we transfer an overlapping-generations model of intertemporal savings and investment decisions used to evaluate taxation systems to an equivalent infinite-horizon Aiyagari-style model. We compare the results of the two model types and investigate the mechanisms at play. Our work is the first step of an ongoing research program with the overall objective of evaluating wealth taxation in the context of heterogeneous returns. We show that the results generated by the transferred model are fairly close to the empirical data on the U.S. earnings, income and wealth distribution. Crucially, the model yields almost the same extent of inequality in terms of Gini coefficients. Second, we explore the technical boundaries of solving complex dynamic macroeco- nomic models with common methods and extend these methods in order to obtain a good compromise between accuracy and computational feasibility. We show that our approach manages to speedup the calculation by factor 9 and allows us to impose configurable standards on the minimum precision.

Asynchronous n-Level Hypergraph Partitioning

  • Datum: Mi, 24 Nov 2021, 14:00
  • Vortragende(r): Moritz Laupichler, ITI Sanders und Wagner; Master Thesis
  • Inhalt: In this thesis, we introduce a novel approach to scalable high-quality parallel hypergraph partitioning. The balanced k-way hypergraph partitioning problem consists of partitioning the vertices of a hypergraph into k blocks of almost equal size s.t. an objective function is optimized (usually the sum of the number of blocks that each hyperedge spans should be minimized). In the n-level variant of the popular multilevel scheme, almost n contractions are performed on the hypergraph before finding an initial partitioning and then reverting the contractions. In the uncoarsening phase, after every uncontraction, localized refinement is applied around the region of the uncontraction, which leads to partitions of very high quality. In this work, we present asynchronous uncoarsening, a highly scalable parallelization of the n-level uncoarsening phase in which uncontractions and localized refinement happen concurrently. We introduce a framework that requires no global synchronization during the uncoarsening phase and allows fine-grained control of cross-dependencies between concurrent uncontractions and refinement. We implement asynchronous uncoarsening in the Mt-KaHyPar framework and experimentally compare our approach with the previous batch synchronous uncoarsening phase. Our extensive experiments on more than 500 real-world hypergraphs with up to 190 million vertices and 2 billion pins (sum of hyperedge sizes) show that our approach scales better on large hypergraphs with only a small loss of quality. We find that Mt-KaHyPar with asynchronous uncoarsening is on average 26% faster than Mt-KaHyPar with batch uncoarsening for large instances using 64 threads. Our uncoarsening phase reaches average self-relative speedups of 39 for 64 threads on difficult instances for which the average speedups of Mt-KaHyPar's batch uncoarsening are limited to less than 24.

Maximal k-Degenerate Spanning Subgraphs

  • Datum: Fr, 19 Nov 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Nadine Krisam, ITI Wagner; Master Thesis
  • Inhalt: In this thesis we discuss maximum k-degenerate spanning subgraphs. A spanning subgraph is a subgraph where only edges were deleted. In a k-degenerate graph G every subgraph of G has a vertex of degree at most k. The degeneracy of a graph G is the minimum integer k such that G is k-degenerate. By deleting edges of a graph the degeneracy can be reduced. We introduce the term of k-degenerate skewness ds_k(G) that denotes the number of edges in a graph G that need to be deleted so that it becomes k-degenerate. We also define the maximum k-degenerate skewness ds_k^C(n) for a graph class C as the maximum of ds_k(G) over all graphs G in C with n vertices. We describe general methods to reduce the degeneracy of a graph. Furthermore, we give bounds for ds_k^P(n) and ds_k^B(n). Here, P stands for the graph class containing all planar graphs and B for the graph class containing all bipartite planar graphs.

Minimum Linear Arrangement

  • Datum: Fr, 12 Nov 2021, 14:30
  • Ort: SR 301
  • Vortragende(r): Michael, Zündorf, Master thesis introduction talk
  • Inhalt: TBD

A Novel Time-dependent Model for Route Planning in Public Transit Networks

  • Datum: Fr, 12 Nov 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Voula Machaira, Guest Talk; Master Thesis; University of Patras
  • Inhalt: In this thesis, the non-FIFO time-dependent model with REalistic vehicle eXchange times (REX) is introduced for schedule-based public transport systems, along with two novel query algorithms for computing optimal multimodal journeys for either a single criterion (earliest arrivals) or two criteria (plus number of transfers). The REX model is a considerable enhancement of the simple time-dependent model, with additional features towards handling non-negligible exchanges from one vehicle to another, as well as supporting non-FIFO instances which are typical in public transport, without compromising the space efficiency of the model. Apart from the novelty of the model, REX is also accompanied with two novel query algorithms, whose rationale is some sort of "trip-targeted" label-correction propagation process: the first algorithm, TRIP-based Label-correction propagation Algorithm (TRIPLA), efficiently solves the realistic earliest-arrival routing problem; the second algorithm, BI-criteria TRIP-based Label-correction propagation Algorithm (BITRIPLA), solves the bi-criteria variant of the problem, where apart from the earliest-arrival objective, the commuters also care for minimizing the number of vehicle exchanges. The set of Pareto-optimal journeys is discovered when all the arrival-times are bounded. We conduct a thorough experimental evaluation on real-world public transit networks which demonstrates that both query algorithms for the REX model are competitive with state-of-art query algorithms for multimodal routing in schedule-based public transport models.

Local Page Number und local Queue Number von gerichteten azyklischen Graphen

  • Datum: Fr, 29 Okt 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Tim Groß, ITI Wagner; Bachelor Thesis
  • Inhalt: Ein Book Embedding (Queue Layout) eines gerichteten azyklischen Graphen besteht aus einer topologischen Ordnung seiner Knoten und einer Partition seiner Kanten in Seiten (Queues) genannte Teilmengen, sodass sich Kanten in derselben Seite (Queue) nicht kreuzen (verschachteln). Zwei Kanten kreuzen sich (sind verschachtelt), wenn ihre Endpunkte in einem ABAB (ABBA) Muster angeordnet sind. Die local Page Number pn(G) (local Queue Number qn(G)) eines Graphen G ist die kleinste Zahl k, sodass es ein Book Embedding (Queue Layout) für G gibt, in welchem jeder Knoten inzidente Kanten in höchstens k Seiten (Queues) hat. Wir präsentieren hier kurz die wichtigsten Ergebnisse der Bachelorarbeit zum Thema "Local Page Number und local Queue Number von gerichteten azyklischen Graphen". Wir zeigen jeweils die Konstruktion eines planaren Graphen mit local Page Number 3, sowie eines mit local Queue Number 3. Außerdem konstruieren wir einen planaren Graphen, der für eine feste Knotenordnung local Page Number 4 hat. Weiterhin zeigen wir für die local Page Number und die local Queue Number von planaren Graphen eine obere Schranke von 4. Für die local Page Number sowie die local Queue Number von gerichteten azyklischen k-Bäumen zeigen wir jeweils eine untere sowie obere Schranke von k+1.

Leiden-Based Parallel Community Detection

  • Datum: Fr, 22 Okt 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Fabian Nguyen, ITI Wagner; Bachelor Thesis
  • Inhalt: Leiden is a community detection algorithm for maximizing modularity by dividing a graph into densely connected disjoint sets of nodes. It improves the well-known Louvain algorithm with an additional refinement phase in which clusters are subdivided before contraction. In this work we investigate an efficient parallelization of the refinement phase and build upon existing work on parallelizing the local moving phase. We show that the overall implementation achieves speedups up to 15.8 on the largest tested graph with 64 threads. Parallel refinement achieves speedups up to 28 with 128 threads whereas local moving only scales up to about 32 threads with a maximum speed up of 12.5.

Coloring the Union of Geometric Hypergraphs

  • Datum: Fr, 8 Okt 2021, 14:30
  • Ort: SR 301
  • Vortragende(r): Vera Chekan, ITI Wagner; Master Thesis
  • Inhalt: For a range family R (e.g., all axis-aligned rectangles in the plane) we consider a geometric hypergraph captured by R, i.e., its vertex set is a finite set of points in the plane and its hyperedges are such subsets of these points that are contained in some range in R. In this thesis we investigate the existence of polychromatic colorings for unions of geometric hypergraphs: in such a coloring every hyperedge contains a vertex of each color. For a range family R and number of colors k, the value m(k) is the smallest number such that every m(k)-uniform hypergraph captured by R admits a polychromatic coloring with k colors. We concentrate on range families consisting of various unbounded axis-aligned rectangles and diagonal strips of slope -1: for each subfamily we either provide an upper bound on m(k) or prove that m(2) = infinity holds. n particular, we show that for the family of all bottomless rectangles and horizontal strips we have m(2) = infinity.

On the Resolution of the Sensitivity Conjecture

  • Datum: Fr, 8 Okt 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): David Schuldes, ITI Wagner; Bachelor Thesis
  • Inhalt: The sensitivity of a boolean function is defined as the maximum number of indices of any input vector x in {0, 1}^n such that flipping the input vector at the index changes the value of f(x). In my presentation I will outline the conceptual proof of the Sensitivity Conjecture and introduce the necessary mathematical definitions and theorems to do so. Moreover, I will show how the techniques used to prove the Sensitivity Conjecture can further be used in order to obtain insights into the structural relationships between a special class of matrices, their eigenvalues, the maximum degree of corresponding the graph and vertex induced subgraphs. Then I will show an additional insight into the relationship between vertex induced subgraphs of the n-hypercube and the structure of the node with maximum degree. To close the presentation, I will show an alternative proof of the main theorem that does not make use of matrices.

Sommersemester 2021

Analysis of Heuristics for Treewidth

  • Datum: Do, 30 Sep 2021, 15:30
  • Ort: ms teams
  • Vortragende(r): Marcus Wunderlich, ITI Blaesius; Bachelor Thesis
  • Inhalt: Treewidth is an important concept in many fields like for example, graph theory and parameterized algorithms. Determining a graph's treewidth is necessary for many applications, but it is, unfortunately, an NP-hard problem. To at least approximate the treewidth efficiently, several heuristics were introduced, including the MinDegree heuristic and the MinFillIn heuristic. Although these achieve surprisingly good results in practice, they are barely studied theoretically. In this thesis, we initiate this study by investigating the behavior of the two heuristics on grids. Along the way to grids with arbitrarily large side lengths, we also investigate some superclasses of small grids like the chordal graphs and series-parallel graphs. We additionally present a first approach to upper bound the result of the MinDegree heuristic, and introduce the concept of a border graph -- a simple structure that captures all relevant information at any fixed point in time during the execution of one of the heuristics. We believe that the border graph provides a useful perspective that will help future studies of the heuristics.

Applying Customizable Contraction Hierarchy Potentials to the Shortest Epsilon-Smooth Path Problem

  • Datum: Fr, 24 Sep 2021, 15:00
  • Ort: ms teams
  • Vortragende(r): Jakob Bussas, ITI Wagner; Bachelor Thesis
  • Inhalt: When computing traffic routes, it is important to consider real-time traffic data. However, this data is not always perfect and might lead to routes with unwanted detours, for example through residential areas. This work focuses on finding fast routes with real-time traffic data while avoiding such unwanted detours. The approach will be to find a shortest path with respect to two different edge weight functions. We propose an algorithm that makes use of Customizable Contraction Hierarchies and analyze its performance and behavior.

Planning Geometric Microgrid Cable Layouts

  • Datum: Fr, 24 Sep 2021, 14:30
  • Ort: ms teams
  • Vortragende(r): Max Göttlicher, ITI Wagner; Master Thesis
  • Inhalt: We introduce a new genetic algorithm for the Microgrid cabling problem. Microgrid cabling is the problem of finding a minimum cost cable layout for a microgrid given the consumer demands and generator supplies and their positions in the plane. The layout is a tree on the terminals and additional freely placeable Steiner nodes with cable types assigned to the edges. The layout cost depends on the required power capacities of the edges and the cable losses. Our algorithm explores possible cable layouts and uses a heuristic to assign the cables with respect to capacitites and losses. The genetic operators can be used in other geometric tree problems. Our algorithm finds good solutions to the geometric Steiner tree problems but cannot compete with dedicated algorithms. On a real-world microgrid example our algorithm converged in less than 30 seconds.

Tiling Rectangles with Unions of Squares

  • Datum: Fr, 24 Sep 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Jonas Seiler, ITI Wagner; Bachelor Thesis
  • Inhalt: Given two squares with side lengths a and b, we can "glue" them together to get an (a, b)-piece. A tiling of a rectangle with side lengths C and D with (a, b)-pieces is a placement of these pieces such that every point in the rectangle is covered by exactly one piece and no piece goes out of the rectangle. We show that we can decide whether a given C × D-rectangle can be tiled with (a, b)-pieces and we can at least semi decide whether there exists a C × D-rectangle that can be tiled with given (a, b)-pieces. Furthermore we will look at some pieces in detail and find categories that have no tilings and some that have at least one tiling. Lastly we will also prove that we can tile the whole plane with (a, b)-pieces for every combination of a,b.

Induced Universal Graphs for Edge-Colored Complete Graphs

  • Datum: Fr, 10 Sep 2021, 14:30
  • Ort: SR 301
  • Vortragende(r): Christian Kouekam, ITI Wagner; Master Thesis
  • Inhalt: TBA

Upward and Upward-Planar Drawings with Limited Slopes

  • Datum: Fr, 10 Sep 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Valentin Quapil, ITI Wagner; Bachelor Thesis
  • Inhalt: We present algorithms and limitations of upward and upward-planar drawings with a limited number of distinct slopes. First we discuss which slope sets are interchangable when drawing upward planar. Then we present a new algorithm for drawing series-parallel graphs upward planar with two or three slopes. Finally, we show a lower bound for the space requirements of upward planar drawings with three slopes: There are series-parallel graphs, cacti, and ordered trees whose upward planar drawings with three slopes require exponential width and height on the integer grid.

Engineering Heuristic Quasi-Threshold Editing

  • Datum: Fr, 23 Jul 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): David Schmitt, ITI Wagner; Master Thesis
  • Inhalt: We introduce an algorithm that solves the quasi-threshold graph editing problem. The problem is defined as removing and inserting edges in a graph to reach a quasi-threshold graph. Quasi-threshold graphs can be defined as the transitive closure of a rooted forest. Given a graph, the algorithm computes a quasi-threshold graph, which is close to the original regarding the sum of edge edit costs. Building on the previously introduced heuristic Quasi-Threshold Mover (QTM), which is limited to uniform edit costs, we consider edit costs for edge insertions and deletions. QTM represents the graph as a skeleton forest and works in rounds. In each round, QTM heuristically improves the number of edits by trying to move every node to a new position in the forest. The approach is called local move. We adapt QTM to solve the problem while minimizing edit costs. Additionally, we propose improvements in solution quality by moving nodes with their subtree instead of the node alone. This optimization is called subtree move. In an extensive experimental evaluation, we apply the algorithm to two large sets of graphs. The quality of the solution and running time per round of QTM suffers with edit costs considered in comparison to uniform edit costs. The solution quality can be improved by enabling the subtree move optimization at the cost of additional running time per round.

Robust Hypergraph Coarsening

  • Datum: Fr, 9 Jul 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Simon Vögele, ITI Wagner; Bachelor Thesis
  • Inhalt: Balanced hypergraph partitioning is a NP-hard problem with applications in various domains like high performance computing and chip design. The multilevel heuristic is used by many partitioners to solve this problem. This heuristic splits the problem into three phases: coarsening, initial partitioning and uncoarsening. The coarsening phase creates a hierarchy of consecutively smaller hypergraphs. The initial partitioning phase computes a partition of the coarsest hypergraph in the hierarchy. In the uncoarsening phase, the partition is projected through the hierarchy and refined until a partition for the original hypergraph is found. We improve the coarsening phase of the hypergraph partitioning tool Mt-KaHyPar. This is done by relaxing some restrictions on how to coarsen the hypergraph if the coarsening does not achieve small enough coarse hypergraphs. Our experiments show that these improvements are able to reduce coarse hypergraph size by up to 98% and total partitioning runtime by up to 54% on some instances with no significant loss of solution quality.

Community Detection in Hypergraphs with Application to Partitioning

  • Datum: Di, 22 Jun 2021, 11:00
  • Vortragende(r): Robert Krause, ITI Wagner und Sanders; Bachelor Thesis
  • Inhalt: We present different approaches to community detection on hypergraphs and evaluate them as a preprocessing step for the coarsening phase of a hypergraph partitioning algorithm. We present a modularity maximization approach that optimizes a modularity formulation that we derived by incorporating the connectivity of hyperedges. We optimize this hypergraph modularity using the parallel Louvain method. Additionally, we present formulations for the map equation on hypergraphs based on different random walk models. We integrate our hypergraph community detection algorithms into the parallel shared-memory hypergraph partitioner Mt-KaHyPar. Finally, we evaluate different optimizations and heuristics we used to speed up the hypergraph modularity method and compare our different approaches as well as the current graph-based approach in extensive experiments. Our approach produced better partitions than the current configuration Mt-KaHyPar-D on 61% of the instances. However, our approach is slower by a factor of 5.4 on average.

Improving Parallel Refinement Algorithms for Hypergraph Partitioning

  • Datum: Fr, 7 Mai 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Noah Wahl, ITI Wagner; Bachelor Thesis
  • Inhalt: Hypergraph partitioning algorithms leverage fast local search algorithms to improve initial solutions, often within the multilevel framework. The most widely used local search algorithm is the Fiduccia-Mattheyses (FM) refinement heuristic, which repeatedly performs the vertex move that improves the solution quality the most, while maintaining a balanced partition. To escape local minima, it allows intermediate quality losses, but reverts to the best solution observed at the end of a pass. With the increasing importance of parallel processing, several parallelization approaches have been published in recent years. In this work, new and existing techniques to improve these algorithms are investigated. Further, the trade-offs between several design decisions of the two most prominent, recent parallelization approaches, the greedy refinement of Mt-Metis and localized FM of Mt-KaHyPar are experimentally evaluated. The implementation is integrated in the Mt-KaHyPar framework. Message queues lead to no noticeable difference in most cases, because the gain table of Mt-KaHyPar overshadows their utility. Greedy refinement suffers from a large discrepancy in solution quality induced by a fixed assignment of vertices. Delaying or preventing reoccurring expensive gain updates leads to substantial savings on a set of previously problematic instances for Mt-KaHyPar. Finally, local search scheduling is a technique aimed at emulating sequential FM. While this emulation is successful, the overall solution quality is worse than the baseline approach, though more careful scheduling rules may yield improvements yet.

Beschleunigtes LKW-Routing mit zeitabhängigen Fahrverboten

  • Datum: Fr, 30 Apr 2021, 14:30
  • Ort: ms teams
  • Vortragende(r): Julius Häcker, ITI Wagner; Bachelor Thesis
  • Inhalt: Routinganwendungen sind für uns heutzutage sehr wichtig und werden häufig genutzt. Für LKWs brauchen wir anderes Routing als für PKWs, da es für LKWs temporäre Fahrverbote gibt. Das können Nacht- oder Wochentagsfahrverbote sein, die ein großräumiges Gebiet betreffen, oder Fahrverbote für bestimmte Straßenabschnitte. Dazu gibt es für LKWs im Gegensatz zu PKWs gesetzlich geregelte Lenk- und Ruhezeiten. Das bedeutet, dass der Fahrer nach einer bestimmten Fahrzeit eine Pause machen muss. Daher können Pausen und das Anfahren von Parkplätzen nötig werden. Für sinnvolle LKW-Routen ist es also wichtig, dass temporäre Fahrverbote und Lenk- und Ruhezeiten bereits in der Routenplanung berücksichtigt werden. Die Qualität einer Pause hängt von der Qualität des Parkplatzes ab, auf dem die Pause gemacht wird. Daher kann es sinnvoll sein, einen größeren Umweg für einen Parkplatz besserer Qualität zu fahren. Dadurch entsteht ein Trade-Off für die Berechnung der Routen. In [KSWZ20] wurde ein Algorithmus vorgestellt, der diesen Trade-Off beim Routing berücksichtigt. Dabei werden keine Lenk- und Ruhezeiten berücksichtigt. Wir erweitern diesen Algorithmus zu einer bidirektionalen Suche, um stärkeres Pruning zu ermöglichen und dadurch die Laufzeit zu verbessern. Die Laufzeit konnte dabei bei einigen langsamen (>10s) Queries halbiert werden. Ansonsten konnten keine langsamen Queries wesentlich beschleunigt werden. Außerdem modifizieren wir den Algorithmus, um Lenk- und Ruhezeiten in einer vereinfachten Form zu berücksichtigen. Dabei vereinfachen sich die Ergebnisse einiger Queries, sodass es dort weniger berechnete Routen gibt.

Coordinated Motion Planning for Multiple Square-Shaped Robots in a Grid

  • Datum: Fr, 30 Apr 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Julian Dinh, ITI Wagner; Bachelor Thesis
  • Inhalt: Gegeben seien n quadratische Roboter mit Start- und Zielpositionen für jeden Roboter. Die Roboter befinden sich in einem unbegrenzten Gitter, welches stationäre Hindernisse enthalten kann. In jedem Zeitschritt kann sich ein Roboter in eine benachbarte Gitterposition bewegen oder auf seiner Position bleiben. Die Aufgabe ist es, einen Plan für die Bewegungsabläufe zu finden, in dem jeder Roboter an seiner Startposition beginnt und seine Zielposition erreicht, ohne dabei mit anderen Robotern oder Hindernissen zu kollidieren. Wir zeigen, dass wir mit einer kleinen Einschränkung immer einen solchen Plan finden. Zusätzlich möchten wir einerseits die Gesamtzeit, die benötigt wird, um alle Roboter an ihre Zielposition zu bringen, und andererseits die Strecke, die alle Roboter zusammen zurücklegen, minimieren. Wir betrachten diverse Heuristiken und evaluieren unsere Lösung auf verschiedenen Probleminstanzen.

A Shortest Path Approach for Gas Turbine Scheduling in Multimodal Energy Systems

  • Datum: Mo, 26 Apr 2021, 10:00
  • Ort: ms teams
  • Vortragende(r): Patrick Fetzer, ITI Wagner; Bachelor Thesis
  • Inhalt: Finding an optimal operating schedule for a combined heat and power plant in a multimodal energy system with district heating, photovoltaics and storages is challenging. The goal of this thesis is to compute an optimal day-ahead operating schedule for the gas turbine. With such a schedule the heat demand needs to be covered at all times, while thermal and electrical turbine output can be stored up to the capacities of the storages and surplus electrical power can be exported. A gas turbine schedule is called optimal if it fulfills demand and storage constraints while minimizing the operating costs. In this work a graph is constructed that represents states of charges of battery and heat storages with state transitions given by discrete thermal set points of the turbine. Two shortest path algorithms, a Dijkstra-based approach and a Dynamic Program, are used to find optimal gas turbine schedules. The algorithms are evaluated using a more accurate simulation of a district energy system scenario containing 16 buildings.

Effiziente Berechnung von Alternativrouten mit der Penaltymethode und CH-Potentialen

  • Datum: Fr, 16 Apr 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Max Willich, ITI Wagner; Bachelor Thesis
  • Inhalt: Wir beschäftigen uns mit der Berechnung von Alternativrouten von A nach B auf Straßengraphen. Mithilfe der Penalty-Methode können Graphen auf sogenannte Alternativgraphen reduziert werden. Ein guter Alternativgraph ist sehr dünn besetzt, beinhält aber viele gute Alternativrouten. Kobitzsch et al. veröffentlichten 2013 in [KRS13] eine Implementation der Penalty-Methode, welche sehr gute Alternativgraphen innerhalb weniger hundert Millisekunden berechnen kann. Wir evaluieren eine alternative Realisierung mithilfe des A*-Algorithmus und CH-Potentialen, welche einfacher zu implementieren ist, auf Qualität und Laufzeit. Wir erreichen hohe Erfolgsquoten und Pfadqualitäten für alle Testinstanzen. Wir erzielen schlechtere Laufzeiten als Kobitzsch et al., aber dennoch Laufzeiten unter einer Sekunde für alle außer die längsten Anfragen.

Wintersemester 2020

Optimizing the Distributed Storage Problem using Time-Expanded Network Flow

  • Datum: Fr, 5 Mär 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Ivo Baar, ITI Wagner; Master Thesis
  • Inhalt: With climate change being a worldwide issue, there are new challenges arising for the power industry. A transition from conventional energy sources to renewable ones is a key to reducing CO 2 emissions. Due to the fact that power supply by renewable sources fluctuates substantially, power storage becomes more important. These units can help to provide power in times when natural factors are not allowing renewable energy production. This helps immensely in utilizing clean energy to a bigger extent. The distribution of power at the lowest possible cost can be modeled as the Optimal Power Flow Problem. With the addition of storage units comes the need for new algorithms, that consider them in their model. In this work we will provide a way to model the Optimal Power Flow Problem with storages as a Minimum Cost Flow Problem. Further, we are presenting and evaluating our implementation of an algorithm for said problem and compare it to a reference implementation with regard to runtime.

Multicriteria Trip-Based Public Transit Routing

  • Datum: Fr, 15 Jan 2021, 14:30
  • Ort: MS teams
  • Vortragende(r): Moritz Potthoff, ITI Wagner; Bachelor Thesis
  • Inhalt: Der Trip-Based Public Transit Routing Algorithmus berechnet Pareto-optimale Routen in öffentlichen Verkehrsnetzwerken für zwei Kriterien: früheste Ankunftszeit und minimale Anzahl Umstiege. Diese Arbeit erweitert den Algorithmus, um Pareto-optimale Routen für ein zusätzliches Kriterium zu berechnen. Der Walking Trip-Based Algorithmus minimiert zusätzlich die Fußwegezeit entlang einer Route. Der Fare Zone Trip-Based Algorithmus optimiert Routen zusätzlich für die minimale Menge an genutzen Tarifzonen. Dazu werden sowohl die Vorberechnungs- als auch die Anfragephase des Algorithmus angepasst und optimiert. Die entstandenen Algorithmen werden ausführlich auf drei realen öffentlichen Verkehrsnetzen evaluiert und Anfragelaufzeiten werden mit denen von McRAPTOR vergleichen. Der Walking Trip-Based Algorithmus berechnet Anfragen auf allen Netzwerken schneller als der McRAPTOR Algorithmus. Die erreichte Beschleuningung gegenüber McRAPTOR liegt zwischen 1.18 und 3.47. Die parallelisierte Vorberechnung läuft für kleine Netzwerke in Minuten und braucht für eine komplexe Variante der Schweiz nur 36 min. Die zweite Erweiterung, der Fare Zone Trip-Based Algorithmus, ist deutlich langsamer als die McRAPTOR-Variante. Basierend auf diesen Erkenntnissen wird analysiert für welche Kombinationen von Optimierungskriterien der multikriterielle Trip-Based-Ansatz vielversprechend ist und mögliche Integrationen mit anderen Algorithmen werden diskutiert.

Evaluating Wind Farm Cable Layouts obtained from Negative Cycle Canceling using Power Flow Analysis in eASiMOV

  • Datum: Do, 17 Dez 2020, 14:00
  • Ort: TBD
  • Vortragende(r): Pascal Mehnert, ITI Wagner; Bachelor Thesis
  • Inhalt: In an offshore wind farm the electrical energy generated by each wind turbine needs to be transported to an offshore substation, to make it available to the rest of the grid. It is the responsibility of the internal cabling of such a wind farm to connect each wind turbine, possible via other turbines, to a substation. The Wind Farm Cabling Problem (WCP) formalizes the design of internal cable layouts as a flow problem on graphs and defines a criteria for their optimality, in the form of a cost function. A number of algorithms have been proposed in the literature to solve instances of WCP, of which we focus mainly on the Negative Cycle Canceling (NCC) heuristic. In this thesis we evaluate cable layouts obtained from NCC and other algorithms, using the capabilities of power flow analysis. We introduce a software application that allows us to generate the required simulation models for any cable layout and calculate power flows for them. The calculation results allow us to gain insight into some of the operating characteristics of the cable layouts. We use this in particular to assess if certain structures in cable layouts, like cycles between multiple turbines, have negative effects on the performance of the resulting simulation models. In the course of this thesis we also compare a number of variations of NCC in terms of the efficiency of solutions generated by them.

Communication-free Generation of Graphs with Planted Communities

  • Datum: Fr, 11 Dez 2020, 15:00
  • Ort: online
  • Vortragende(r): Adrian Feilhauer, ITI Wagner/Sanders; Master Thesis
  • Inhalt: Graphen, die soziale Strukturen widerspiegeln, beinhalten oft sogenannte Communities von Knoten, deren Mitglieder untereinander häufig verbunden sind. Algorithmen, die derartige Netzwerke analysieren, sind zur Qualitätskontrolle auf Graphen mit bekannter Communitystruktur angewiesen. Hier werden einige Modelle mit zugehörigen Generatoren vorgestellt, die Graphen mit spezieller Communitystruktur erzeugen. Die Generatoren arbeiten in verteilten Systemen ohne Kommunikation. Dadurch können Graphen generiert werden, ohne von Beschränkungen der Kommunikation zwischen Prozessoren beeinträchtigt zu werden. Die einfacheren Modelle skalieren nahezu perfekt. Mit 128 Kernen können dort Graphen mit 2^31 Knoten und über 2^42 Kanten in weniger als zehn Minuten erzeugt werden. Das entspricht ca. 10^8 Kanten pro Sekunde und Prozessor. Komplexere Modelle mit nach Potenzgesetz verteilten Communitygrößen und Knotenmitgliedschaften skalieren einigermaßen gut. Obwohl die Verteilung der Last zwischen den verwendeten 128 Kernen suboptimal war, konnten für Graphen mit 2^25 Knoten durchschnittlich 10^6 Kanten pro Sekunde und Prozessor generiert werden.

Negative Cycle Canceling for Cost-Efficient Wind Farm Planning

  • Datum: Fr, 11 Dez 2020, 14:00
  • Ort: TBD
  • Vortragende(r): Alina Valta, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Ordered Covering Numbers

  • Datum: Fr, 27 Nov 2020, 14:00
  • Ort: ms teams
  • Vortragende(r): Laura Merker, ITI Wagner; Master Thesis
  • Inhalt: Given a graph, we aim to find a vertex ordering and a partition of the edges such that each part satisfies certain conditions like being crossing-free. We first discuss results and open problems for some ordered covering numbers (including variants of page numbers, queue numbers, and track numbers) and then focus on book embeddings of upward planar graphs. A directed acyclic graph is called upward planar if it admits a plane drawing such that all edges increase monotonically in y-direction. A book embedding of an upward planar graph consists of a topological ordering of the vertices and a partition of the edges into pages, where two edges whose endpoints form an ABAB-pattern may not belong to the same page. That is, each page is crossing-free if the vertices are placed on a straight line and all edges are drawn in the same half-plane. The page number of a graph G is defined as the smallest k such that there is a book embedding with at most k pages for G. We show that there is an upward planar graph (and even a planar poset) that requires at least five pages.

Engineering an algorithm for optimal backload allocation in freight exchanges

  • Datum: Mi, 11 Nov 2020, 10:00
  • Ort: i10 Jitsi
  • Vortragende(r): Julian Labeit, ITI Sanders; Master Thesis
  • Inhalt: In this work we examine a specific problem that occurs when trucking companies search for matching orders in so called freight exchanges. The objective is to find the cheapest route for a truck from a start s to a destination t while executing additional orders from the freight exchange along the way. First, we model this problem as a shortest-path problem in a graph with O(n) vertices, negative edge weights and possibly negative cycles. Second, we apply proposed algorithms for the Longest Paths problem and from the Vehicle Routing Problem with Profits. Finally, we present an evaluation of the different approaches on real example datasets from the logistics field.

On the Strong Product Theorem -- Improving the Treewidth Bound

  • Datum: Di, 10 Nov 2020, 13:00
  • Ort: MS Teams
  • Vortragende(r): Wendy Yi, ITI Wagner; Bachelor Thesis
  • Inhalt: A layering of a graph assigns each vertex an integer such that layers of adjacent vertices differ by at most one. A path in a graph with a given layering is vertical if its vertices are assigned pairwise distinct layers. Dujmovic et al. recently proved the Strong Product Theorem, which states that for every planar graph G with a BFS-layering (a type of layerings that are based on distances in BFS-trees), the vertices of G can be partitioned into vertical paths P such that the quotient graph G/P has treewidth at most 8. This is equivalent to the statement that every planar graph is a subgraph of the strong product of some graph with treewidth at most 8 and some path. By modifying the original proof of the Strong Product Theorem, we prove that the upper bound for the treewidth of the quotient graph can be improved to 7. Additionally, we show that this bound is tight when following the approach from the proof. Moreover, we prove that for a particular subclass of planar graphs, we can obtain a better upper bound.

Accurate Public Transit Assignment using Network Pruning and Quasi-Monte Carlo Simulation

  • Datum: Fr, 6 Nov 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Kolja Kühn, ITI Wagner; Bachelor Thesis
  • Inhalt: We study the problem of computing traffic assignments for public transit networks. Given a list of passengers (each having an origin, a destination and a departure time), we want to predict for each passenger which journey they will take. This information allows us to estimate the expected utilization of each vehicle. Previous work accounted for variations in the passengers' preferences by adding a randomly distributed error term to the utility of each possible journey. However, this model does not account for correlations between journeys that share connections or use vehicles of the same type (bus, tram etc.). We address this problem by weighting the time spent in each vehicle type by a randomly distributed factor. In this model journeys using the same vehicle type will automatically be correlated as they share the same factor. However, we show that computing an exact solution for this new problem is #P-hard. In order to provide an efficient algorithm for approximating a solution, we use a sampling-based algorithm and improve convergence by sampling using a low discrepancy point set. An assignment of all passengers travelling to the same destination can be computed with a single sweep over the network based on the Connection Scan Algorithm, resulting in an algorithm that scales well even with a large number of passengers. We present three pruning methods to further improve performance by reducing the size of the network during the assignment process.

Negative Cycle Canceling for the Wind Farm Cabling Problem with Distribution Nodes

  • Datum: Di, 27 Okt 2020, 14:00
  • Ort: TBD
  • Vortragende(r): Niklas Meier, ITI Wagner; Bachelor Thesis
  • Inhalt: Das Windfarm-Verkabelungsproblem (WCP) beschreibt die Aufgabe, eine Verkabelung einer Windfarm zu finden. Ziel des WCP ist es, dass von Turbinen produzierter Strom möglichst kostengünstig zu Substationen geleitet wird. Hierfür können unterschiedliche Kabeltypen genutzt werden, jeweils mit einer bestimmten Kapazität und unterschiedlichen Kosten. Dadurch ist das WCP im Allgemeinen NP-schwer. Als NP-schweres Problem gibt es keinen Algorithmus, der WCP effizient bis zum Optimalwert lösen kann, aber es gibt heuristische Ansätze, welche schnell eine angenäherte Lösung finden, wie zum Beispiel Negative Cycle Canceling (NCC). In meiner Arbeit wurde das WCP um Verteilerstationen erweitert. Verteilerstationen sind zusätzliche optionale Knoten, welche genutzt werden können, um elektrischen Fluss umzuleiten. Wird eine Verteilerstation genutzt, entstehen zusätzliche Kosten, welche die Baukosten der Verteilerstation repräsentieren. Ziel meiner Arbeit war es, einen vorhandenen NCC-Algorithmus so zu erweitern, dass er Verteilerstationen mit ihren entsprechenden Kosten berücksichtigen kann. Hierfür habe ich zunächst eine Fluss-Formulierung von WCP erweitert. In einem weiteren Schritt habe ich Verteilerstationen mit ihren entsprechenden Kosten in einem Residualgraphen modelliert. Dieser Residualgraph repräsentiert die Kosten von Flussänderungen und wird von dem NCC-Algorithmus genutzt. In einem dritten Schritt habe ich die Residualgraph-Modellierung algorithmisch realisiert und den vorhandenen NCC-Algorithmus angepasst.

Combining Multiple Criteria in Multi-Modal Route Planning using ULTRA

  • Datum: Fr, 9 Okt 2020, 15:00
  • Ort: SR 301
  • Vortragende(r): Manuel Schweigert, ITI Wagner; Master Thesis
  • Inhalt: We study the problem of finding multimodal, multicriteria journeys in transportation networks, including a single mode of unrestricted individual transport like walking, cycling or driven, and a schedule-based public transportation system. We use the ideas of the ULTRA preprocessing technique (UnLimited TRAnsfers) and combine them with a multicriteria search based on RAPTOR to produce full Pareto sets of optimal journeys. We examine the performance of this technique to optimize for three criteria: arrival time, walking distance and number of rides on public transportation vehicles utilized and show that this approach leads to a significant speed up for queries using these criteria for transfer speeds up to driving-speeds compared to other algorithms. Furthermore, they also show that the technique is well suited for metropolitan areas, but that it can also deal with country-scale networks.

UnLimited TRAnsfer Shortcuts with Delay Tolerance for Multi-Modal Journey Planning

  • Datum: Fr, 9 Okt 2020, 14:30
  • Ort: SR 301
  • Vortragende(r): Dominik Bez, ITI Wagner; Bachelor Thesis
  • Inhalt: Some routing algorithms for public transit assume that all vehicles (buses, trains, planes, etc.) depart and arrive on time, which is not a realistic scenario. This is especially true for algorithms which precompute data relying on the timetable. One such algorithm is ULTRA. ULTRA precomputes transfer shortcuts between stops of the public transit network to prepare public transit routing algorithms like RAPTOR for multi-modal scenarios which include a secondary mode of transportation (e.g., walking or cycling). These shortcuts represent a transfer between leaving a public transit vehicle and entering another. However, if the departure or arrival of a public transit vehicle is delayed, other shortcuts not precomputed by ULTRA may become necessary. The purpose of this thesis is to adapt ULTRA to a more realistic model of public transit that includes delays. The result is called DB-ULTRA and precomputes shortcuts for all possible delay scenarios within given bounds. These shortcuts can then be used by public transit routing algorithms to find optimal journeys even in those delay scenarios. We evaluate our new algorithm on the public transit networks of Switzerland and Germany and conclude that the query times are similar to ULTRA, as long as the maximum allowed delay is not too large. If both departures and arrivals can be delayed, a maximum delay of ten minutes yields half the query times of comparable multi-modal routing algorithms, whereas if only arrivals can be delayed, even a maximum delay of 30 minutes yields similar results.

Parallel FlowCutter Refinement for Hypergraph Partitioning

  • Datum: Fr, 9 Okt 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Florian Grötschla, ITI Wagner; Master Thesis
  • Inhalt: The balanced k-way hypergraph partitioning problem (HGP) has usages in a wide array of applications where performance is critical. Most partitioners use multilevel schemes that coarsen the hypergraph, find an initial partitioning and apply refinement algorithms while iteratively uncoarsening the hypergraph again. FlowCutter is a flow-based algorithm that uses the max-flow-min-cut theorem to find small cuts between blocks of the partition by solving a sequence of flow problems. This thesis presents parallelizations of flow algorithms that can be used in the weighted HyperFlowCutter framework (WHFC), an adaption of FlowCutter, that works for weighted hypergraphs, as well as an algorithm to extract smaller hypergraphs around an existing cut that are used as the input for the flow-based refinement. We also explore two approaches for parallel partitioning algorithms that use the fast sequential partitioner PaToH to find initial partitions and apply the flow-based refinement in parallel. One of them uses recursive bisection to split the hypergraph into increasingly smaller blocks, the second algorithm uses an initial k-way partition and schedules block pairs for parallel refinement steps. We conclude with an analysis of the algorithms in an experimental evaluation of our implementation. We show that our parallelized WHFC implementation provides good speed-ups and the sequential implementation of our Push-Relabel flow algorithm outperforms the existing Dinic implementation. The parallel refinement profits from the utilization of the parallel extraction and flow algorithms, resulting in a partitioner that scales well.

Approximating One-Sided Crossing Minimization with Graph Networks

  • Datum: Do, 8 Okt 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Thomas Weidmann, ITI Wagner; Bachelor Thesis
  • Inhalt: Zu einem gegeben Graphen existieren viele verschiedene Zeichnungen. In manchen Zeichnungen kann man die Beziehungen zwischen den Knoten besser erkennen als in anderen. Ein Merkmal einer guten Zeichnung eines Graphen ist die Anzahl an Kreuzungen der Kanten. Das zugehörige Optimierungsproblem heißt Kreuzungsminimierungsproblem (KMP) welches NP-schwer ist. Das einseitige Kreuzungsminimierungsproblem (EKMP) ist eine stark eingeschränkte Version davon wobei die Knoten auf zwei horizontale Linien aufgeteilt sind und gesucht ist eine Permutation der Knoten auf der oberen Linie, sodass die Anzahl der Kreuzungen minimal ist. Auch dieses Problem ist NP-schwer. Es existieren einige lang erforschte Heuristiken und wir versuchen zwei Heuristiken mit Hilfe von maschinellem Lernen zu entwickeln. Ein Ansatz startet in einer zufälligen Permutation und tauscht benachbarte Knoten um die Anzahl an Kreuzungen zu minimieren und in dem anderen Ansatz bestimmen wir den linkesten Knoten der Permutation und durch mehrfaches Anwenden dieses Vorgehens können wir eine komplette Permutation aufbauen. Wir konnten konkurrenzfähige Ansätze zu existierenden Heuristiken entwickeln, die auch auf größeren Instanzen als die Trainingsdaten (bis zu 20 Knoten) noch gut skalieren.

Sommersemester 2020

P_n-free colorings of planar graphs

  • Datum: Fr, 25 Sep 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Miriam Goetze, ITI Wagner; Bachelor Thesis
  • Inhalt: Axenovich et al. started the study of planar avoidable graphs. We say that a graph H is k-planar unavoidable if there exists a planar graph G such that every k-edge-coloring of G contains a monochromatic subgraph isomorphic to H, otherwise we call H k-planar avoidable. Similarly, we define the notion of k-outerplanar avoidable graphs. Axenovich et al. were in particular interested in 2-edge-colorings and showed that every path is 2-planar unavoidable. Building on their work, we continue the study of edge-colorings of planar graphs that do not contain a monochromatic path of a given length. Modifying a proof of Ding et al., we prove that paths of length at least 3 are 3-outerplanar avoidable and applying a result of Merker and Postle that there exists a natural number n such that paths of length at least n are 4-planar avoidable. Further, we study edge-colorings of the iterated triangulation, a specific family of planar graphs, that avoid a restricted class of long paths. Finally, we are interested in the complexity of the associated decision problem: Given a planar graph and a natural number k, is there a 3-edge-coloring that does not contain a monochromatic P_k? We attack the special case k = 2 by considering 3-regular, bridgeless, planar supergraphs.

Inclusion-Minimal Quasi-Threshold Editing

  • Datum: Fr, 18 Sep 2020, 14:30
  • Ort: SR 301
  • Vortragende(r): Luise Häuser, ITI Wagner; Bachelor Thesis
  • Inhalt: A graph is called a quasi-threshold graph if and only if it contains neither a path nor a cycle of length 4 as an induced subgraph. The quasi-threshold editing problem is concerned with the question, how to construct a quasi-threshold graph from an arbitrary graph by inserting or deleting as few edges as possible. This problem is NP-hard. Here we present an algorithm which determines an inclusion-minimal solution. Additionally, we consider how the number of edits can be further reduced in several iterations. The running time for establishing an initial editing and for each improving iteration is linear with respect to the number of nodes plus the number of edges the graph admits. Data structures for a respective implementation get introduced as well. To make convergence in a local minimum more difficult, we propose an approach how certain decisions in the algorithm can be randomized. In experiments on various testing instances, the presented algorithm leads to better results than from previously proposed heuristics for quasi-threshold editing. Further, we confirm its scalability in practice.

Complexity of Graph Drawing Problems in Relation to the Existential Theory of the Reals

  • Datum: Fr, 18 Sep 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Nicholas Bieker, ITI Wagner; Bachelor Thesis
  • Inhalt: In dieser Arbeit beschäftigen wir uns mit der Komplexitätsklasse existsR, welche über die Existentielle Theorie der Reellen Zahlen definiert wird. Das ist eine Menge von existenziell quantifizierten wahren Formeln, die aus logischen Verknüpfungen von Polynomgleichungen und Polynomungleichungen über reellen Zahlen bestehen. Das zugehörige Entscheidungsproblem, das für eine Formel dieser Struktur entscheidet, ob sie wahr ist, heißt ETR. Die entsprechende Komplexitätsklasse besteht dann aus allen Problemen, die in einer ETR-Formel in polynomieller Länge darstellbar sind. Wir definieren zuerst ETR und die zugehörige Komplexitätsklasse ausführlich und zeigen dann existsR-Vollständigkeit für das Problem DrawingOnSegments, wo wir einen gegebenen Graphen planar auf eine Anordnung von Variablensegmenten zeichnen müssen, wobei die Kanten gewisse Hindernissegmente nicht schneiden dürfen. Dafür konstruieren wir zuerst eine ETR-Formel für das Problem und führen dann eine Reduktion von einer gleichwertigen Variante von ETR durch.

Experiments on Node Orderings for Flow-Based Graph Partitioning

  • Datum: Fr, 28 Aug 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Robert Schmoltzi, ITI Wagner; Bachelor Thesis
  • Inhalt: FlowCutter and InertialFlowCutter are two flow based partitioning algorithms. While FlowCutter calculates cuts of high quality, it is rather slow. To accelerate flow calculations, InertialFlowCutter uses geographical coordinates. These coordinates are used to generate node orderings, which determine the order in which nodes are added to the source and target sides. Due to the use of geographical information, InertialFlowCutter is limited to the calculation of cuts on road graphs. In this thesis, we want to enable InertialFlowCutter to compute cuts on graphs without node coordinates. To achieve this, we generate node orderings based on clustering algorithms and algorithms which produce node coordinates. Then, we evaluate the node orderings based on the quality of cuts InertialFlowCutter finds, using the orderings, and the running time. We compare the cuts found with the orderings specifically to FlowCutter to test whether we are able to achieve an acceleration of the flow calculations. We show that the orderings produce good cuts and nested dissection orders of decent quality. However, FlowCutter produces good cuts with higher consistency and significantly better nested dissection orders. Additionally, the accumulated running times of the creation of the orderings and cut computation with InertialFlowCutter were often longer than the running times of FlowCutter. While the creation of the oderings was slow, we were able to achieve a significant speed-up of the flow calculations, both when calculating bipartitions and nested dissection orders.

Routenplanung für Lastzüge bei beschränktem Anhängereinsatz unter Berücksichtigung von Kundenzeitfenstern, Anhängerabstellplätzen und Umladezeiten

  • Datum: Fr, 31 Jul 2020, 14:00
  • Ort: SR 301/online
  • Vortragende(r): Anastasia Slobodyanik, ITI Wagner; Bachelor Thesis
  • Inhalt: Wir untersuchen das Problem der Routenplanung für Lastzüge (LKW mit Anhänger) mit beschränktem Anhängereinsatz. Einige Kunden können mit oder ohne Anhänger angefahren werden, sofern die Kapazität des LKW das zulässt. Andere Kunden können in der Praxis teilweise nur mit LKW erreicht werden. Dafür kann es unterschiedliche Gründe geben, wie zum Beispiel ein nicht ausreichender Platz für das manövrieren. Vor der Bedienung solcher Kunden wird der Anhänger auf einem Abstellplatz abgestellt. Wir lösen das Problem der Routenplanung für eine gegebene Sequenz von Kunden und einen Lastzug exakt. Dafür entwickeln wir einen pseudopolynomiellen Algorithmus mittels dynamischer Programmierung. Service-Zeitfenster, Zeiten für An- und Abkoppeln des Anhängers sowie Zeit für das Umladen der homogenen Ware vom Anhänger auf den LKW werden berücksichtigt.

Visualizing Dynamic Clustered Data Using Area-proportional Maps

  • Datum: Fr, 3 Jul 2020, 13:00
  • Ort: SR 301/Online
  • Vortragende(r): Christian Schnorr, ITI Wagner; Master Thesis
  • Inhalt: We explore how cluster information in graphs can be visualized naturally as countries on a map in a dynamic setting where the graph changes over time. We want there to be a strong correlation between a country's size and the size of the cluster it represents, and want to be able to react to dynamic changes of the graph in a way that preserves the viewer's mental model of the map. This is a challenging problem because popular algorithms for visualizing graphs as geographic-like maps struggle with clusters being fragmented across different countries on the map, and because redrawing the map for a new, albeit similar, input graph does generally not preserve the viewer's mental map. To address these issues, we propose a framework that guarantees to keep clusters as continuous regions in the generated maps and supports dynamic inputs by allowing for small, incremental updates such as inserting or removing regions over time. We do this by working on an intermediate plane graph whose vertices correspond to clusters in the input graph, the cluster graph, and constructing the map as a contact representation of this cluster graph while accounting for the dynamic changes in both the cluster graph and its contact representation. This framework can be applied to a variety of real-world applications, allowing us to visualize clusters in the underlying data and how they change over time, thereby enabling viewers of the visualization to detect trends in the data easily.

Multilevel Hypergraph Partitioning with Vertex Weights Revisited

  • Datum: Mo, 22 Jun 2020, 11:00
  • Vortragende(r): Nikolai Maas, ITI Sanders; Bachelor Thesis
  • Inhalt: We analyze the k-way partitioning problem for hypergraphs with vertex weights and specifically the task of finding a balanced partition within the multilevel context. Problems from practical applications such as VLSI design and sparse matrix-vector multiplication naturally incorporate weighted instances, but the topic is only partially covered by current state-of-the-art partitioners. We investigate existing definitions of the balance constraint for weighted hypergraphs and propose a new generalized definition. In order to construct a partitioning algorithm that guarantees a balanced solution, we examine different aspects of the multilevel paradigm. In particular, additional measures are necessary for k-way partitioning via recursive bisection. To address this, we develop an approach based on an assignment of heavy vertices as fixed vertices to both blocks of the bisection and use theoretical results to prove that the balance of the final partition can be guaranteed. Our algorithm is integrated into the hypergraph partitioner KaHyPar and is evaluated in extensive computational experiments. Unlike the competing algorithms, our configuration always computes a balanced partition on the tested instances. The solution quality is equivalent to the current version of KaHyPar while slightly improving the running time.

Scalable Radiation Model Implementation Using Shortest-Path Distances

  • Datum: Fr, 5 Jun 2020, 14:00
  • Vortragende(r): Adrian Cierpka, ITI Wagner; Bachelor Thesis
  • Inhalt: Das Verkehrsaufkommen in einer Region zu bestimmen ist keine einfache Aufgabe. Es benötigt viele Daten und die Erfahrung von Experten um hochqualitative Verkehrsdaten zu berechnen. Somit ist die Erstellung solcher Daten teuer und zeitaufwändig. Meistens werden die Ergebnisse nicht veröffenlicht und so gibt es Bedarf für Algorithmen die ein ungefähres, realistisches Verkehrsaufkommen in einer Region berechnen. Dabei dürfen solche Algorithmen nur Daten benötigen, die öffentlich verfügbar sind und müssen einfach zu bedienen sein. Die Verkehrsdaten die man mit solchen Algorithmen berechnen kann, werden in Benchmarks verwendet um Verkehrsalgorithmen zu testen. Buchhold et al. haben in ihrer Arbeit Implementierungen des Radiation-Modells vorgestellt und mit diesen gute Ergebnisse erzielt. Zwei dieser Algorithmen heißen DRAD und TRAD. DRAD überzeugt mit guten Ergebnissen, ist aber langsamer als TRAD, welcher jedoch schlechtere Ergebnisse erzielt. In dieser Arbeit stellen wir einen Algorithmus vor, der wie TRAD eine Baum-basierte Suche verwendet. Anstatt georaphischer Distanzen nutzen wir jedoch kürzeste Pfad Distanzen. Dieser Algorithmus, CRAD genannt, liefert die gleiche Ergebinsqualität wie DRAD, ist aber in den meisten Experimenten deutlich schneller. Des Weiteren zeigen wir am Ende dieser Arbeit, dass wir nur mit Daten, die öffentlich verfügbar sind gute Ergebnisse erzielen können.

Min-cost flow algorithms for the Wind Farm Cabling Problem

  • Datum: Fr, 8 Mai 2020, 14:00
  • Vortragende(r): Marc Jenne, ITI Wagner; Bachelor Thesis
  • Inhalt: The Wind Farm Cabling Problem (WCP) describes the problem of finding a suitable cabling between a set of turbines and substations in wind farms with the goal of transmitting the whole electricity produced by the turbines to the substations. While there exist numerous possibilities of feasible cablings, it is of interest to find the one that minimizes the total costs of the required cables. This problem can be modeled as a Minimum-Cost Flow Problem (MCF), a well-known problem for which multiple algorithms already exist. These algorithms are proven to find an optimal solution in polynomial time; however, they cannot be used for the WCP without adaptions because of the primary difference between both problems: while the cost function is linear in the MCF, it is a non-linear step function in the WCP. We take a closer look at some of those algorithms and examine whether they can be adapted so that they are able to provide solutions for the WCP. We describe the algorithms and their different approaches to solve the MCF and outline the problems that arise once the cost function becomes non-linear. We present our adaption of the Successive Shortest Path Algorithm and provide multiple strategies to solve the WCP with this algorithm. In an experimental evaluation, we compare the best of these strategies to a NCC algorithm and an exact MILP solver in terms of running times and quality of the found solutions.

A Comparative Analysis of Switchings in Static and Dynamic Power Grids

  • Datum: Di, 28 Apr 2020, 13:00
  • Vortragende(r): Adrian Grupp, ITI Wagner - Master's Thesis
  • Inhalt: The power grid is the largest machine humankind has ever built. However, this machine is facing wide-ranging structural change. The transition towards intensive usage of renewable energy sources introduces new challenges: How do we cope with their volatility and how can we use them as efficiently as possible? Exploiting structural properties may be one answer to this. On one hand it is known that purposefully removing transmission lines from a power grid, so called switching, can in fact resolve congestions and overloads, which can eventually lead to a higher power throughput. In the language of graph theory this can be formalized as an optimization problem on flow networks, the Maximum Transmission Switching Flow Problem. On the other hand the concern is that the power grid can be compromised by such big topological interventions as the removal of a whole transmission line. Stable operation has to be guaranteed at all times which means adhering to the network's utility frequency. The oscillator model, used in statistical physics, can be utilized to study the transient behavior of the power grid. With it we can investigate whether switchings still allow network synchronization. Additionally, small signal analysis can be used to analyze the stability of the system after the switching took place. In this work we give a comparative analysis of the two mentioned approaches. We study how optimization results from the static world of graph theory behave in the dynamic setting of real world power grids and assess if they are reasonable with regards to the stability of the network frequency. We want to shed light on the derivation of the models and give a first answer to the question whether we can safely use switching in order to improve our power grids. Where? DFNconf Meeting Room Name: Adrian Grupp Abschlussvortrag DFNconf Meeting Room Number: 979145276 DFNconf Meeting Link: https://conf.dfn.de/webapp/conference/979145276