TY - GEN A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Aggregation Methods for Railway Networks N2 - In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run. T3 - ZIB-Report - 10-23 KW - makroskopische Bahnmodellierung KW - Netzwerkaggregation KW - macroscopic railway modeling KW - network aggregation Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11881 UR - http://www.sciencedirect.com/science/article/pii/S2210970611000047 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Railway Track Allocation by Rapid Branching N2 - The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported. T3 - ZIB-Report - 10-22 KW - Trassenallokationsproblem KW - Ganzzahlige Programmierung KW - Rapid-Branching-Heuristik KW - Proximale Bündelmethode KW - Optimization KW - Railway Track Allocation KW - Bundle Method KW - Rapid Branching Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11864 SN - 1438-0064 ER - TY - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - The Random Hypergraph Assignment Problem T2 - Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013 N2 - The analysis of random instances of a combinatorial optimization problem, especially their optimal values, can provide a better insight into its structure. Such an extensive analysis was theoretically and practically done for the assignment problem ("random assignment problem") and several of its generalizations. For a recent generalization of the assignment problem to bipartite hypergraphs, the hypergraph assignment problem, such results do not exist so far. We consider a random version of the hypergraph assignment problem for the simplest possible complete bipartite hypergraphs. They have only edges and proper hyperedges of size four and follow a special structure, but the hypergraph assignment problem for this type of hypergraphs is, however, already NP-hard. It can be viewed as a combination of two assignment problems. For random hyperedge costs exponentially i.i.d. with mean 1 we show computational results that suggest that the expected value of minimum cost hyperassignments converges to some value around 1.05 with a small standard deviation. The computational results also suggest that the optimal value is most probably attained with half of the maximum possible number of proper hyperedges. The main result of this paper is the proof that the expected value of a minimum cost hyperassignment which uses exactly half the possible maximum number of proper hyperedges if the vertex number tends to infinity lies between 0.3718 and 1.8310 when hyperedge costs are exponentially i.i.d. with mean 1. Y1 - 2013 SP - 599 EP - 602 ER - TY - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning T2 - Operations Research Proceedings 2011 N2 - Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially. Y1 - 2012 SP - 59 EP - 64 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Muñoz, J. C. ED - Voß, S. T1 - Vehicle Rotation Planning for Intercity Railways JF - Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12) N2 - This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers. Y1 - 2012 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Railway Track Allocation -- Simulation, Aggregation, and Optimization JF - Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011) N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-27963-8 VL - 2 IS - 148 SP - 53 EP - 70 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Hypergraph Model for Railway Vehicle Rotation Planning JF - 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved. Y1 - 2011 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2011.146 VL - OpenAccess Series in Informatics (OASIcs) IS - 20 SP - 146 EP - 155 ER - TY - JOUR A1 - Schlechte, Thomas A1 - Borndörfer, Ralf A1 - Erol, Berkan A1 - Graffagnino, Thomas A1 - Swarat, Elmar T1 - Micro–macro transformation of railway networks JF - Journal of Rail Transport Planning & Management N2 - In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run. Y1 - 2011 U6 - https://doi.org/10.1016/j.jrtpm.2011.09.001 VL - 1 IS - 1 SP - 38 EP - 48 ER - TY - THES A1 - Beckenbach, Isabel T1 - Special cases of the hypergraph assignment problem N2 - In this thesis we investigate the hyperassignment problem with a special focus on connections to the theory of hypergraphs, in particular balanced and normal hyper- graphs, as well as its relation to the Stable Set Problem. The main point is the investigation of the matching and perfect matching polytope for partitioned hypergraphs. Therefore, valid inequalities, facets, and the dimension of some polytopes are given. Furthermore, we show that the trivial LP-relaxation of the Hyperassignment Problem obtained by relaxing x_i ∈ {0, 1} by 0 ≤ x_i ≤ 1 has an arbitrarily large integrality gap, even after adding all clique inequalities. Whereas the integrality gap of the trivial LP-relaxation of the maximum weight matching problem for partitioned hypergraphs with maximum part size M is at most 2M − 1. Additionally, computational results for small partitioned hypergraphs of part size two are presented. Using symmetry it was possible to calculate all minimal fractional vertices of the fractional perfect matching polytope of partitioned hypergraphs with part size two having at most twelve vertices. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42480 ER - TY - GEN A1 - Heismann, Olga A1 - Hildenbrandt, Achim A1 - Silvestri, Francesco A1 - Reinelt, Gerhard A1 - Borndörfer, Ralf T1 - HUHFA: A Framework for Facet Classification N2 - Usually complete linear descriptions of polytopes consist of an enormous number of facet-defining inequalities already for very small problem sizes. In this paper, we describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of a polytope. We propose an algorithm for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem. T3 - ZIB-Report - 13-45 KW - facet classification KW - symmetry KW - polyhedral structure Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42230 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Railway Track Allocation - Simulation, Aggregation, and Optimization N2 - Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data. T3 - ZIB-Report - 11-35 KW - railway models, railway capacity, track allocation framework Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14031 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Heismann, Olga T1 - Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning N2 - Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially. T3 - ZIB-Report - 11-46 KW - hyperassignments KW - vehicle rotation planning Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14564 UR - http://link.springer.com/chapter/10.1007%2F978-3-642-29210-1_10 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Erlebach, Thomas ED - Lübbecke, Marco T1 - Railway Track Allocation by Rapid Branching T2 - Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Y1 - 2010 UR - http://drops.dagstuhl.de/opus/volltexte/2010/2746 U6 - https://doi.org/http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.13 VL - 14 SP - 13 EP - 23 PB - Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Heismann, Olga T1 - The hypergraph assignment problem JF - Discrete Optimization Y1 - 2015 U6 - https://doi.org/10.1016/j.disopt.2014.11.002 VL - 15 SP - 15 EP - 25 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - An Approximation Result for Matchings in Partitioned Hypergraphs N2 - We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$. T3 - ZIB-Report - 14-30 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51083 ER - TY - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - A Generalization of Odd Set Inequalities for the Set Packing Problem T2 - Operations Research Proceedings 2013 N2 - The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning. Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-07001-8_26 SP - 193 EP - 199 ER - TY - GEN A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - A Generalization of Odd Set Inequalities for the Set Packing Problem N2 - The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning. T3 - ZIB-Report - 14-28 KW - set packing KW - matching KW - hypergraph KW - inequality KW - facet Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51010 SN - 1438-0064 ER - TY - THES A1 - Heismann, Olga T1 - The Hypergraph Assignment Problem N2 - This thesis deals with the hypergraph assignment problem (HAP), a set partitioning problem in a special type of hypergraph. The HAP generalizes the assignment problem from bipartite graphs to what we call bipartite hypergraphs, and is motivated by applications in railway vehicle rotation planning. The main contributions of this thesis concern complexity, polyhedral results, analyses of random instances, and primal methods for the HAP. We prove that the HAP is NP-hard and APX-hard even for small hyperedge sizes and hypergraphs with a special partitioned structure. We also study the complexity of the set packing and covering relaxations of the HAP, and present for certain cases polynomial exact or approximation algorithms. A complete linear description is known for the assignment problem. We therefore also study the HAP polytope. There, we have a huge number of facet-defining inequalities already for a very small problem size. We describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of the polytope. We propose the algorithm "HUHFA" for the classification that is applicable not only to the HAP but combinatorial optimization problems involving symmetries in general. In the largest possible HAP instance for which we could calculate the complete linear description, we have 14049 facets, which can be divided into 30 symmetry classes. We can combinatorially interpret 16 of these classes. This is possible by employing cliques to generalize the odd set inequalities for the matching problem. The resulting inequalities are valid for the polytope associated with the set packing problem in arbitrary hypergraphs and have a clear combinatorial meaning. An analysis of random instances provides a better insight into the structure of hyperassignments. Previous work has extensively analyzed random instances for the assignment problem theoretically and practically. As a generalization of these results for the HAP, we prove bounds on the expected value of a minimum cost hyperassignment that uses half of the maximum possible number of hyperedges that are not edges. In a certain complete partitioned hypergraph G2,2n with i. i. d. exponential random variables with mean 1 as hyperedge costs it lies between 0.3718 and 1.8310 if the vertex number tends to infinity. Finally, we develop an exact combinatorial solution algorithm for the HAP that combines three methods: A very large-scale neighborhood search, the composite columns method for the set partitioning problem, and the network simplex algorithm. N2 - Diese Arbeit beschäftigt sich mit dem Hypergraph Assignment Problem (Abkürzung "HAP", dt.: Zuordnungsproblem auf Hypergraphen), einem Mengenzerlegungsproblem auf einem speziellen Typ von Hypergraphen. Das HAP verallgemeinert das Zuordnungsproblem von bipartiten Graphen auf eine Struktur, die wir bipartite Hypergraphen nennen, und ist durch eine Anwendung in der Umlaufplanung im Schienenverkehr motiviert. Die Hauptresultate betreffen die Komplexität, polyedrische Ergebnisse, die Analyse von Zufallsinstanzen sowie primale Methoden für das HAP. Wir beweisen, dass das HAP NP-schwer und APX-schwer ist, sogar wenn wir uns auf kleine Hyperkantengrößen und Hypergraphen mit einer speziellen, partitionierten Struktur beschränken. Darüber hinaus untersuchen wir die Komplexität der Mengenpackungs- sowie Mengenüberdeckungsrelaxierung und geben für bestimmte Fälle Approximations- und exakte Algorithmen mit einer polynomiellen Laufzeit an. Für das Polytop des Zuordnungsproblems ist eine vollständige lineare Beschreibung bekannt. Wir untersuchen daher auch das HAP-Polytop. Dafür ist die Anzahl der Facettenungleichungen schon für sehr kleine Problemgrößen sehr groß. Wir beschreiben eine Methode zur Aufteilung der Ungleichungen in Äquivalenzklassen, die ohne die Verwendung von Normalformen auskommt. Die Facetten in jeder Klasse können durch Symmetrien ineinander überführt werden. Es genügt, einen Repräsentanten aus jeder Klasse anzugeben, um ein vollständiges Bild der Polytopstruktur zu erhalten. Wir beschreiben den Algorithmus "HUHFA", der diese Klassifikation nicht nur für das HAP, sondern für beliebige kombinatorische Optimierungsprobleme, die Symmetrien enthalten, durchführt. Die größtmögliche HAP-Instanz, für die wir die vollständige lineare Beschreibung berechnen konnten, hat 14049 Facetten, die in 30 Symmetrieklassen aufgeteilt werden können. Wir können 16 dieser Klassen kombinatorisch interpretieren. Dafür verallgemeinern wir Odd-Set-Ungleichungen für das Matchingproblem unter Verwendung von Cliquen. Die Ungleichungen, die wir erhalten, sind gültig für Mengenpackungsprobleme in beliebigen Hypergraphen und haben eine klare kombinatorische Bedeutung. Die Analyse von Zufallsinstanzen erlaubt einen besseren Einblick in die Struktur von Hyperzuordnungen. Eine solche ausführliche Analyse wurde in der Literatur theoretisch und praktisch bereits für das Zuordnungsproblem durchgeführt. Als eine Verallgemeinerung dieser Ergebnisse für das HAP beweisen wir Schranken für den Erwartungswert einer Hyperzuordnung mit minimalen Kosten, die genau die Hälfte der maximal möglichen Anzahl an Hyperkanten, die keine Kanten sind, benutzt. In einem sog. vollständigen partitionierten Hypergraphen G2,2n mit Hyperkantenkosten, die durch unabhängig identisch exponentiell verteilte Zufallsvariablen mit Erwartungswert 1 bestimmt sind, liegt dieser Wert zwischen 0.3718 und 1.8310, wenn die Knotenanzahl gegen unendlich strebt. Schließlich entwickeln wir eine exakte kombinatorische Lösungsmethode für das HAP, die drei Ansätze kombiniert: Eine Nachbarschaftssuche mit Nachbarschaften exponentieller Größe, die Composite-Columns-Methode für das Mengenzerlegungsproblem sowie den Netzwerksimplexalgorithmus. KW - assignment KW - bipartite KW - hyperassignment KW - hypergraph KW - set partitioning Y1 - 2014 UR - http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/5321 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Heismann, Olga T1 - The Hypergraph Assignment Problem N2 - The hypergraph assignment problem (HAP) is the generalization of assignments from directed graphs to directed hypergraphs. It serves, in particular, as a universal tool to model several train composition rules in vehicle rotation planning for long distance passenger railways. We prove that even for problems with a small hyperarc size and hypergraphs with a special partitioned structure the HAP is NP-hard and APX-hard. Further, we present an extended integer linear programming formulation which implies, e. g., all clique inequalities. T3 - ZIB-Report - 12-14 KW - directed hypergraphs KW - hyperassignment KW - assignment Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14822 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Vehicle Rotation Planning for Intercity Railways N2 - This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers. T3 - ZIB-Report - 12-11 KW - rolling-stock-planning KW - mixed-integer-programming KW - hypergraphs KW - column generation KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14731 SN - 1438-0064 ER -