TY - THES A1 - Beckenbach, Isabel T1 - Matchings and Flows in Hypergraphs N2 - In this dissertation, we study matchings and flows in hypergraphs using combinatorial methods. These two problems are among the best studied in the field of combinatorial optimization. As hypergraphs are a very general concept, not many results on graphs can be generalized to arbitrary hypergraphs. Therefore, we consider special classes of hypergraphs, which admit more structure, to transfer results from graph theory to hypergraph theory. In Chapter 2, we investigate the perfect matching problem on different classes of hypergraphs generalizing bipartite graphs. First, we give a polynomial time approximation algorithm for the maximum weight matching problem on so-called partitioned hypergraphs, whose approximation factor is best possible up to a constant. Afterwards, we look at the theorems of König and Hall and their relation. Our main result is a condition for the existence of perfect matchings in normal hypergraphs that generalizes Hall’s condition for bipartite graphs. In Chapter 3, we consider perfect f-matchings, f-factors, and (g,f)-matchings. We prove conditions for the existence of (g,f)-matchings in unimodular hypergraphs, perfect f-matchings in uniform Mengerian hypergraphs, and f-factors in uniform balanced hypergraphs. In addition, we give an overview about the complexity of the (g,f)-matching problem on different classes of hypergraphs generalizing bipartite graphs. In Chapter 4, we study the structure of hypergraphs that admit a perfect matching. We show that these hypergraphs can be decomposed along special cuts. For graphs it is known that the resulting decomposition is unique, which does not hold for hypergraphs in general. However, we prove the uniqueness of this decomposition (up to parallel hyperedges) for uniform hypergraphs. In Chapter 5, we investigate flows on directed hypergraphs, where we focus on graph-based directed hypergraphs, which means that every hyperarc is the union of a set of pairwise disjoint ordinary arcs. We define a residual network, which can be used to decide whether a given flow is optimal or not. Our main result in this chapter is an algorithm that computes a minimum cost flow on a graph-based directed hypergraph. This algorithm is a generalization of the network simplex algorithm. N2 - Diese Arbeit untersucht Matchings und Flüsse in Hypergraphen mit Hilfe kombinatorischer Methoden. In Graphen gehören diese Probleme zu den grundlegendsten der kombinatorischen Optimierung. Viele Resultate lassen sich nicht von Graphen auf Hypergraphen verallgemeinern, da Hypergraphen ein sehr abstraktes Konzept bilden. Daher schauen wir uns bestimmte Klassen von Hypergraphen an, die mehr Struktur besitzen, und nutzen diese aus um Resultate aus der Graphentheorie zu übertragen. In Kapitel 2 betrachten wir das perfekte Matchingproblem auf Klassen von „bipartiten“ Hypergraphen, wobei es verschiedene Möglichkeiten gibt den Begriff „bipartit“ auf Hypergraphen zu definieren. Für sogenannte partitionierte Hypergraphen geben wir einen polynomiellen Approximationsalgorithmus an, dessen Gütegarantie bis auf eine Konstante bestmöglich ist. Danach betrachten wir die Sätze von Konig und Hall und untersuchen deren Zusammenhang. Unser Hauptresultat ist eine Bedingung für die Existenz von perfekten Matchings auf normalen Hypergraphen, die Halls Bedingung für bipartite Graphen verallgemeinert. Als Verallgemeinerung von perfekten Matchings betrachten wir in Kapitel 3 perfekte f-Matchings, f-Faktoren und (g, f)-Matchings. Wir beweisen Bedingungen für die Existenz von (g, f)-Matchings auf unimodularen Hypergraphen, perfekten f-Matchings auf uniformen Mengerschen Hypergraphen und f-Faktoren auf uniformen balancierten Hypergraphen. Außerdem geben wir eine Übersicht über die Komplexität des (g, f)-Matchingproblems auf verschiedenen Klassen von Hypergraphen an, die bipartite Graphen verallgemeinern. In Kapitel 4 untersuchen wir die Struktur von Hypergraphen, die ein perfektes Matching besitzen. Wir zeigen, dass diese Hypergraphen entlang spezieller Schnitte zerlegt werden können. Für Graphen weiß man, dass die so erhaltene Zerlegung eindeutig ist, was im Allgemeinen für Hypergraphen nicht zutrifft. Wenn man jedoch uniforme Hypergraphen betrachtet, dann liefert jede Zerlegung die gleichen unzerlegbaren Hypergraphen bis auf parallele Hyperkanten. Kapitel 5 beschäftigt sich mit Flüssen in gerichteten Hypergraphen, wobei wir Hypergraphen betrachten, die auf gerichteten Graphen basieren. Das bedeutet, dass eine Hyperkante die Vereinigung einer Menge von disjunkten Kanten ist. Wir definieren ein Residualnetzwerk, mit dessen Hilfe man entscheiden kann, ob ein gegebener Fluss optimal ist. Unser Hauptresultat in diesem Kapitel ist ein Algorithmus, um einen Fluss minimaler Kosten zu finden, der den Netzwerksimplex verallgemeinert. KW - Matchings KW - Balanced Hypergraphs KW - Normal Hypergraphs KW - Mengerian Hypergraphs KW - Factors KW - Tight Cuts KW - Network Flows Y1 - 2019 UR - http://nbn-resolving.de/urn:nbn:de:kobv:188-refubium-24385-6 ER - TY - THES A1 - Reuther, Markus T1 - Mathematical Optimization of Rolling Stock Rotations N2 - We show how to optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical ptimization problem is called rolling stock rotation problem (RSRP) and the leitmotiv of the thesis is RotOR, i.e., a highly integrated optimization algorithm for the RSRP. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. In this application, RSRPs have to be solved which (A) require many different aspects to be simultaneously considered, (B) are typically of large scale, and (C) include constraints that have a difficult combinatorial structure. This thesis suggests answers to these issues via the following concepts. (A) The main model, which RotOR uses, relies on a hypergraph. The hypergraph provides an easy way to model manifold industrial railway requirements in great detail. This includes well known vehicle composition requirements as well as relatively unexplored regularity stipulations. At the same time, the hypergraph directly leads to a mixed-integer programming (MIP) model for the RSRP. (B) The main algorithmic ingredient to solve industrial instances of the RSRP is a coarse-to-fine (C2F) column generation procedure. In this approach, the hypergraph is layered into coarse and fine layers that distinguish different levels of detail of the RSRP. The coarse layers are algorithmically utilized while pricing fine columns until proven optimality. Initially, the C2F approach is presented in terms of pure linear programming in order to provide an interface for other applications. (C) Rolling stock rotations have to comply to resource constraints in order to ensure, e.g., enough maintenance inspections along the rotations. These constraints are computationally hard, but are well known in the literature on the vehicle routing problem (VRP). We define an interface problem in order to bridge between the RSRP and the VRP and derive a straightforward algorithmic concept, namely regional search (RS), from their common features and, moreover, differences. Our RS algorithms show promising results for classical VRPs and RSRPs. In the first part of the thesis we present these concepts, which encompass its main mathematical contribution. The second part explains all modeling and solving components of RotOR that turn out to be essential in its industrial application. The thesis concludes with a solution to a complex re-optimization RSRP that RotOR has computed successfully for DBF. In this application all ICE vehicles of the ICE-W fleets of DBF had to be redirected past a construction site on a high-speed line in the heart of Germany. Y1 - 2017 UR - https://depositonce.tu-berlin.de/handle/11303/6309 ER -