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 - 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 - Beckenbach, Isabel A1 - Peis, Britta A1 - Schaudt, Oliver A1 - Scheidweiler, Robert T1 - A Combinatorial Proof of a König-type Theorem for Unimodular Hypergraphs N2 - We state purely combinatorial proofs for König- and Hall-type theorems for a wide class of combinatorial optimization problems. Our methods rely on relaxations of the matching and vertex cover problem and, moreover, on the strong coloring properties admitted by bipartite graphs and their generalizations. T3 - ZIB-Report - 17-27 KW - Packing KW - Covering KW - Total Unimodularity KW - König's Theorem KW - Factors Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64017 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Scheidweiler, Robert T1 - Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach N2 - We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard. T3 - ZIB-Report - 16-22 KW - perfect f-matchings in hypergraphs KW - f-factors in hypergraphs KW - mengerian hypergraph KW - balanced hypergraph KW - perfect hypergraph KW - Hall's Theorem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59071 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Hatzel, Meike A1 - Wiederrecht, Sebastian T1 - The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs N2 - The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lovász on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable. T3 - ZIB-Report - 18-61 KW - uniform hypergraphs KW - perfect matchings KW - tight cuts Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71149 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - A Hall Condition for Normal Hypergraphs N2 - Conforti, Cornuéjols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs. T3 - ZIB-Report - 15-45 KW - Matchings in hypergraphs KW - Normal hypergraphs KW - Hall condition Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56175 SN - 1438-0064 ER -