Publication Server of Zuse Institute Berlin (ZIB)
Not a member yet
6648 research outputs found
Sort by
Beimischung von Wasserstoff zum Erdgas: Eine Kapazitätsstudie des deutschen Gasnetzes
No full textDie europäische Gasinfrastruktur wird disruptiv in ein zukünftiges dekarbonisiertes Energiesystem verändert; ein Prozess, der angesichts der jüngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, trägt zur Erhöhung der öffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Fachbeitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualität analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem
einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten genügend Kapazität bietet, um für einen großen Teil der bis 2030 geplanten Erzeugungskapazität für grünen Wasserstoff als garantierter Abnehmer zu dienen
Modeling and solving real-world transient gas network transport problems using mathematical programming
No full textThis thesis considers the transient gas network control optimization problem for on-shore pipeline-based transmission networks with numerous gas routing options.
As input, the problem is given the network's topology, its initial state, and future demands at the boundaries of the network, which prescribe the gas flow exchange and potentially the pressure values.
The task is to find a set of future control measures for all the active, i.e., controllable, elements in the network that minimizes a combination of different penalty functions.
The problem is examined in the context of a decision support tool for gas network dispatchers.
This results in detailed models featuring a diverse set of constraints, large and challenging real-world instances, and demanding time limit requirements.
All these factors further complicate the problem, which is already difficult to solve in theory due to the inherent combination of non-linear and combinatorial aspects.
Our contributions concern different steps of the process of solving the problem.
Regarding the model formulation, we investigate the validity of two common approximations of the gas flow description in transport pipes: neglecting the inertia term and assuming a friction term that linearly depends on the gas flow and the pressure.
For both, we examine if they can be applied under real-world conditions by evaluating a large amount of historical state data of the network of our project partner, the gas network operator Open Grid Europe.
While we can confirm that it is reasonable to ignore the influence of the inertia term, the friction term linearization leads to significant errors and, as a consequence, cannot be used for describing the general gas flow behavior in transport pipes.
As another topic of this thesis, we introduce the target value concept as a more realistic approach to express control actions of dispatchers regarding regulators and compressor stations.
Here, we derive the mechanisms defined for target values based on the gas flow principles in pipes and develop a mixed-integer programming model capturing their behavior.
The accuracy of this model is demonstrated in comparison to a target-value-based industry-standard simulator.
Furthermore, we present two heuristics for the transient gas network control optimization problem featuring target values that are based on approximative models for the target-value-based control and determine the final decisions in a post-processing step.
To compare the performance of the two heuristics with the approach of directly solving the corresponding model, we evaluate them on a set of artificially created test instances.
Finally, we develop problem-specific algorithms for two variants of the described problem.
One considers the control optimization for a single network station, which represents a local operation site featuring a large number of active elements.
The used transient model is very detailed and includes a sophisticated representation of the compressor stations.
Based on the shortness of the pipes in the station, the corresponding algorithm finds valid solutions by solving a series of stationary model variants as well as a transient rolling horizon approach.
As the second variant, we consider the problem on the entire network but assume an approximative model representing the control capabilities of network stations.
Aside from a new description of the compression capabilities, we introduce an algorithm that uses a combination of sequential mixed-integer programming, two heuristics based on reduced time horizons, and a specialized dynamic branch-and-bound node limit to determine promising values for the binary variables of the model.
Complete solutions for the problem are obtained by fixing the binary values and solving the remaining non-linear program.
Both algorithms are investigated in extensive empirical studies based on real-world instances of the corresponding model variants.Diese Arbeit behandelt das Optimierungsproblem der transienten Gasnetzwerksteuerung von Fernleitungsnetzen auf dem Festland mit einer großen Anzahl möglicher Gastransportrouten.
Die Eingabedaten bestehen aus der Netzwerktopologie, dem Anfangszustand des Netzes und zukünftigen Vorgaben an den Randknoten des Netzes, welche den Gaseinfluss und Gasausfluss sowie eine potenzielle Vorgabe von Druckwerten umfassen.
Gegeben diese Daten besteht die Aufgabe besteht darin, eine Menge an zukünftigen Steuerungsentscheidungen für alle aktiven, also steuerbaren, Elemente des Netzes zu finden, sodass eine Kombination von Straffunktionen minimiert wird.
Das Problem wird in dieser Arbeit im Rahmen der Erstellung eines entscheidungsunterstützenden Systems für Dispatcher betrachtet, welche das Gasnetz steuern.
Dies resultiert in einer detaillierten Modellierung mit einer Vielzahl von Nebenbedingungen, großen und herausfordernden realistischen Instanzen sowie anspruchsvollen Vorgaben zur maximalen Laufzeit.
Diese Eigenschaften erhöhen die Komplexität des Problems, welches bereits in der Theorie auf Grund der inhärenten Kombination von nichtlinearen und kombinatorischen Aspekten schwierig zu lösen ist.
Die Beiträge dieser Arbeit betreffen verschiedene Schritte des Prozesses zur Lösung des Problems.
Bezüglich der Modellformulierung werden zwei übliche Approximationen der Gasflussbeschreibung in Fernleitungsrohren auf Validität überprüft:
die Vernachlässigung des Trägheitsterms und die Annahme einer linearisierten Beschreibung des Reibungsterms.
Für beide Approximationen wird untersucht, ob sie für reale Gasflussbedingungen zulässig sind.
Dazu wird eine große Anzahl historischer Netzzustandsdaten des Gasnetzbetreibers Open Grid Europe ausgewertet.
Während bestätigt werden kann, dass eine Vernachlässigung des Trägheitsterms unter Realbedingungen angemessen ist, führt die Linearisierung des Reibungsterms zu signifikanten Fehlern und kann daher nicht für die allgemeine Beschreibung des Gasflusses in Fernleitungsrohren verwendet werden.
In einem weiteren Teil dieser Arbeit wird das Konzept der Sollwerte eingeführt.
Mit diesen ist eine realistischere Beschreibung der Steuerungsbefehle möglich, welche den Dispatchern für Regler und Verdichterstationen zur Verfügung stehen.
Der Sollwertmechanismus wird basierend auf den Gasflussprinzipien in Rohrleitungen hergeleitet, um anschließend ein gemischt-ganzzahliges Programm zu entwickeln, welches das entsprechende Verhalten erzeugt.
Die Präzision dieses Modells wird durch einen Vergleich mit einem Simulator von Industriestandard sichergestellt, welcher auf Sollwerten basiert.
Außerdem werden zwei Heuristiken für das Optimierungsproblem der transienten Gasnetzwerksteuerung mit Sollwertmodellierung vorgestellt.
Diese basieren auf approximativen Modellen für die Sollwertsteuerung und ermitteln die letztendlichen Steuerungsentscheidungen in einer nachgelagerten Routine.
Basierend auf künstlich erzeugten Testinstanzen werden die Heuristiken schließlich mit dem direkten Lösen des entsprechenden Modells verglichen.
Zudem werden in dieser Arbeit problemspezifische Algorithmen für zwei Varianten des beschriebenen Optimierungsproblems entwickelt.
Die erste Variante betrachtet das Gasnetzwerksteuerungsproblem beschränkt auf eine einzelne Netzstation, die lokale Betriebsstellen darstellen und über eine Vielzahl an aktiven Steuerungselementen verfügen.
Das entsprechende transiente Modell ist sehr detailliert und beinhaltet eine differenzierte Beschreibung der Verdichterstationen.
Der problemspezifische Algorithmus basiert auf der Kürze der Rohre innerhalb der Station und findet zulässige Lösungen durch das Lösen von stationären Varianten des Modells sowie der Nutzung eines transienten Rolling-Horizon Ansatzes.
In der zweiten Problemvariante wird das gesamte Gasnetz betrachtet, wobei eine vereinfachte Modellierung der Steuerungsmöglichkeiten innerhalb von Netzstationen angenommen wird.
Neben einer neuen Beschreibung der Verdichtungsmöglichkeiten einer Station wird ebenfalls ein problemspezifischer Algorithmus entwickelt.
Dieser erstellt aussichtsreiche Werte für die Binärvariablen und nutzt dafür eine Kombination aus sequenzieller gemischt-ganzzahliger Programmierung, zwei auf verkürzten Zeithorizonten basierenden Heuristiken und eine spezialisierte dynamische Obergrenze für die Anzahl der Branch-and-Bound-Knoten.
Diese Teillösungen werden durch eine Fixierung der binären Variablen und das anschließende Lösen des restlichen nichtlinearen Programms komplettiert.
Die Güte beider Algorithmen wird in umfangreichen empirischen Experimenten untersucht, welche reale Instanzen der jeweiligen Problemvarianten betrachten
Computational Methods for Protein Inference in Shotgun Proteomics Experiments
No full textSince the beginning of this millennium, the advent of high-throughput methods in numerous fields of the life sciences led to a shift in paradigms. A broad variety of technologies emerged that allow comprehensive quantification of molecules involved in biological processes. Simultaneously, a major increase in data volume has been recorded with these techniques through enhanced instrumentation and other technical advances. By supplying computational methods that automatically process raw data to obtain biological information, the field of bioinformatics plays an increasingly important role in the analysis of the ever-growing mass of data. Computational mass spectrometry in particular, is a bioinformatics field of research which provides means to gather, analyze and visualize data from high-throughput mass spectrometric experiments. For the study of the entirety of proteins in a cell or an environmental sample, even current techniques reach limitations that need to be circumvented by simplifying the samples subjected to the mass spectrometer. These pre-digested (so-called bottom-up) proteomics experiments then pose an even bigger computational burden during analysis since complex ambiguities need to be resolved during protein inference, grouping and quantification. In this thesis, we present several developments in the pursuit of our goal to provide means for a fully automated analysis of complex and large-scale bottom-up proteomics experiments. Firstly, due to prohibitive computational complexities in state-of-the-art Bayesian protein inference techniques, a refined, more stable technique for performing inference on sums of random variables was developed to enable a variation of standard Bayesian inference for the problem. nextflow and part of a set of standardized, well-tested, and community-maintained workflows by the nf-core collective. Our workflow runs on large-scale data with complex experimental designs and allows a one-command analysis of local and publicly available data sets with state-of-the-art accuracy on various high-performance computing environments or the cloud
WaveTrain: a Python Package for Numerical Quantum Mechanics of Chain-like Systems Based on Tensor Trains
No full textWaveTrain is an open-source software for numerical simulations of chain-like quantum systems with nearest-neighbor (NN) interactions only. The Python package is centered around tensor train (TT, or matrix product) format representations of Hamiltonian operators and (stationary or time-evolving) state vectors. It builds on the Python tensor train toolbox Scikit_tt, which provides efficient construction methods and storage schemes for the TT format. Its solvers for eigenvalue problems and linear differential equations are used in WaveTrain for the time-independent and time-dependent Schrödinger equations, respectively. Employing efficient decompositions to construct low-rank representations, the tensor-train ranks of state vectors are often found to depend only marginally on the chain length N. This results in the computational effort growing only slightly more than linearly with N, thus mitigating the curse of dimensionality. As a complement to the classes for full quantum mechanics, WaveTrain also contains classes for fully classical and mixed quantum–classical (Ehrenfest or mean field) dynamics of bipartite systems. The graphical capabilities allow visualization of quantum dynamics “on the fly,” with a choice of several different representations based on reduced density matrices. Even though developed for treating quasi-one-dimensional excitonic energy transport in molecular solids or conjugated organic polymers, including coupling to phonons, WaveTrain can be used for any kind of chain-like quantum systems, with or without periodic boundary conditions and with NN interactions only. The present work describes version 1.0 of our WaveTrain software, based on version 1.2 of scikit_tt, both of which are freely available from the GitHub platform where they will also be further developed. Moreover, WaveTrain is mirrored at SourceForge, within the framework of the WavePacket project for numerical quantum dynamics. Worked-out demonstration examples with complete input and output, including animated graphics, are available
Branching via Cutting Plane Selection: Improving Hybrid Branching
No full textCutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a decrease in solve time, and an decrease in number of nodes over affected instances of MIPLIB 2017
Design Challenges and Opportunities of Fossil Preparation Tools and Methods
No full textFossil preparation is the activity of processing paleontological specimens for research and exhibition purposes. In addition to traditional mechanical extraction of fossils, preparation presently comprises non-destructive digital methods that are part of a relatively new field, namely virtual paleontology. Despite significant technological advances, both traditional and digital preparation remain cumbersome and time-consuming endeavors. However, this field has received scarce attention from a human-computer interaction perspective. The present study aims to elucidate the state-of-the-art for paleontological fossil preparation in order to determine its main challenges and start a conversation regarding opportunities for creating novel designs that tackle the field's current issues. We conducted a qualitative study involving both technical preparators and virtual paleontologists. The study was divided into two parts: First, we assembled technical preparators and paleontology researchers in a focus group session to discuss their workflows, obtain a preliminary understanding of their issues, and ideate solutions based on their counterparts' workflows. Next, we conducted a series of contextual inquiries involving direct observation and semi-structured in-depth interviews. We transcribed our recordings and examined the data through theoretical and inductive thematic analysis, clustering emerging themes and applying concepts from human-computer interaction and related fields. Our findings report on challenges faced by traditional and digital fossil preparators and potential opportunities to improve their tools and workflows. We contribute with a novel analysis of fossil preparation from an HCI perspective
Periodic Timetabling with Cyclic Order Constraints
No full textPeriodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful
Model reduction for calcium-induced vesicle fusion dynamics
No full textIn this work, we adapt an established model for the Ca2+-induced fusion dynamics of synaptic vesicles and employ a lumping method to reduce its complexity. In the reduced system, sequential Ca2+-binding steps are merged to a single releasable state, while keeping the important dependence of the reaction rates on the local Ca2+ concentration. We examine the feasibility of this model reduction for a representative stimulus train over the physiologically relevant site-channel distances. Our findings show that the approximation error is generally small and exhibits an interesting nonlinear and non-monotonic behavior where it vanishes for very low distances and is insignificant at intermediary distances. Furthermore, we give expressions for the reduced model’s reaction rates and suggest that our approach may be used to directly compute effective fusion rates for assessing the validity of a fusion model, thereby circumventing expensive simulations
Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times
No full textThe Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice
Bravo MaRDI: A Wikibase Knowledge Graph on Mathematics
No full textMathematical world knowledge is a fundamental component of Wikidata. However, to date, no expertly curated knowledge graph has focused specifically on contemporary mathematics. Addressing this gap, the Mathematical Research Data Initiative (MaRDI) has developed a comprehensive knowledge graph that links multimodal research data in mathematics. This encompasses traditional research data items like datasets, software, and publications and includes semantically advanced objects such as mathematical formulae and hypotheses. This paper details the abilities of the MaRDI knowledge graph, which is based on Wikibase, leading up to its inaugural public release, codenamed Bravo, available on https://portal.mardi4nfdi.de