Library

Description: Modern methods of simulating molecular systems are based on the mathematical theory of Markov operators with a focus on autonomous equilibrated systems. However, non-autonomous physical systems or non-autonomous simulation processes are becoming more and more important. A representation of non-autonomous Markov jump processes is presented as autonomous Markov chains on space-time. Augmenting the spatial information of the embedded Markov chain by the temporal information of the associated jump times, the so-called augmented jump chain is derived. The augmented jump chain inherits the sparseness of the infinitesimal generator of the original process and therefore provides a useful tool for studying time-dependent dynamics even in high dimensions. Furthermore, possible generalizations and applications to the computation of committor functions and coherent sets in the non-autonomous setting are discussed. After deriving the theoretical foundations, the concepts with a proof-of-concept Galerkin discretization of the transfer operator of the augmented jump chain applied to simple examples are illustrated.

Description: This paper studies time-inhomogeneous nonequilibrium diffusion processes, including both Brownian dynamics and Langevin dynamics. We derive upper bounds of the relative entropy production of the time-inhomogeneous process with respect to the transient invariant probability measures. We also study the time reversal of the reverse process in Crooks' fluctuation theorem. We show that the time reversal of the reverse process coincides with the optimally controlled forward process that leads to zero variance importance sampling estimator based on Jarzynski's equality.

Description: Calculating averages with respect to probability measures on submanifolds is often necessary in various application areas such as molecular dynamics, computational statistical mechanics and Bayesian statistics. In recent years, various numerical schemes have been proposed in the literature to study this problem based on appropriate reversible constrained stochastic dynamics. In this paper we present and analyse a non-reversible generalisation of the projection-based scheme developed by one of the authors [ESAIM: M2AN, 54 (2020), pp. 391-430]. This scheme consists of two steps - starting from a state on the submanifold, we first update the state using a non-reversible stochastic differential equation which takes the state away from the submanifold, and in the second step we project the state back onto the manifold using the long-time limit of a ordinary differential equation. We prove the consistency of this numerical scheme and provide quantitative error estimates for estimators based on finite-time running averages. Furthermore, we present theoretical analysis which shows that this scheme outperforms its reversible counterpart in terms of asymptotic variance. We demonstrate our findings on an illustrative test example.

Description: We present a method based on a generative model for detection of disturbances such as prosthesis, screws, zippers, and metals in 2D radiographs. The generative model is trained in an unsupervised fashion using clinical radiographs as well as simulated data, none of which contain disturbances. Our approach employs a latent space consistency loss which has the benefit of identifying similarities, and is enforced to reconstruct X-rays without disturbances. In order to detect images with disturbances, an anomaly score is computed also employing the Frechet distance between the input X-ray and the reconstructed one using our generative model. Validation was performed using clinical pelvis radiographs. We achieved an AUC of 0.77 and 0.83 with clinical and synthetic data, respectively. The results demonstrated a good accuracy of our method for detecting outliers as well as the advantage of utilizing synthetic data.

Description: Three-dimensional medical imaging enables detailed understanding of osteoarthritis structural status. However, there remains a vast need for automatic, thus, reader-independent measures that provide reliable assessment of subject-specific clinical outcomes. To this end, we derive a consistent generalization of the recently proposed B-score to Riemannian shape spaces. We further present an algorithmic treatment yielding simple, yet efficient computations allowing for analysis of large shape populations with several thousand samples. Our intrinsic formulation exhibits improved discrimination ability over its Euclidean counterpart, which we demonstrate for predictive validity on assessing risks of total knee replacement. This result highlights the potential of the geodesic B-score to enable improved personalized assessment and stratification for interventions.

Description: We present a method for the quantification of knee alignment from full-leg X-Rays. A state-of-the-art object detector, YOLOv4, was trained to locate regions of interests (ROIs) in full-leg X-Ray images for the hip joint, the knee, and the ankle. Residual neural networks (ResNets) were trained to regress landmark coordinates for each ROI.Based on the detected landmarks the knee alignment, i.e., the hip-knee-ankle (HKA) angle, was computed. The accuracy of landmark detection was evaluated by a comparison to manually placed landmarks for 360 legs in 180 X-Rays. The accuracy of HKA angle computations was assessed on the basis of 2,943 X-Rays. Results of YARLA were compared to the results of two independent image reading studies(Cooke; Duryea) both publicly accessible via the Osteoarthritis Initiative. The agreement was evaluated using Spearman's Rho, and weighted kappa as well as regarding the correspondence of the class assignment (varus/neutral/valgus). The average difference between YARLA and manually placed landmarks was less than 2.0+- 1.5 mm for all structures (hip, knee, ankle). The average mismatch between HKA angle determinations of Cooke and Duryea was 0.09 +- 0.63°; YARLA resulted in a mismatch of 0.10 +- 0.74° compared to Cooke and of 0.18 +- 0.64° compared to Duryea. Cooke and Duryea agreed almost perfectly with respect to a weighted kappa value of 0.86, and showed an excellent reliability as measured by a Spearman's Rho value of 0.99. Similar values were achieved by YARLA, i.e., a weighted kappa value of0.83 and 0.87 and a Spearman's Rho value of 0.98 and 0.99 to Cooke and Duryea,respectively. Cooke and Duryea agreed in 92% of all class assignments and YARLA did so in 90% against Cooke and 92% against Duryea. In conclusion, YARLA achieved results comparable to those of human experts and thus provides a basis for an automated assessment of knee alignment in full-leg X-Rays.

Description: Three-dimensional medical imaging enables detailed understanding of osteoarthritis structural status. However, there remains a vast need for automatic, thus, reader-independent measures that provide reliable assessment of subject-specific clinical outcomes. To this end, we derive a consistent generalization of the recently proposed B-score to Riemannian shape spaces. We further present an algorithmic treatment yielding simple, yet efficient computations allowing for analysis of large shape populations with several thousand samples. Our intrinsic formulation exhibits improved discrimination ability over its Euclidean counterpart, which we demonstrate for predictive validity on assessing risks of total knee replacement. This result highlights the potential of the geodesic B-score to enable improved personalized assessment and stratification for interventions.

Description: We present a novel approach for nonlinear statistical shape modeling that is invariant under Euclidean motion and thus alignment-free. By analyzing metric distortion and curvature of shapes as elements of Lie groups in a consistent Riemannian setting, we construct a framework that reliably handles large deformations. Due to the explicit character of Lie group operations, our non-Euclidean method is very efficient allowing for fast and numerically robust processing. This facilitates Riemannian analysis of large shape populations accessible through longitudinal and multi-site imaging studies providing increased statistical power. Additionally, as planar configurations form a submanifold in shape space, our representation allows for effective estimation of quasi-isometric surfaces flattenings. We evaluate the performance of our model w.r.t. shape-based classification of hippocampus and femur malformations due to Alzheimer's disease and osteoarthritis, respectively. In particular, we achieve state-of-the-art accuracies outperforming the standard Euclidean as well as a recent nonlinear approach especially in presence of sparse training data. To provide insight into the model's ability of capturing biological shape variability, we carry out an analysis of specificity and generalization ability.

Description: Currently, new materials for knee implants need to be extensively and expensive tested in a knee wear simulator in a realized design. However, using a rolling-sliding test bench, these materials can be examined under the same test conditions but with simplified geometries. In the present study, the test bench was optimized, and forces were adapted to the physiological contact pressure in the knee joint using the available geometric parameters. Various polymers made of polyethylene and polyurethane articulating against test wheels made of cobalt-chromium and aluminum titanate were tested in the test bench using adapted forces based on ISO 14243-1. Polyurethane materials showed distinctly higher wear rates than polyethylene materials and showed inadequate wear resistance for use as knee implant material. Thus, the rolling-sliding test bench is an adaptable test setup for evaluating newly developed bearing materials for knee implants. It combines the advantages of screening and simulator tests and allows testing of various bearing materials under physiological load and tribological conditions of the human knee joint. The wear behavior of different material compositions and the influence of surface geometry and quality can be initially investigated without the need to produce complex implant prototypes of total knee endoprosthesis or interpositional spacers.

Description: Long-lived flow patterns in the atmosphere such as weather fronts, mid-latitude blockings or tropical cyclones often induce extreme weather conditions. As a consequence, their description, detection, and tracking has received increasing attention in recent years. Similar objectives also arise in diverse fields such as turbulence and combustion research, image analysis, and medical diagnostics under the headlines of "feature tracking", "coherent structure detection" or "image registration" - to name just a few. A host of different approaches to addressing the underlying, often very similar, tasks have been developed and successfully used. Here, several typical examples of such approaches are summarized, further developed and applied to meteorological data sets. Common abstract operational steps form the basis for a unifying framework for the specification of "persistent structures" involving the definition of the physical state of a system, the features of interest, and means of measuring their persistence.

Description: Convolutional neural networks (CNNs) are the state-of-the-art for automated assessment of knee osteoarthritis (KOA) from medical image data. However, these methods lack interpretability, mainly focus on image texture, and cannot completely grasp the analyzed anatomies’ shapes. In this study we assess the informative value of quantitative features derived from segmentations in order to assess their potential as an alternative or extension to CNN-based approaches regarding multiple aspects of KOA. Six anatomical structures around the knee (femoral and tibial bones, femoral and tibial cartilages, and both menisci) are segmented in 46,996 MRI scans. Based on these segmentations, quantitative features are computed, i.e., measurements such as cartilage volume, meniscal extrusion and tibial coverage, as well as geometric features based on a statistical shape encoding of the anatomies. The feature quality is assessed by investigating their association to the Kellgren-Lawrence grade (KLG), joint space narrowing (JSN), incident KOA, and total knee replacement (TKR). Using gold standard labels from the Osteoarthritis Initiative database the balanced accuracy (BA), the area under the Receiver Operating Characteristic curve (AUC), and weighted kappa statistics are evaluated. Features based on shape encodings of femur, tibia, and menisci plus the performed measurements showed most potential as KOA biomarkers. Differentiation between non-arthritic and severely arthritic knees yielded BAs of up to 99%, 84% were achieved for diagnosis of early KOA. Weighted kappa values of 0.73, 0.72, and 0.78 were achieved for classification of the grade of medial JSN, lateral JSN, and KLG, respectively. The AUC was 0.61 and 0.76 for prediction of incident KOA and TKR within one year, respectively. Quantitative features from automated segmentations provide novel biomarkers for KLG and JSN classification and show potential for incident KOA and TKR prediction. The validity of these features should be further evaluated, especially as extensions of CNN- based approaches. To foster such developments we make all segmentations publicly available together with this publication.

Description: Morphomatics is an open-source Python library for (statistical) shape analysis developed within the geometric data analysis and processing research group at Zuse Institute Berlin. It contains prototype implementations of intrinsic manifold-based methods that are highly consistent and avoid the influence of unwanted effects such as bias due to arbitrary choices of coordinates.

Description: Purpose Segmentation of surgical instruments in endoscopic video streams is essential for automated surgical scene understanding and process modeling. However, relying on fully supervised deep learning for this task is challenging because manual annotation occupies valuable time of the clinical experts. Methods We introduce a teacher–student learning approach that learns jointly from annotated simulation data and unlabeled real data to tackle the challenges in simulation-to-real unsupervised domain adaptation for endoscopic image segmentation. Results Empirical results on three datasets highlight the effectiveness of the proposed framework over current approaches for the endoscopic instrument segmentation task. Additionally, we provide analysis of major factors affecting the performance on all datasets to highlight the strengths and failure modes of our approach. Conclusions We show that our proposed approach can successfully exploit the unlabeled real endoscopic video frames and improve generalization performance over pure simulation-based training and the previous state-of-the-art. This takes us one step closer to effective segmentation of surgical instrument in the annotation scarce setting.

Description: This article revisits a complexly folded silver scroll excavated in Jerash, Jordan in 2014 that was digitally examined in 2015. In this article we apply, examine and discuss a new virtual unfolding technique that results in a clearer image of the scroll’s 17 lines of writing. We also compare it to the earlier unfolding and discuss progress in general analytical tools. We publish the original and the new images as well as the unfolded volume data open access in order to make these available to researchers interested in optimising unfolding processes of various complexly folded materials.

Description: Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.

Description: Agent based models (ABMs) are a useful tool for modeling spatio-temporal population dynamics, where many details can be included in the model description. Their computational cost though is very high and for stochastic ABMs a lot of individual simulations are required to sample quantities of interest. Especially, large numbers of agents render the sampling infeasible. Model reduction to a metapopulation model leads to a significant gain in computational efficiency, while preserving important dynamical properties. Based on a precise mathematical description of spatio-temporal ABMs, we present two different metapopulation approaches (stochastic and piecewise deterministic) and discuss the approximation steps between the different models within this framework. Especially, we show how the stochastic metapopulation model results from a Galerkin projection of the underlying ABM onto a finite-dimensional ansatz space. Finally, we utilize our modeling framework to provide a conceptual model for the spreading of COVID-19 that can be scaled to real-world scenarios.

Description: Convolutional neural networks (CNNs) are the state-of-the-art for automated assessment of knee osteoarthritis (KOA) from medical image data. However, these methods lack interpretability, mainly focus on image texture, and cannot completely grasp the analyzed anatomies’ shapes. In this study we assess the informative value of quantitative features derived from segmentations in order to assess their potential as an alternative or extension to CNN-based approaches regarding multiple aspects of KOA A fully automated method is employed to segment six anatomical structures around the knee (femoral and tibial bones, femoral and tibial cartilages, and both menisci) in 46,996 MRI scans. Based on these segmentations, quantitative features are computed, i.e., measurements such as cartilage volume, meniscal extrusion and tibial coverage, as well as geometric features based on a statistical shape encoding of the anatomies. The feature quality is assessed by investigating their association to the Kellgren-Lawrence grade (KLG), joint space narrowing (JSN), incident KOA, and total knee replacement (TKR). Using gold standard labels from the Osteoarthritis Initiative database the balanced accuracy (BA), the area under the Receiver Operating Characteristic curve (AUC), and weighted kappa statistics are evaluated. Features based on shape encodings of femur, tibia, and menisci plus the performed measurements showed most potential as KOA biomarkers. Differentiation between healthy and severely arthritic knees yielded BAs of up to 99%, 84% were achieved for diagnosis of early KOA. Substantial agreement with weighted kappa values of 0.73, 0.73, and 0.79 were achieved for classification of the grade of medial JSN, lateral JSN, and KLG, respectively. The AUC was 0.60 and 0.75 for prediction of incident KOA and TKR within 5 years, respectively. Quantitative features from automated segmentations yield excellent results for KLG and JSN classification and show potential for incident KOA and TKR prediction. The validity of these features as KOA biomarkers should be further evaluated, especially as extensions of CNN-based approaches. To foster such developments we make all segmentations publicly available together with this publication.

Description: The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib.

Description: About 23% of the German energy demand is supplied by natural gas. Additionally, for about the same amount Germany serves as a transit country. Thereby, the German network represents a central hub in the European natural gas transport network. The transport infrastructure is operated by transmissions system operators (TSOs). The number one priority of the TSOs is to ensure the security of supply. However, the TSOs have only very limited knowledge about the intentions and planned actions of the shippers (traders). Open Grid Europe (OGE), one of Germany’s largest TSO, operates a high-pressure transport network of about 12,000 km length. With the introduction of peak-load gas power stations, it is of great importance to predict in- and out-flow of the network to ensure the necessary flexibility and security of supply for the German Energy Transition (“Energiewende”). In this paper, we introduce a novel hybrid forecast method applied to gas flows at the boundary nodes of a transport network. This method employs an optimized feature selection and minimization. We use a combination of a FAR, LSTM and mathematical programming to achieve robust high-quality forecasts on real-world data for different types of network nodes.

Description: We evaluated how plasma proteomic signatures in patients with suspected COVID-19 can unravel the pathophysiology, and determine kinetics and clinical outcome of the infection. We identified distinct plasma proteins linked to the presence and course of COVID-19. These plasma proteomic findings may translate to a protein fingerprint, helping to assist clinical management decisions.

Description: Solving PDEs on unstructured grids is a cornerstone of engineering and scientific computing. Heterogeneous parallel platforms, including CPUs, GPUs, and FPGAs, enable energy-efficient and computationally demanding simulations. In this article, we introduce the HPM C++-embedded DSL that bridges the abstraction gap between the mathematical formulation of mesh-based algorithms for PDE problems on the one hand and an increasing number of heterogeneous platforms with their different programming models on the other hand. Thus, the HPM DSL aims at higher productivity in the code development process for multiple target platforms. We introduce the concepts as well as the basic structure of the HPM DSL, and demonstrate its usage with three examples. The mapping of the abstract algorithmic description onto parallel hardware, including distributed memory compute clusters, is presented. A code generator and a matching back end allow the acceleration of HPM code with GPUs. Finally, the achievable performance and scalability are demonstrated for different example problems.

Description: Solving partial differential equations on unstructured grids is a cornerstone of engineering and scientific computing. Nowadays, heterogeneous parallel platforms with CPUs, GPUs, and FPGAs enable energy-efficient and computationally demanding simulations. We developed the HighPerMeshes C++-embedded Domain-Specific Language (DSL) for bridging the abstraction gap between the mathematical and algorithmic formulation of mesh-based algorithms for PDE problems on the one hand and an increasing number of heterogeneous platforms with their different parallel programming and runtime models on the other hand. Thus, the HighPerMeshes DSL aims at higher productivity in the code development process for multiple target platforms. We introduce the concepts as well as the basic structure of the HighPer-Meshes DSL, and demonstrate its usage with three examples, a Poisson and monodomain problem, respectively, solved by the continuous finite element method, and the discontinuous Galerkin method for Maxwell’s equation. The mapping of the abstract algorithmic description onto parallel hardware, including distributed memory compute clusters is presented. Finally, the achievable performance and scalability are demonstrated for a typical example problem on a multi-core CPU cluster.

Description: Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.

Description: Parallel in time methods for solving initial value problems are a means to increase the parallelism of numerical simulations. Hybrid parareal schemes interleaving the parallel in time iteration with an iterative solution of the individual time steps are among the most efficient methods for general nonlinear problems. Despite the hiding of communication time behind computation, communication has in certain situations a significant impact on the total runtime. Here we present strict, yet no sharp, error bounds for hybrid parareal methods with inexact communication due to lossy data compression, and derive theoretical estimates of the impact of compression on parallel efficiency of the algorithms. These and some computational experiments suggest that compression is a viable method to make hybrid parareal schemes robust with respect to low bandwidth setups.

Description: We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound.

Description: Computers, servers and supercomputers with more than one GPU become more and more common. To fully utilize such systems the application needs to be aware of the additional GPUs. E.g., computational workload needs to be distributed across the GPUs. Along with that goes data movement as well as communication. Recently, NVIDIA introduced new features, Unified Memory and Cooperative Groups, that enable programmers to extend their applications with multi-GPU capabilities. In this thesis the aforementioned features are presented in detail and evaluated in the context of the GPU molecular dynamics simulation HAL's MD package on the latest NVIDIA GPU architecture Pascal. A hotspot analysis with the NVIDIA Visual Profiler identified the radix sort as a major hotspot within HAL's MD package. This thesis presents an approach towards a multi-GPU implementation of radix sort. The individual kernels are analysed and an implementation is discussed. Then, the radix sort is transformed into a multi-GPU implementation kernel per kernel. For each step the individual runtime measurements and bottlenecks are presented to analyse the approach. A general sequence diagram of the implementation shows how the individual parts interact with each other. The outlook discusses the further development of HAL's MD package, especially the force computation for multi-GPU which has not been covered in this thesis.

Description: Computer, Server und Supercomputer mit mehr als einer GPU sind immer häufiger zu finden. Um solche Systeme komplett ausnutzen zu können, müssen Anwendung für die Verwendung mehrerer GPUs angepasst werden. Z.B. müssen die Berechnungen zwischen den GPUs verteilt werden. Damit einher gehen die Kommunikation zwischen den GPUs sowie der Austausch der Daten. Mit Unified Memory und Cooperative Groups hat NVIDIA zwei neue Funktionen vorgestellt, damit Programmierer ihre Anwendungen einfach an Multi-GPU Systeme anpassen können. Im Rahmen dieser Arbeit werden die oben genannten Funktionen im Detail vorgestellt und anhand der Molekulardynamiksimulation HAL's MD package auf der neuesten NVIDIA GPU Architektur Pascal evaluiert. Eine Hotspot Analyse von HAL's MD package mit dem NVIDIA Visual Profiler hat den Radix Sort als einen großen Hotspot identifiziert. Daher stellt diese Arbeit eine Multi-GPU Implementierung für Radix Sort vor. Dabei werden die einzelnen Kernel Schritt für Schritt vorgestellt und ihre Implementierung, insbesondere Laufzeiten und Probleme bei der Umsetzung, im Detail diskutiert. Ein Sequenzdiagramm der einzelnen Teile von Radix Sort zeigt dabei, wie die einzelnen Teile in der Multi-GPU Implementierung zusammenarbeiten. Abschließend wird, ausgehend von den Ergebnissen, die zukünftige Entwicklung von HAL's MD package unter besonderen Berücksichtigung einer vollständigen Multi-GPU Molekulardynamiksimulation betrachtet.

Description: Small-molecule oxoanions are often imprinted noncovalently as carboxylates into molecularly imprinted polymers (MIPs), requiring the use of an organic counterion. Popular species are either pentamethylpiperidine (PMP) as a protonatable cation or tetraalkylammonium (TXA) ions as permanent cations. The present work explores the influence of the TXA as a function of their alkyl chain length, from methyl to octyl, using UV/vis absorption, fluorescence titrations, and HPLC as well as MD simulations. Protected phenylalanines (Z-L/D-Phe) served as templates/analytes. While the influence of the counterion on the complex stability constants and anion-induced spectral changes shows a monotonous trend with increasing alkyl chain length at the prepolymerization stage, the cross-imprinting/rebinding studies showed a unique pattern that suggested the presence of adaptive cavities in the MIP matrix, related to the concept of induced fit of enzyme–substrate interaction. Larger cavities formed in the presence of larger counterions can take up pairs of Z-x-Phe and smaller TXA, eventually escaping spectroscopic detection. Correlation of the experimental data with the MD simulations revealed that counterion mobility, the relative distances between the three partners, and the hydrogen bond lifetimes are more decisive for the response features observed than actual distances between interacting atoms in a complex or the orientation of binding moieties. TBA has been found to yield the highest imprinting factor, also showing a unique dual behavior regarding the interaction with template and fluorescent monomer. Finally, interesting differences between both enantiomers have been observed in both theory and experiment, suggesting true control of enantioselectivity. The contribution concludes with suggestions for translating the findings into actual MIP development.

Description: Computing the Hierarchical Equations of Motion (HEOM) is by itself a challenging problem, and so is writing portable production code that runs efficiently on a variety of architectures while scaling from PCs to supercomputers. We combined both challenges to push the boundaries of simulating quantum systems, and to evaluate and improve methodologies for scientific software engineering. Our contributions are threefold: We present the first distributed memory implementation of the HEOM method (DM-HEOM), we describe an interdisciplinary development workflow, and we provide guidelines and experiences for designing distributed, performance-portable HPC applications with MPI-3, OpenCL and other state-of-the-art programming models. We evaluated the resulting code on multi- and many-core CPUs as well as GPUs, and demonstrate scalability on a Cray XC40 supercomputer for the PS I molecular light harvesting complex.

Description: We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.

Description: The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations.

Description: We consider the Cumulative Scheduling Problem (CuSP) in which a set of $n$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k 〈= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades.

Description: Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung.

Description: We investigate the relation between Hall’s theorem and Kőnig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all Kőnig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs.

Description: Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zunächst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs.

Description: Gene Regulatory Networks are powerful models for describing the mechanisms and dynamics inside a cell. These networks are generally large in dimension and seldom yield analytical formulations. It was shown that studying the conditional expectations between dimensions (vertices or species) of a network could lead to drastic dimension reduction. These conditional expectations were classically given by solving equations of motions derived from the Chemical Master Equation. In this paper we deviate from this convention and take an Algebraic approach instead. That is, we explore the consequences of conditional expectations being described by a polynomial function. There are two main results in this work. Firstly: if the conditional expectation can be described by a polynomial function, then coefficients of this polynomial function can be reconstructed using the classical moments. And secondly: there are dimensions in Gene Regulatory Networks which inherently have conditional expectations with algebraic forms. We demonstrate through examples, that the theory derived in this work can be used to develop new and effective numerical schemes for forward simulation and parameter inference. The algebraic line of investigation of conditional expectations has considerable scope to be applied to many different aspects of Gene Regulatory Networks; this paper serves as a preliminary commentary in this direction.

Description: The paper investigates the efficient use of a linearly implicit stiff integrator for the numerical solution of density driven flow problems. Upon choosing a one-step method of extrapolation type (code LIMEX), the use of full Jacobians and reduced approximations are discussed. Numerical experiments include nonlinear density flow problems such as diffusion from a salt dome (2D), a (modified) Elder problem (3D), the saltpool benchmark (3D) and a real life salt dome problem (2D). The arising linear equations are solved using either a multigrid preconditioner from the software package UG4 or the sparse matrix solver SuperLU.

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

Description: In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping"). The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally. On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models. Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times.

Description: The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel.

Description: Mathematical models for bioregulatory networks can be based on different formalisms, depending on the quality of available data and the research question to be answered. Discrete boolean models can be constructed based on qualitative data, which are frequently available. On the other hand, continuous models in terms of ordinary differential equations (ODEs) can incorporate time-series data and give more detailed insight into the dynamics of the underlying system. A few years ago, a method based on multivariate polynomial interpolation and Hill functions has been developed for an automatic conversion of boolean models to systems of ordinary differential equations. This method is frequently used by modellers in systems biology today, but there are only a few results available about the conservation of mathematical structures and properties across the formalisms. Here, we consider subsets of the phase space where some components stay fixed, called trap spaces, and demonstrate how boolean trap spaces can be linked to invariant sets in the continuous state space. This knowledge is of practical relevance since finding trap spaces in the boolean setting, which is relatively easy, allows for the construction of reduced ODE models.

Description: Let $G$ be a directed acyclic graph with $n$ arcs, a source $s$ and a sink $t$. We introduce the cone $K$ of flow matrices, which is a polyhedral cone generated by the matrices $1_P 1_P^T \in R^{n\times n}$, where $1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$. Several combinatorial problems reduce to a linear optimization problem over $K$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of $K$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.

Description: Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library.

Description: Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.

Description: Estimation of time of death based on a single measurement of body core temperature is a standard procedure in forensic medicine. Mechanistic models using simulation of heat transport promise higher accuracy than established phenomenological models in particular in nonstandard situations, but involve many not exactly known physical parameters. Identifying both time of death and physical parameters from multiple temperature measurements is one possibility to reduce the uncertainty significantly. In this paper, we consider the inverse problem in a Bayesian setting and perform both local and sampling-based uncertainty quantification, where proper orthogonal decomposition is used as model reduction for fast solution of the forward model. Based on the local uncertainty quantification, optimal design of experiments is performed in order to minimize the uncertainty in the time of death estimate for a given number of measurements. For reasons of practicability, temperature acquisition points are selected from a set of candidates in different spatial and temporal locations. Applied to a real corpse model, a significant accuracy improvement is obtained already with a small number of measurements.

Description: Time- and frequency resolved optical signals provide insights into the properties of light harvesting molecular complexes, including excitation energies, dipole strengths and orientations, as well as in the exciton energy flow through the complex. The hierarchical equations of motion (HEOM) provide a unifying theory, which allows one to study the combined effects of system-environment dissipation and non-Markovian memory without making restrictive assumptions about weak or strong couplings or separability of vibrational and electronic degrees of freedom. With increasing system size the exact solution of the open quantum system dynamics requires memory and compute resources beyond a single compute node. To overcome this barrier, we developed a scalable variant of HEOM. Our distributed memory HEOM, DM-HEOM, is a universal tool for open quantum system dynamics. It is used to accurately compute all experimentally accessible time- and frequency resolved processes in light harvesting molecular complexes with arbitrary system-environment couplings for a wide range of temperatures and complex sizes.

Description: Human mobility always had a great influence on the spreading of cultural, social and technological ideas. Developing realistic models that allow for a better understanding, prediction and control of such coupled processes has gained a lot of attention in recent years. However, the modeling of spreading processes that happened in ancient times faces the additional challenge that available knowledge and data is often limited and sparse. In this paper, we present a new agent-based model for the spreading of innovations in the ancient world that is governed by human movements. Our model considers the diffusion of innovations on a spatial network that is changing in time, as the agents are changing their positions. Additionally, we propose a novel stochastic simulation approach to produce spatio-temporal realizations of the spreading process that are instructive for studying its dynamical properties and exploring how different influences affect its speed and spatial evolution.

Description: The reproductive cycle of mono-ovulatory species such as cows or humans is known to show two or more waves of follicular growth and decline between two successive ovulations. Within each wave, there is one dominant follicle escorted by subordinate follicles of varying number. Under the surge of the luteinizing hormone a growing dominant follicle ovulates. Rarely the number of ovulating follicles exceeds one. In the biological literature, the change of hormonal concentrations and individually varying numbers of follicular receptors are made responsible for the selection of exactly one dominant follicle, yet a clear cause has not been identified. In this paper, we suggest a synergistic explanation based on competition, formulated by a parsimoniously defined system of ordinary differential equations (ODEs) that quantifies the time evolution of multiple follicles and their competitive interaction during one wave. Not discriminating between follicles, growth and decline are given by fixed rates. Competition is introduced via a growth-suppressing term, equally supported by all follicles. We prove that the number of dominant follicles is determined exclusively by the ratio of follicular growth and competition. This number turns out to be independent of the number of subordinate follicles. The asymptotic behavior of the corresponding dynamical system is investigated rigorously, where we demonstrate that the ω-limit set only contains fixed points. When also including follicular decline, our ODEs perfectly resemble ultrasound data of bovine follicles. Implications for the involved but not explicitly modeled hormones are discussed.

Description: “Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex” This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.

Description: This book promotes the use of mathematical optimization and operations research methods in rail transportation. The editors assembled thirteen contributions from leading scholars to present a unified voice, standardize terminology, and assess the state-of-the-art. There are three main clusters of articles, corresponding to the classical stages of the planning process: strategic, tactical, and operational. These three clusters are further subdivided into five parts which correspond to the main phases of the railway network planning process: network assessment, capacity planning, timetabling, resource planning, and operational planning. Individual chapters cover: Simulation Capacity Assessment Network Design Train Routing Robust Timetabling Event Scheduling Track Allocation Blocking Shunting Rolling Stock Crew Scheduling Dispatching Delay Propagation

Description: Inspired by the problem of best managing the invasive mosquito Aedes albopictus across the 17 Torres Straits islands of Australia, we aim at solving a Markov decision process on large Susceptible-Infected-Susceptible (SIS) networks that are highly connected. While dynamic programming approaches can solve sequential decision-making problems on sparsely connected networks, these approaches are intractable for highly connected networks. Inspired by our case study, we focus on problems where the probability of nodes changing state is low and propose two approximate dynamic programming approaches. The first approach is a modified version of value iteration where only those future states that are similar to the current state are accounted for. The second approach models the state space as continuous instead of binary, with an on-line algorithm that takes advantage of Bellman's adapted equation. We evaluate the resulting policies through simulations and provide a priority order to manage the 17 infested Torres Strait islands. Both algorithms show promise, with the continuous state approach being able to scale up to high dimensionality (50 nodes). This work provides a successful example of how AI algorithms can be designed to tackle challenging computational sustainability problems.

Description: Das Wind-Interpolation-Problem (WIP) ist ein bisher selten diskutiertes Problem der Flugplanungsoptimierung, bei dem es darum geht, Wind-Komponenten auf einer Luftstraße zu approximieren. Anhand von Winddaten, die vektoriell an den Gitterpunkten eines den Globus umspannenden Gitters vorliegen, soll bestimmt werden, wie viel Wind entlang der Luftstraße und quer zu ihr weht. Thema dieser Arbeit ist ein Spezialfall des WIP, nämlich das statische WIP auf einer Planfläche (SWIPP). Dazu wird zuerst ein Algorithmus besprochen, der das SWIPP zwar löst, aber einem Ansatz zugrunde liegt, der bei genauerem Hinsehen nicht sinnvoll erscheint: hier wird Wind zwischen vier Punkten interpoliert, wozu es keine triviale Methode gibt. Ähnlich zu diesem Algorithmus, der heute als State-of-the-Art gilt, wird als Ergebnis dieser Arbeit ein neuer Algorithmus vorgestellt, der das SWIPP akkurater und schneller löst. Hier wird deutlich seltener auf die Interpolation zwischen vier Punkten zurückgegriffen - stattdessen wird fast immer linear zwischen zwei Punkten interpoliert. Die Algorithmen zum Lösen des SWIPP werden auf ihre Genauigkeit, asymptotische Laufzeit und Geschwindigkeit untersucht und verglichen. Als Testareal dienen zum einen echte Wetterdaten sowie das Luftstraßennetz, das die Erde umspannt, und zum anderen ein eigens generiertes Windfeld und fiktive Luftstraßen. Es wird gezeigt, dass der hier vorgestellte Algorithmus die State-of-the-Art-Variante in allen genannten Aspekten übertrifft.

Description: In several inital value problems with particularly expensive right hand side evaluation or implicit step computation, there is a trade-off between accuracy and computational effort. We consider inexact spectral deferred correction (SDC) methods for solving such initial value problems. SDC methods are interpreted as fixed point iterations and, due to their corrective iterative nature, allow to exploit the accuracy-work-tradeoff for a reduction of the total computational effort. On one hand we derive error models bounding the total error in terms of the evaluation errors. On the other hand, we define work models describing the computational effort in terms of the evaluation accuracy. Combining both, a theoretically optimal local tolerance selection is worked out by minimizing the total work subject to achieving the requested tolerance. The properties of optimal local tolerances and the predicted efficiency gain compared to simpler heuristics, and a reasonable practical performance, are illustrated on simple numerical examples.

Description: Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.

Description: Most distributed file systems assign new files to storage servers randomly. While working well in some situations, this does not help to optimize the input performance for most MapReduce computations’ data access patterns. In this work, we consider an access pattern where input files are partitioned into groups of heterogeneous size. Each group is accessed by exactly one process. We design and implement a data placement strategy that places these file groups together on the same storage server. This colocation approach is combined with near-optimal storage load balancing. To do so, we use a classical scheduling approximation algorithm to solve the NP hard group assignment problem. We argue that local processing is not only beneficial because of reduced network traffic, but especially because it imposes an even resource schedule. Our experiments, based on the parallel processing of remote sensing images, reveal an enormous reduction of network traffic and up to 39 % faster input read times. Further, simulations show that our approximate assignments limit storage server imbalances to less than 5 % above the theoretical minimum, in contrast to more than 85 % with random assignment.

Description: We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.

Description: We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.

Description: Molecular dynamics (MD) simulations can model the interactions between macromolecules with high spatiotemporal resolution but at a high computational cost. By combining high-throughput MD with Markov state models (MSMs), it is now possible to obtain long-timescale behavior of small to intermediate biomolecules and complexes. To model the interactions of many molecules at large lengthscales, particle-based reaction-diffusion (RD) simulations are more suitable but lack molecular detail. Thus, coupling MSMs and RD simulations (MSM/RD) would be highly desirable, as they could efficiently produce simulations at large time- and lengthscales, while still conserving the characteristic features of the interactions observed at atomic detail. While such a coupling seems straightforward, fundamental questions are still open: Which definition of MSM states is suitable? Which protocol to merge and split RD particles in an association/dissociation reaction will conserve the correct bimolecular kinetics and thermodynamics? In this paper, we make the first step towards MSM/RD by laying out a general theory of coupling and proposing a first implementation for association/dissociation of a protein with a small ligand (A + B 〈--〉 C). Applications on a toy model and CO diffusion into the heme cavity of myoglobin are reported.

Description: OPUS wurde als Dokumentenserver konzipiert und ursprünglich nicht für den Nachweis von Forschungsdaten angelegt. Mit vergleichsweise geringem Aufwand können dennoch Forschungsdaten als Supplementary Material zu Zeitschriftenbeiträgen publiziert werden. Auch reine Forschungsdatenpublikationen können via OPUS veröffentlicht werden, selbst wenn die gegenwärtig auf Textpublikationen zugeschnittene Metadatenerfassung weniger gut für die Beschreibung reiner Forschungsdaten geeignet ist. Ein Unterschied zu anderen Systemen und Anwendungsszenarien besteht in der Beschränkung, großvolumige Daten nicht innerhalb von OPUS selbst vorzuhalten. Der für das institutionelle Repository des Zuse-Instituts Berlin konzipierte pragmatische Lösungsansatz ist in OPUS ohne zusätzliche Programmierung umsetzbar und skaliert für beliebig große Forschungsdatensätze.

Description: We reconstruct the temporal evolution of the source distribution for the four major gas species H2O, CO2, CO, and O2 on the surface of comet 67P/Churyumov-Gerasimenko during its 2015 apparition. The analysis applies an inverse coma model and fits to data between August 6th 2014 and September 5th 2016 measured with the Double Focusing Mass Spectrometer (DFMS) of the Rosetta Orbiter Spectrometer for Ion and Neutral Analysis (ROSINA) and the COmet Pressure Sensor (COPS). The spatial distribution of gas sources with their temporal variation allows one to construct surface maps for gas emissions and to evaluate integrated productions rates. For all species peak production rates and integrated productions rates per orbit are evaluated separately for the northern and the southern hemisphere. The nine most active emitting areas on the comet’s surface are defined and their correlation to emissions for each of the species is discussed.

Description: Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.

Description: The design of rolling stock rotations is an important task in large-scale railway planning. This so-called rolling stock rotation problem (RSRP) is usually tackled using an integer programming approach. Markus Reuther did so in his dissertation [15] for the ICE railway network of DB ("Deutsche Bahn"). Due to the size of the network and the complexity of further technical requirements, the resulting integer problems tend to become very large and computationally involved. In this thesis, we tackle the linear programming relaxation of the RSRP integer program. We will do so by applying a modified version of an algorithm recently proposed by Dan Bienstock and Mark Zuckerberg [2] for the precedence constrained production scheduling problem that arises in open pit mine scheduling. This problem contains a large number of "easy" constraints and a relatively small number of "hard" constraints. We will see that a similar problem structure can also be found in the RSRP. The Bienstock-Zuckerberg algorithm relies on applying Lagrangian relaxation to the hard constraints as well as on partitioning the variable set. We propose three different partition schemes which try to exploit the specific problem structure of the RSRP. Furthermore, we will discuss the influence of primal degeneracy on the algorithm's performance, as well as possible merits of perturbating the right-hand side of the constraint matrix. We provide computational results to assess the performance of those approaches.

Description: Viele Firmen nutzen für ihre eigenen Softwareentwicklungen verschiedene Server mit unterschiedlichen Konfigurationen. Manche Server werden dazu eingestzt das Verhalten einer Software in einer bestimmten Umgebung zu testen und andere dienen zur Bereitstellung der Software für den Endnutzer. Hierbei ist es wichtig, dass die Konfiguration der Server regelmäßig überprüft wird. Eine solche Sicherstellung der Deployment- und Umgebungs-Integrität wird meistens durch eine Mitarbeiter der Firma oder durch einen externen Dienstleister erbracht. D.h. die Firma muss sich auf die Zuverlässigkeit eines Mitarbeiters oder einer externen Dienstleistung verlassen, bie zunehmender Komplexität ist sie sogar abhängig. Das Ziel dieser Masterarbeit ist es, zu untersuchen, ob die Sicherstellung der Deployment- und Umgebungs-Integrität durch automatisierte kryptografische Beweise, anstelle externer Dienstleistungen oder anderer Mitarbeiter, gewährleistet werden kann. Als Anwendungsfall dient die Toll Collect GmbH. Im ersten Teil dieser Arbeit wird das Matheamtische Modell einer Blockchain erläutert. die Blockchain wurde erstmals in einem Dokument, welches unter dem Pseudonym Satoshi Nakamoto veröffentlicht wurde, beschrieben. Die erste große Anwendungen der Blockchain ist das dezentrale Zahlungssystem Bitcoin. Im zweiten Teil dieser Arbeit wird die Softwareimplementierung vorgestellt, welche im Rahmen dieser Arbeit entstanden ist. Mithilfe dieses Programms kann die Deployment- und Umgebungs-Integrität durch eine heirführ entwickelte Blockchainlösung dezentralisiert werden. Es wird außerdem der Übergang vom Mathematischen Modell zur Implementierung gezeigt.

Description: This thesis deals with a new algorithm for finding Shortest Paths on Airway Networks. It is about a Bidirectional A* Search, a Greedy algorithm exploring a network from two sides instead of one. We will use it to solve the so-called 'Horizontal Flight Trajectory Problem', where one searches for an aircraft trajectory between two airports of minimal costs on an Airway Network. The given network will be modeled as a directed graph and in order to reflect reality we concentrate on the dynamic version. Here a timedependent cost function for all arcs is integrated, that shall represent the winds blowing. This way we model the Horizontal Flight Trajectory Problem mathematically as a Time-Dependent Shortest Path Problem. The basic algorithm idea derives from the algorithm presented in 'Bidirectional A* Search on Time-Dependent Road Networks' [1], where a similar setting is elaborated for road networks. The algorithm procedure bears on a modified generalization of Dijkstra's algorithm, made bidirectional and improved in several aspects. As for the backwards search the arrival times are not known in advance, the reversed graph it occurs on has to be weighted by a lower bound. Contrary to the static case the forwards search still has to go on, when they 'meet' in one node. In the static case, the shortest path would have been found at this point. For road networks the TDSPP is well-studied, for airway networks cannot be found as much in literature. In order to test efficiency, we implement Dijkstra's algorithm, unidirectional A* Search and Bidirectional A* Search. We draw up how potential functions for the static case could look like and that with a suitable potential A* Search with works approx. 7 times faster than Dijkstra in the dynamic case. Our computations lead also to the result, that the unidirectional A* Search works even better on the network than our new bidirectional approach does. On average it labels fewer nodes and also yields 1,7 times faster to the solutions. For assessing the efficiency of the different algorithms we compare the running times and to exclude processor characteristics we consider also the set labels relative to the labels on the resulting optimal path. In addition, we present examples of routes visually and explain shortly why there appear local differences regarding performance of A* Search and Bidirectional A* Search.

Description: Let G be a directed acyclic graph with n arcs, a source s and a sink t. We introduce the cone K of flow matrices, which is a polyhedral cone generated by the matrices $\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}$, where $\vec{1}_P\in\RR^n$ is the incidence vector of the (s,t)-path P. We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over $\mathcal{K}$. This cone is intractable: we prove that the membership problem associated to $\mathcal{K}$ is NP-complete. However, the affine hull of this cone admits a nice description, and we give an algorithm which computes in polynomial-time the decomposition of a matrix $X\in \operatorname{span} \mathcal{K}$ as a linear combination of some $\vec{1}_P\vec{1}_P^T$'s. Then, we provide two convergent approximation hierarchies, one of them based on a completely positive representation of~K. We illustrate this approach by computing bounds for the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities.

Description: In Silico Clinical Trials (ISCT), i.e., clinical experimental campaigns carried out by means of computer simulations, hold the promise to decrease time and cost for the safety and efficacy assessment of pharmacological treatments, reduce the need for animal and human testing, and enable precision medicine. In this paper we present a case study aiming at quantifying, by means of a multi-arm ISCT supervised by intelligent search, the potential impact of precision medicine approaches on a real pharmacological treatment, namely the downregulation phase of a complex clinical protocol for assisted reproduction.

Description: We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.

Description: Upon ligand binding or during chemical reactions the state of a molecular system changes in time. Usually we consider a finite set of (macro-) states of the system (e.g., ’bound’ vs. ’unbound’), although the process itself takes place in a continuous space. In this context, the formula chi=XA connects the micro-dynamics of the molecular system to its macro-dynamics. Chi can be understood as a clustering of micro-states of a molecular system into a few macro-states. X is a basis of an invariant subspace of a transfer operator describing the micro-dynamics of the system. The formula claims that there is an unknown linear relation A between these two objects. With the aid of this formula we can understand rebinding effects, the electron flux in pericyclic reactions, and systematic changes of binding rates in kinetic ITC experiments. We can also analyze sequential spectroscopy experiments and rare event systems more easily. This article provides an explanation of the formula and an overview of some of its consequences.

Description: Although intensively studied in recent years, the optimization of the transient (time-dependent) control of large real-world gas networks is still out of reach for current state-of-the-art approaches. For this reason, we present further simplifications of the commonly used model, which lead to a linear description of the gas flow on pipelines. In an empirical analysis of real-world data, we investigate the properties of the involved quantities and evaluate the errors made by our simplification.

Description: Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching.

Description: In this thesis we study order picking optimization problems for a two-blocks rectangle warehouse layout. We present combinatorial formulations and linear programming models based on the Steiner graph representation for order batching, picker routing, and joint order batching and picker routing problems. A special case of the latter is considered. This case assumes that each order contains exactly one item and each item can be picked from different possible locations in a warehouse. The underlying optimization problem is called joint multi-location order batching and picker routing problem (JMLOBPRP). Since having only one-item orders turns the JMLOBPRP into a special case of a capacitated vehicle routing problem, we suggest to implement algorithmic approaches for those to solve the JMLOBPRP. In particular, we define the JMLOBPRP as a generalization of the resource constrained assignment problem, for which a regional search method exists. The intention of the thesis is to investigate how a relaxation of the JMLOBPRP, a so-called group assignment problem (GrAP), can be solved following the ideas of regional search. We present a mathematical model of the GrAP and prove that it is NP-hard. Furthermore, we propose a novel heuristic algorithm for the GrAP. We call this method a network search algorithm, as it is based on a Lagrangian relaxation of the GrAP, which is solved by the network simplex method. On each its iteration network search examines a solution region suggested by the network simplex algorithm and improves the incumbent solution. Numerical experiments are conducted to assess a performance of the network search method. We create more realistic problem instances. The proposed algorithm is compared to the integer optimal solution of the GrAP and optimal fractional solution of its linear relaxation. Both computed using the commercial linear solver Gurobi. Our experiments show that the developed network search algorithm leads to the hight-quality solution within a short computing time. The results obtained testing large problem instances which cannot be solved by Gurobi within a reasonable computing time, show that the network search method provides a solution approach which can be used in practice.

Description: In dieser Arbeit wird die Platzierung von Ladestationen für Elektrobusse untersucht. Dabei soll für eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zunächst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden könnte. Dieses Problem stellt sich als NP-schwer heraus. Für einige einfachere Fällewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur Lösung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station würde ein individueller Wert geladen, so ist das Problem schon für nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazität hinzugefügt und die zuvor entwickelten Algorithmen werden entsprechend angepasst. Für die abschließende Problemdefinition werden verschiedene Batteriegrößen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich größeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt größerer und mehr Ladestationen genutzt werden.

Description: Running and optimizing transportation systems give rise to very complex and large-scale optimization problems requiring innovative solution techniques and ideas from mathematical optimization, theoretical computer science, and operations research. Since 2000, the series of Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) workshops brings together researchers and practitioners who are interested in all aspects of algorithmic methods and models for transportation optimization and provides a forum for the exchange and dissemination of new ideas and techniques. The scope of ATMOS comprises all modes of transportation. The 18th ATMOS workshop (ATMOS’18) was held in connection with ALGO’18 and hosted by Aalto University in Helsinki, Finland, on August 23–24, 2018. Topics of interest were all optimization problems for passenger and freight transport, including, but not limited to, demand forecasting, models for user behavior, design of pricing systems, infrastructure planning, multi-modal transport optimization, mobile applications for transport, congestion modelling and reduction, line planning, timetable generation, routing and platform assignment, vehicle scheduling, route planning, crew and duty scheduling, rostering, delay management, routing in road networks, traffic guidance, and electro mobility. Of particular interest were papers applying and advancing techniques like graph and network algorithms, combinatorial optimization, mathematical programming, approximation algorithms, methods for the integration of planning stages, stochastic and robust optimization, online and real-time algorithms, algorithmic game theory, heuristics for real-world instances, and simulation tools. There were twenty-nine submissions from eighteen countries. All of them were reviewed by at least three referees in ninety-one reviews, among them five external ones, and judged on their originality, technical quality, and relevance to the topics of the workshop. Based on the reviews, the program committee selected sixteen submissions to be presented at the workshop (acceptance rate: 55%), which are collected in this volume in the order in which they were presented. Together, they quite impressively demonstrate the range of applicability of algorithmic optimization to transportation problems in a wide sense. In addition, Dennis Huisman kindly agreed to complement the program with an invited talk on Railway Disruption Management: State-of-the-art in practice and new research directions. Based on the reviews, Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner won the Best Paper Award of ATMOS’18 with their paper A simple way to compute the number of vehicles that Are required to operate a periodic timetable. In addition, we awarded Tomas Lidén the Best VGI Paper Award of ATMOS’18 for his paper Reformulations for railway traffic and maintenance planning. We would like to thank the members of the Steering Committee of ATMOS for giving us the opportunity to serve as Program Chairs of ATMOS’18, all the authors who submitted papers, Dennis Huisman for accepting our invitation to present an invited talk, the members of the Program Committee and the additional reviewers for their valuable work in selecting the papers appearing in this volume, our sponsors MODAL, TomTom, and VGIscience for their support of the prizes, and the local organizers for hosting the workshop as part of ALGO’18. We acknowledge the use of the EasyChair system for the great help in managing the submission and review processes, and Schloss Dagstuhl for publishing the proceedings of ATMOS’18 in its OASIcs series.

Description: Lactating dairy cows require a particular composition of nutritional ingredients depending on their production status. The optimal supply of energy and minerals in diet, one of them potassium, is indispensable for the prevention of disbalances like hypokalemia or hypoglycaemia. Potassium balance in cows is the result of potassium intake, distribution in the organism, and excretion, and closely interacts with glucose and electrolyte metabolism, in which postpartum veterinary treatments frequently intervene. We present a mechanistic, dynamic model for potassium balance together with a glucose insulin model in non-lactating and lactating dairy cows based on ordinary differential equations. Parameter values were obtained from data of a clinical trial as well as from literature. To verify the mechanistic functioning of the model, we validate the model by comparing simulation outcomes with clinical study findings. Furthermore we perform numerical experiments and compare them with expected behaviour according to mechanistic knowledge. The results give insight into the dynamic behaviour of the network and open the way for further open questions and hypothesis to be tested.