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: Im Mai 2009 wurde Wolfram|Alpha gestartet, ein Service, der seinen Namen von seinem Entwickler, dem britischen Mathematiker Stephen Wolfram, ableitet. Dem Benutzer soll nicht nur eine Liste von Webseiten als Ergebnis auf Anfragen geliefert werden, sondern Antworten auf konkrete Fragen geben. In diesem Report soll gezeigt werden, warum sichWolframjAlpha von Suchmaschinen abgrenzt und was die Berechnung von Antworten auf natürlichsprachliche Fragen möglich machen kann.

Description: Wolfram|Alpha was started in May 2009 and it's a service whose name derives from the british mathematician Stephen wolfram. As a result for a request the user is not just supported with a list of websites but with answers for concrete questions. In this report it will be shown why Wolfram|Alpha seperates from search engines and moreover what makes the computation of answers for natural language queries possible.

Description: We consider an optimal control problem from hyperthermia treatment planning and its barrier regularization. We derive basic results, which lay the groundwork for the computation of optimal solutions via an interior point path-following method. Further, we report on a numerical implementation of such a method and its performance at an example problem.

Description: Optical technologies are ubiquitously used in hi-tech devices. As a common feature of such devices one finds structures with dimensions in the order of the wavelength of the used light. To design and produce such devices, the wave nature of light must be taken into account. Accordingly, robust simulation tools are required which are based on rigorously solving Maxwell's equations, the governing equations of light propagation within macroscopic media. This thesis contributes to the modeling and the numerical computation of light scattering problems: Light scattering problems are typically posed on the entire space. The Perfectly-Matched -Layer method (PML) is widely used to restrict the simulation problem onto a bounded computational domain. We propose an adaptive PML method which exhibits a good convergence even for critical problems where standard PML implementations fail. Besides the computation of the near field, that is the electromagnetic field within the computational domain, it is of major interest to evaluate the electromagnetic field in the exterior domain and to compute the far field. So far, this was numerically only possible for simple geometries such as homogeneous exterior domains or layered media. To deal with more complicated devices, for example with waveguide inhomogeneities, we develop an evaluation formula based on the PML solution which allows for an exterior domain field evaluation in a half space above the device. Finally, we generalize the PML method to problems with multiply structured exterior domains. The term “multiply structured exterior domain” is defined in this thesis and means that the exterior domain exhibits several half-infinite structures. Mathematically, this gives rise to various complications. For example, no analytical solutions to Maxwell's equations for standard light sources are available in the exterior domain, which are needed to describe the incoming field in a light scattering problem. To tackle this we propose a new light scattering problem formulation which fits well into the PML method framework and which may be regarded as an extension of classical contributions by Sommerfeld, Wiener and Hopf. An exterior domain evaluation formula for multiply structured exterior domains with an extended illumination is derived as well.

Description: We introduce the coolest path problem, which is a mixture of two well-known problems from distinct mathematical fields. One of them is the shortest path problem from combinatorial optimization. The other is the heat conduction problem from the field of partial differential equations. Together, they make up a control problem, where some geometrical object traverses a digraph in an optimal way, with constraints on intermediate or the final state. We discuss some properties of the problem and present numerical solution techniques. We demonstrate that the problem can be formulated as a linear mixed-integer program. Numerical solutions can thus be achieved within one hour for instances with up to 70 nodes in the graph.

Description: Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.

Description: Executing applications in the Grid often requires access to multiple geographically distributed resources. In a Grid environment, these resources belong to different administrative domains, each employing its own scheduling policy. That is, at which time an activity (e.g., compute job, data transfer) is started, is decided by the resource's local management system. In such an environment, the coordinated execution of distributed applications requires guarantees on the quality of service (QoS) of the needed resources. Reserving resources in advance is an accepted means to obtain QoS guarantees from a single provider. The challenge, however, is to coordinate advance reservations of multiple resources. This work presents a system architecture and mechanisms to coordinate multiple advance reservations -- called co-reservations -- for delivering QoS guarantees to complex applications. We formally define the co-reservation problem as an optimization problem. The presented model supports three dimensions of freedom: the start time, the duration and the service level of a reservation. Requests and resources are described in a simple language. After matching the static properties and requirements of either side in a mapping, the reservation mechanism probes information about the future status of the resources. The versatile design of the probing step allows the efficient processing of requests, but also lets the resources express their preferences among the myriads of reservation candidates. Next, the best mapping is found through an implementation of the formal co-reservation model. Then, the mapping has to be secured, i.e., resources need to be allocated to a co-reservation candidate with all-or-nothing semantics. We study several goal-driven sequential and concurrent allocation mechanisms and define schemes for handling allocation failures. Finally, we introduce the concept of virtual resources for seamlessly embedding co-reservations into Grid resource management.

Description: Die Ausführung von Anwendungen erfordert oft mehrere, geographisch verteilte Ressourcen. In Grid-Umgebungen gehören diese Ressourcen zu verschiedenen administrativen Organisationen, wobei jede ihre eigene Schedulingregeln verwendet. Das bedeutet, zu welcher Zeit eine Aktivität gestartet wird (z.B. ein Rechenjob), wird vom lokalen Ressourcenmanagementsystem entschieden. Die koordinierte Ausführung von verteilten Anwendungen erfordert Dienstgütegarantien für die benötigten Ressourcen. Das Reservieren von Ressourcen im Voraus ist ein Mittel, um Dienstgütegarantien von einem einzelnen Ressourcenanbieter zu erhalten. Die Herausforderung in dieser Arbeit ist, Vorausreservierungen von mehreren Ressourcen zu koordinieren. Es wird ein System für die Koordinierung mehrerer Vorausreservierungen -- Co-Reservierungen genannt -- für die Bereitstellung von Dienstgütegarantien vorgestellt. Wir definieren das Co-Reservierungsproblem als Optimierungsproblem. Das vorgestellte Modell unterstützt drei Freiheitsgrade: die Startzeit, die Dauer und die Dienstgüte einer Reservierung. Anfragen und Ressourcen werden in einer einfachen Sprache beschrieben. Nachdem statische Eigenschaften und Anforderungen beider Seiten überprüft wurden, ermittelt der Reservierungsmechanismus Informationen über den zukünftigen Zustand der Ressourcen. Dieser Schritt ist so allgemein gehalten, daß er sowohl ein effizientes Bearbeiten der Anfragen erlaubt als auch den Ressourcen ermöglicht ihre Präferenzen auszudrücken. Im Anschluss wird die optimale Zuweisung von Anfragen zu Ressourcen ermittelt. Im letzten Schritt muss diese Zuweisung umgesetzt werden, d.h., entweder alle oder keine Ressource wird allokiert. Es werden mehrere sequentielle und parallele Allokationsverfahren vorgestellt sowie deren Auswirkung auf verschiedene Metriken untersucht. Die Einbettung von Co-Reservierungen in das Grid-Ressourcenmanagement wird anhand des Konzeptes der virtuellen Ressource dargestellt.

Description: Vorbemerkung Beim Schreiben dieses Artikels, der auf Veränderungen der Kommunikations- und Publikationstechniken und ihre Bedeutung hinweist, ist uns mehr als je zuvor bewusst geworden, wie beschränkt das Medium Papier ist. Es gibt z. B. keine Hyperlinks, durch die man unmittelbar das Erwähnte erleben oder überprüfen kann. Ein schneller Wechsel vom Wort zum Bild, zum Ton oder Video ist nicht möglich. Wer will schon lange URLs abtippen und Medienbrüche erleiden? Wir haben uns daher entschlossen, eine textidentische Version dieses Artikels mit allen URLs – sie liegt Ihnen hier vor – elektronisch anzubieten und in der für die "Gegenworte" (BBAW) gekürzten Fassung nur durch [URL] anzudeuten, dass der Leser an dieser Stelle einfach in der elektronischen Version einen Klick ins Internet machen sollte. Und damit sind wir bereits mitten im Thema.

Description: In this paper we revisit the a priori turbulent flame speed tabulation (TFST) technique for a given parameter space within the region of flamelet combustion-regimes. It can be used as a subgrid-scale (SGS) model in Large Eddy Simulation (LES). In a first step, stationary laminar flamelets are computed and stored over the progress variable following the ideas of flamelet generated manifolds (FGM). In a second step, the incompressible one-dimensional Navier-Stokes equations supplemented by the equation for the progress variable are solved on a grid that resolves all turbulent scales. Additionally, turbulent transport is implemented via the linear eddy model (LEM). The turbulent flame structures are solved until a statistically stationary mean value of the turbulent flame speed has been reached. The results are stored in a table that could be used by large scale premixed combustion models, e.g. front tracking schemes. First results are compared quantitatively with direct numerical simulations (DNS) taken from literature. Then it is illustrated in one example how the new method could help to fix constants in algebraic models for turbulent flame speeds. Further it is shown how the technique can be extended to incorporate turbulent strain effects. Finally we investigate the effect of the use of detailed and tabulated chemistry under unsteady conditions.

Description: Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver.

Description: The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.

Description: Zwischen dem Bibliotheksverbund Bayern (BVB) und dem Kooperativen Bibliotheksverbund Berlin-Brandenburg (KOBV) besteht seit Ende 2007 eine Strategische Allianz, die auf zwei Säulen beruht: einer langfristigen Entwicklungspartnerschaft einerseits und der Kooperation im Dienstleistungsbereich mit der Integration der Verbundkataloge andererseits. Ende 2008 wurde das erste Entwicklungsprojekt "Literaturverwaltungsprogramme" abgeschlossen, dessen Ergebnisse in dieser Handreichung in Form von Handlungsempfehlungen für Bibliotheken vorgestellt werden. Ziel des Projekts war es, den Datenaustausch zwischen den Bibliotheks- und Verbundkatalogen des BVB und KOBV und gängigen Literaturverwaltungsprogrammen zu optimieren. Neben Handlungsempfehlungen für die Implementierung neuer Exportschnittstellen und die Verbesserung bestehender Exportmöglichkeiten werden Hinweise auf verbesserte Nutzerführung gegeben. Die Empfehlungen beziehen sich vorwiegend auf den Datenaustausch zwischen den Bibliothekssystemen Aleph 500, MetaLib und WebOPAC/InfoGuide und den Literaturverwaltungsprogrammen Citavi, EndNote, RefWorks und Zotero.

Description: Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and “scream” for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today’s challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).

Description: The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.

Description: Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6.

Description: The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view.

Description: The understanding of geometric structures and dynamical properties of molecular conformations gives insight into molecular long-term behavior. The identification of metastable conformations together with their life times and transition patterns is the intention of conformation dynamics. Conformation dynamics is a multi-scale approach that leads to a reduced description of the dynamical system in terms of a stochastic transition probability matrix. The present thesis deals with the error analysis of computed matrices and the resulting matrix functions. Since conformational membership vectors, as they are computed by the Robust Perron Cluster Analysis (PCCA+), form an invariant subspace of the transition matrix, subspace-based error estimators are of particular interest. The decomposition of the state space into basis functions and the approximation of integrals by Monte-Carlo quadrature give rise to row-wise correlated random matrices, for which stochastic norms are computed. Together with an appropriate statistical model for the distribution of matrix rows, this allows for the calculation of error bounds and error distributions of the invariant subspace and other variables of interest. Equilibration of errors among the basis functions can be achieved by enhanced sampling in regions where the trajectories are mixing slowly. Hierarchical refinement of such basis functions systematically improves the clustering into metastable conformations by reducing the error in the corresponding invariant subspace. These techniques allow for an evaluation of simulation results and pave the way for the analysis of larger molecules. Moreover, the extension of PCCA+ to non-reversible Markov chains, verified by the corresponding perturbation theory, and the modification of the objective function for the case of soft membership vectors represent a further generalization of the clustering method, thus continuing the development from PCCA over PCCA+ to PCCA++. The methods developed in this thesis are useful for but not limited to conformation dynamics. In fact, they are applicable to a broader class of problems which combine domain decomposition with Monte-Carlo quadrature. Possible application areas may include the chemical master equation or quantum dynamical systems.

Description: Das Verständnis von geometrischen Strukturen und dynamischen Eigenschaften molekularer Konformationen ist essentiell für die Vorhersage des Langzeitverhaltens von Molekülen. Die Identifikation metastabiler Konformationen sowie die Bestimmung von Übergangswahrscheinlichkeiten und Haltezeiten sind Bestandteil der Konformationdynamik. Dabei handelt es sich um eine Mehrskalenmethode, die auf eine reduzierte Beschreibung des Systems mittels einer stochastischen Übergangsmatrix führt. In der vorliegenden Dissertation wurde untersucht, wie man die Genauigkeit der Matrizen sowie der daraus berechneten Größen quantifizieren kann. Im Mittelpunkt stehen dabei Fehlerschätzer für den invarianten Unterraum, da die rechten Eigenvektoren als Grundlage der Robusten Perron Cluster Analyse (PCCA+) zur Identifizierung der metastabilen Konformationen dienen. Die Zerlegung des Zustandsraumes in Basisfunktionen sowie die Approximation der Matrixeinträge mittels Monte-Carlo-Quadratur führen zu zeilenweise korrelierten Zufallsmatrizen. Mit Hilfe einer stochastischen Norm sowie einem geeigneten statistischen Modell für die Verteilung der Matrixzeilen können u.a. Fehlerschranken und -verteilungen für den invarianten Unterraum brechnet werden. Eine Equilibrierung des Fehlers zwischen den Basisfunktionen kann durch erweitertes Sampling in solchen Regionen erreicht werden, in denen die Trajektorien nur langsam mischen.Eine hierarchische Zerlegung dieser Basisfunktionen verbessert systematisch die Zerlegung in metastabile Konformationen, indem sie den Fehler im invarianten Unterraum reduziert. Diese Techniken gestatten eine Evaluierung der Simulationsergebnisse und ebnen den Weg zur Behandlung komplexerer Moleküle. Desweiteren wurden Verallgemeinerungen der PCCA+ untersucht. Die Erweiterung der PCCA+ auf nicht-reversible Markov-Ketten sowie die Modifizierung der Zielfunktion für den Fall der weichen Clusterung setzen die Entwicklung von der PCCA über PCCA+ zu PCCA++ fort. Somit können neue Anwendungsfelder für dieses Cluster-Verfahren erschlossen werden. Die Methoden wurden zwar in Rahmen der Konformationsdynamik entwickelt, jedoch lassen sie sich auf eine weite Problemklasse anwenden, in der Gebietszerlegungsverfahren mit Monte-Carlo-Quadratur kombiniert werden. Mögliche Anwendungsgebiete umfassen die chemische Master-Gleichung oder quantenchemische Systeme.

Description: We give the basic definitions and some theoretical results about hyperdeterminants, introduced by A.~Cayley in 1845. We prove integrability (understood as $4d$-consistency) of a nonlinear difference equation defined by the $2 \times 2 \times 2$ - hyperdeterminant. This result gives rise to the following hypothesis: the difference equations defined by hyperdeterminants of any size are integrable. We show that this hypothesis already fails in the case of the $2\times 2\times 2\times 2$ - hyperdeterminant.

Description: A world-wide used program for the simulation of fire-induced flows is the Fire Dynamics Simulator (FDS) which originally was developed for a purely serial execution on single-processor computing systems. Due to steadily increasing problem sizes and accuracy requirements as well as restrictions in storage capacity and computing power on single-processor systems, the efficient simulation of the considered fire scenarios can only be achieved on modern high-performance systems based on multi-processor architectures. The transition to those systems requires the elaborate parallelization of the underlying numerical methods which must guarantee the same result for a given problem as the corresponding serial execution. Unfortunately, one fundamental serial serial solver of FDS, the pressure solver, only possesses a low degree of inherent parallelizm. Its current parallelization may cause additional numerical errors, casually leading to significant losses of accuracy or even numerical instabilities. In order to ensure that the parallelization errors are limited by the leading error of the numerical scheme such that second order convergence for the whole method can be acchieved, optimized parallelization concepts must be designed. With respect to these considerations this articles gives an overview of the current parallel pressure solver as well as the problems related to it and presents an alternative method, SCARC, to overcome the existing complicacies. Part I explains the theory, concept and implementation of this new strategy, whereas Part II describes a series of validation and verification tests to proof its correctness.

Description: Because CFD programs, like FDS, generally consist of a large number of different components representing the variety of participating numerical algorithms and chemical / physical processes, it is nearly impossible to verify such codes in their entirety, for example with comparisons of fire tests. Instead, a careful verification and validation with respect to the underlying mathematical conditions and applied numerical schemes is indispensable. In particular, error cancelations between single program components can only be detected by such detailed component-level tests. In part I of this article series a conceptual deficiency of the FDS program package with regard to multi-mesh computations was illustrated and an alternative domain decomposition strategy FDS-ScaRC was introduced. In this second part we will present the structure of a comprehensive test concept and the needs for a more mathematically and numerically orientated test procedure that is much more suited for a reliable evaluation than only a simple visual comparison of the numerical results with experimental fire tests. After a general introduction of our test concept we will demonstrate the high potential of the new FDS-\scarc{} technique compared to the FDS-FFT technique which is used in the FDS program package as yet. Based on this concept, we will present a comprehensive set of analytical and numerical test results.

Description: The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.

Description: Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of Möhring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05% gap of the optimum.

Description: Starting from the conservation laws for mass, momentum and energy together with a three species, bulk microphysic model, a model for the interaction of internal gravity waves and deep convective hot towers is derived by using multiscale asymptotic techniques. From the resulting leading order equations, a closed model is obtained by applying weighted averages to the smallscale hot towers without requiring further closure approximations. The resulting model is an extension of the linear, anelastic equations, into which moisture enters as the area fraction of saturated regions on the microscale with two way coupling between the large and small scale. Moisture reduces the effective stability in the model and defines a potential temperature sourceterm related to the net effect of latent heat release or consumption by microscale up- and downdrafts. The dispersion relation and group velocity of the system is analyzed and moisture is found to have several effects: It reduces energy transport by waves, increases the vertical wavenumber but decreases the slope at which wave packets travel and it introduces a lower horizontal cutoff wavenumber, below which modes turn into evanescent. Further, moisture can cause critical layers. Numerical examples for steadystate and timedependent mountain waves are shown and the effects of moisture on these waves are investigated.

Description: In dieser Arbeit wird ein neuer Ansatz zur Modellierung von thermal signifikanten Gefäßsträngen im Hyperthermie-Kontext betrachtet. Ausgehend von einer Konvektions-Diffusions-Gleichung wird durch Reskalierung des Massenflussterms eine Reduktion des Adergebietes auf eine 1D-Struktur erreicht. Nach numerischen Vorbetrachtungen wird die Grenzgleichung innerhalb einer verallgemeinerten Sobolev-Algebra formuliert. Die Untersuchung der Lösungsfamilie in klassischen Funktionenräumen zeigt, dass deren schwacher Grenzwert die Lösung der korrespondierenden Diffusions-Gleichung ist. Die Diskretisierung einer formalen Grenzgleichung mit Linienstromanteil stellt jedoch eine gute Approximation an die Diskretisierung des ursprünglichen Problems dar, wenn man die lokale Maschenweite an die Gefäßradien koppelt und bei erhöhtem Genauigkeitsbedarf auf ein vollständiges 3D-Modell umschaltet.