Exact dynamic programming algorithms for planning problems that are represented as partially observable Markov decision processes rely on a subroutine that removes, or ``prunes", dominated vectors from sets of vectors that represent piecewise-linear and convex value functions. The classic vector pruning subroutine solves one linear program per vector, where the number of variables is equal to the size of the state space and the number of constraints is equal to the number of vectors shown so far to be undominated. Thus, its scalability is limited not only by the number of linear programs it solves, but especially by their size. Recent work shows how to improve the performance of this vector pruning subroutine by limiting the number of constraints in the linear programs it solves, using a row-generation technique. This work shows how to further improve its performance by similarly limiting the number of variables using a column-generation technique, which improves scalability with respect to the size of the state space. This new technique allows vector pruning to be used for problems with a much larger state space than was previously possible. Additionally, the most widely used dynamic programming algorithm for solving partially observable Markov decision processes is bottlenecked by vector pruning during its cross-sum step. This work adapts geometrical insights for speeding up the cross-sum step to the row and column generation technique, showing how to improve its performance even further. These techniques speed up exact algorithms for solving POMDPs as well as related optimization problems with hidden variables for which similar vector pruning techniques are used, such as multi-objective planning problems, partially observable stochastic games, and in a recent variable elimination algorithm for influence diagrams.

With recent and continuing advances in bioinformatics, the volume of sequence data has increased tremendously. Along with this increase, there is a growing need to develop efficient algorithms to process such data in order to make useful and important discoveries. Careful analysis of genomic data will benefit science and society in numerous ways, including the understanding of protein sequence functions, early detection of diseases, and finding evolutionary relationships that exist among various organisms. Most sequence analysis problems arising from computational genomics and evolutionary biology fall into the class of NP-complete problems. Advances in exact and approximate algorithms to address these problems are critical. In this thesis, we investigate a novel graph theoretical model that deals with fundamental evolutionary problems. The model allows incorporation of the evolutionary operations ``insertion', ``deletion', and ``substitution', and various parameters such as relative distances and weights. By varying appropriate parameters and weights within the model, several important combinatorial problems can be represented, including the weighted supersequence, weighted superstring, and weighted longest common sequence problems. Consequently, our model provides a general computational framework for solving a wide variety of important and difficult biological sequencing problems, including the multiple sequence alignment problem, and the problem of finding an evolutionary ancestor of multiple sequences. In this thesis, we develop large scale combinatorial optimization techniques to solve our graph theoretical model. In particular, we formulate the problem as two distinct but related models: constrained network flow problem and weighted node packing problem. The integer programming models are solved in a branch and bound setting using simultaneous column and row generation. The methodology developed will also be useful to solve large scale integer programming problems arising in other areas such as transportation and logistics.

For over a century, the railway system has been gradually designed and adapted to serve the corresponding demands under variations of given budgets. However, recent developments indicate that the railway systems of many European countries gradually come to their limits, as the national infrastructure managers declare an increasing share of their network tracks as congested. Consequently, the capabilities of each railway system are getting more into focus, to adequately serve the recent intention of shifting more demand to rail to encounter climate change. The system’s capacity is thereby of particular interest, i. e. whether the system already has the ability to serve increasing traffic loads by leveraging existing reserves, or otherwise needs significant extensions to serve the increasing demand. We thus need to quantify the current capacity of the railway system to identify its current capabilities and to deduct corresponding measures to leverage capacity reserves and relieve saturated network parts. Only the appropriate measure selection, i.e. deciding where to apply traffic reorganization and optimization or infrastructural extensions and restructuring, allows to achieve the goal of shifting more demand to rail under limited resource constraints. The main contributions of this thesis are in the design, optimization and application of a network capacity assessment approach for large-scale railway networks, which incorporates the perspectives of infrastructure, operations and demand by using the number of trains per time window and scheduled waiting times as capacity metric. Hence, this thesis provides a new definition of network capacity, and develops petri net (PN)-based capacity assessment models for railway networks with the use of mixed integer program (MIP) and row generation. The capacity is then determined by assessing the maximum utilization and the scheduled waiting times of the railway network with respect to infrastructure, railway operations and demand. We first introduce the definition of railway network capacity, which extends the concept of railway capacity from stations and corridors to entire networks. This new utilization-based and demand-centric definition of practical railway network capacity defines railway network capacity as the maximum number of departing trains in the network over a given time period, regarding the given infrastructure, operations and demand. This definition allows to accurately determine the interplay of infrastructure, operations and demand, with a combined measure of traffic flow and scheduled waiting times. In the context of this new definition on network capacity, different assessment approaches for the capacity of railway stations, corridors and networks are reviewed with regard to their spatial scope, the used approach and the applied capacity metric. Second we propose the railway network utilization model (RNUM), which extends an existing PN based approach from single line to entire network operations. This model builds upon individual lines, which are then connected to more complex structures. The analysis of the maximum utilization is based on the network’s elementary circuits. Furthermore, token modifications are introduced to characterize relevant process circuits and introduce interline separation places to model and assess complex networks. By additionally considering rolling stock circulations and imposed train orders, the utilization is determined for given operation scenarios of a line system, which operates at heterogeneous frequencies. The resulting timetable independent approach allows to fully characterize the utilization of the network. To assess the network capacity, an enumeration-based railway network capacity (RNC) framework is further introduced, which evaluates the maximum utilization over diverse operation scenarios to represent possible network demands. The resulting train flows as well as the average scheduled waiting times per train, the capacity and the corresponding network effects were finally quantified and determined in network-specific macroscopic fundamental diagram for the railway network (MFD-R). Third, we introduce the railway network utilization MIP model (MIP-RNUM) to determine the optimal capacity utilization by combining PNs with mathematical linear programming. The presented model is enabled to simultaneously assess different train locations and line orders to provide the network’s utilization, capacity-optimal train locations and line orders for given operation scenarios. The MIP-RNUM is further improved to provide the demand-centered capacity utilization, by incorporating extended demand structures, which capture the demanded flows and magnitudes as fixed proportions of trains per line. The additional incorporation of local routing and thus optimal line orders in the utilization assessment, extend the model further to provide the optimal and demand-centered capacity utilization without the correspondingly required enumeration of different line orders. The resulting fully extended MIP-RNUM comprehensively captures the interplay of infrastructure, railway operations and demand; and the resulting effects on the network capacity. Fourth, we propose the row generation MIP-RNUM (MIP-RNUM-RG) to assess the capacity of large-scale instances. The proposed approach tackles the computationally intensive enumeration of the network’s cycles of the RNUM by applying lazy-constraint generation i.e. iteratively adding violated constraints of previous solutions to the problem in a row generating manner. To assess the solution quality of intermediate solutions during the capacity assessment of large instances, a lower-bound method is presented, which combines a higher order max-plus system and a binary search algorithm. The lower-bound method allows to check the feasibility of a given solution and to quantify the optimality gap of the current results while solving the MIP-RNUM-RG. In summary, this thesis provides multiple scientific contributions to efficiently assess the capacity of complex railway networks by developing several assessment models and frameworks. By integrating the different perspectives of infrastructure, operations and demand, this thesis supports network design towards the development of demand-centric railway systems. Regarding the intended growth of the railway demand in the near future, this thesis can guide practitioners to assess the capabilities of our present railway systems and derive the necessary actions to transform them into the transport systems of our future. / Das Eisenbahnsystem wurde über ein Jahrhundert lang entworfen und angepasst, um die jeweilige Nachfrage unter einem sich verändernden Budget zu bedienen. Aktuelle Entwicklungen zeigen jedoch, dass die Eisenbahnsysteme vieler europäischer Länder allmählich an ihre Grenzen stoßen. Zeitgleich geraten die Fähigkeiten eines jeden Eisenbahnsystems in den Fokus, mit denen zur Begegnung des Klimawandels mehr Verkehr auf die Schiene verlagert werden kann. Die Systemkapazität ist dabei von besonderem Interesse, d. h. ob das System bereits in der Lage ist, wachsende Verkehrsmengen durch die Nutzung existierender Reserven zu bewältigen, oder ob es zur Bedienung der steigenden Nachfrage einen deutlichen Ausbau braucht. Aus diesem Grund muss die Kapazität des Eisenbahnsystems bewertet werden, um damit seine aktuellen Möglichkeiten zu identifizieren und durch entsprechend abgeleitete Maßnahmen Kapazitätsreserven nutzbar zu machen und saturierte Netzteile zu entlasten. Der wesentliche Beitrag dieser Arbeit liegt im Entwurf, der Erweiterung und Anwendung eines Ansatzes zur Untersuchung der Netzwerkkapazität für großräumige Eisenbahnnetze unter Einbeziehung der Einflussfaktoren Infrastruktur, Betrieb und Nachfrage. Als Kapazitätsmetrik kommen dabei die Zugzahlen pro Zeiteinheit und die planmäßigen Wartezeiten zum Einsatz. Diese Arbeit entwirft dafür eine neue Definition der Netzwerkkapazität und entwickelt anschließend Petri-Netz (PN) basierte Untersuchungsmodelle für die Eisenbahnnetzkapazität unter Nutzung von gemischt-ganzzahliger Programmierung und Zeilengenerierung (eng. row generation). Durch die Analyse der maximalen Kapazitätsausnutzung und der planmäßigen Wartezeiten im Netz wird die Kapazität unter Berücksichtigung der Einflussfaktoren bestimmt. Zuerst wird die Definition der Eisenbahnnetzwerkkapazität eingeführt, die das Konzept der Eisenbahnkapazität von Bahnhöfen und Streckenkorridoren auf Netzwerke erweitert. Diese neue, auf Kapazitätsausnutzung basierende, nachfragezentrierte Definition der praktischen Eisenbahnnetzwerkkapazität definiert die Netzkapazität als die maximale Anzahl der im Netzwerk abfahrenden Züge innerhalb eines gegebenen Zeitintervalls, unter Berücksichtigung der gegebenen Einflussfaktoren. Im Kontext dieser neuen Definition werden verschiedene, existierende Untersuchungsansätze für die Kapazität von Eisenbahnknoten, Streckenkorridoren und Netzwerken rezensiert. Die Ansätze werden insbesondere hinsichtlich ihres räumlichen Umfangs, des angewendeten Verfahrens und der jeweils genutzten Kapazitätsmetrik verglichen. Als Zweites wird das Eisenbahnnetzwerkausnutzungsmodell (eng. railway network utilization model – RNUM) präsentiert, das einen existierenden PN-Ansatz von einer einzelnen Linie auf Netzwerke erweitert. Dieses Modell setzt sich aus einzelnen Linien zusammen, die zu komplexeren Strukturen zusammengesetzt werden. Die Analyse der maximalen Kapazitätsausnutzung basiert auf den Elementarkreisen des entstehenden Netzwerks. Durch die zusätzliche Berücksichtigung von Fahrzeugumläufen und vorgegebenen Zugfolgen wird die Kapazitätsausnutzung für gegebene Betriebsszenarien eines Liniensystems bestimmt, in welchem die Linien mit heterogenen Taktzeiten verkehren. Der resultierende, fahrplanunabhängige Ansatz erlaubt die vollständige Charakterisierung der maximalen Kapazitätsausnutzung unter Berücksichtigung diverser Betriebsszenarien. Die resultierenden Zugverkehrsströme und die mittleren planmäßigen Wartezeiten pro Zug, die ermittelte Kapazität und die zugehörigen Netzwerkeffekte werden schließlich in einem netzwerkspezifischen makroskopischen Fundamentaldiagram für Eisenbahnnetzwerke (MFD-R) bestimmt. Als Drittes wird das Eisenbahnnetzwerkausnutzungs-MIP-modell (MIP-RNUM) eingeführt, um die optimale Kapazitätsausnutzung durch eine Kombination von PN und linearer Programmierung zu bestimmen. Das eingeführte Modell kann simultan verschiedene Zugpositionen und Zugfolgen berücksichtigen, um auf deren Grundlage die Netzwerkausnutzung, kapazitätsoptimale Zugpositionen und -folgen für gegebene Betriebsszenarien zu untersuchen. Im Folgenden wird das MIP-RNUM erweitert, um die nachfragezentrierte Kapazitätsausnutzung zu erfassen. Die zusätzliche Berücksichtigung von variablen Fahrwegen in Knoten und den zugehörigen optimalen Zugfolgen in der Ausnutzungsuntersuchung ergänzen das Modell zusätzlich, um die optimale und nachfragezentrierte Kapazitätsausnutzung ohne die bisher benötigte Enumeration der Zugfolgen zu ermitteln. Das resultierende erweiterte MIP-RNUM erfasst das Zusammenspiel von Infrastruktur, Eisenbahnbetrieb und Nachfrage und deren umfassende Auswirkungen auf die Netzwerkkapazität. Zuletzt wird das zeilengenerierende MIP-RNUM (MIP-RNUM-RG) vorgestellt, um auch die Kapazität großräumiger Instanzen untersuchen zu können. Der vorgestellte Ansatz begegnet der rechenzeitintensiven Enumeration der Elementarkreise des RNUM mit einer sog. lazy constraint generation, d. h. der iterativen, zeilengenerierenden Ergänzung verletzter Nebenbedingungen zum Problem. Um bei der Untersuchung großräumiger Instanzen die Lösungsqualität der jeweiligen Zwischenergebnisse beurteilen zu können, wird eine untere Schranke vorgestellt, die ein max-plus System höherer Ordnung mit einem binären Suchalgorithmus kombiniert. Diese untere Schranke ermöglicht die Zulässigkeitsprüfung einer gegebenen Lösung und darüber hinaus die Quantifizierung der Optimalitätslücke der aktuellen Ergebnisse. Damit stellt diese Arbeit verschiedene wissenschaftliche Beiträge in Form unterschiedlicher Untersuchungsmodelle und -methoden bereit, um die Kapazität komplexer Eisenbahnnetzwerke zu untersuchen. Dabei werden die verschiedenen infrastrukturellen, betrieblichen und nachfragespezifischen Perspektiven integriert betrachtet, um die nachfragezentrierte Netzentwicklung von Eisenbahnsystemen zu unterstützen. Unter Berücksichtigung des Wachstums der Eisenbahnnachfrage in naher Zukunft kann diese Arbeit so Planer*innen helfen, die Fähigkeiten unserer gegenwärtigen Eisenbahnsysteme zu untersuchen und daraus die nötigen Handlungsalternativen abzuleiten, um die Verkehrssysteme unserer Zukunft zu entwickeln.