Library

Description: 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.

Description: 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.

Description: The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an opportunity for high-achieving graduate-level students to work in teams on a real-world research project proposed by a sponsor from industry or the public sector. Each G-RIPS team consists of four international students (two from the US and two from European universities), an academic mentor, and an industrial sponsor. This is the report of the Rail-Lab project on the definition and integration of robustness aspects into optimizing rolling stock schedules. In general, there is a trade-off for complex systems between robustness and efficiency. The ambitious goal was to explore this trade-off by implementing numerical simulations and developing analytic models. In rolling stock planning a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects, have to be considered in an integrated model. General hypergraphs provide the modeling power to tackle those requirements. Furthermore, integer programming approaches are able to produce high quality solutions for the deterministic problem. When stochastic time delays are considered, the mathematical programming problem is much more complex and presents additional challenges. Thus, we started with a basic variant of the deterministic case, i.e., we are only considering hypergraphs representing vehicle composition and regularity. We transfered solution approaches for robust optimization from the airline industry to the setting of railways and attained a reasonable measure of robustness. Finally, we present and discuss different methods to optimize this robustness measure.

Description: Vehicle rotation planning for long distance passenger railways is a fundamental problem in rail transport. It deals with the allocation of vehicles to trips in a cyclic weekly schedule. Its result is an assignment of each trip to a follow-on trip which will be serviced by the same vehicle. To take so-called regularity, which is an important requirement, into account, vehicle rotation planning can be modeled as a hyperassignment problem. This is a generalization of the assignment problem to directed hypergraphs we propose. We prove that the hyperassignment problem is NP-hard for the practically relevant cases and that the canonical integer linear programming (ILP) formulation results in large integrality gaps and arbitrarily high basis matrix determinants. Our main contribution is an extended ILP formulation, which provably implies important classes of inequalities, e. g., all clique inequalities. Clique inequalities are of great importance, because as calculations with practical data show they highly reduce the LP-IP gap. The extended formulation can be solved by column generation. We propose fast combinatorial algorithms for the pricing subproblem.

Description: 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.

Description: 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.

Description: 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.

Description: The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinato- rial optimization problems: the traveling salesman and the linear ordering problem. In this paper we present several possible IP-Models for this problem and compared them to their usability for branch-and-cut approaches.

Description: 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.

Description: 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.

Description: 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.