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 - 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 -