Library

Description: This is the documentation on current results of a research project jointly conducted by Stiftung Deutsche Kinemathek (SDK) and Zuse Institute Berlin (ZIB). In this project, we are working on a practical yet sustainable archiving solution for audiovisual material. In the course of the project two major obstacles were identified: 1) Metadata is collected according to standards established in the community but lacking a prescribed serialisation format. 2) Storage size of audiovisual material and time scales of production processes make it often impractical to defer submission for archival storage until all components have arrived and can be processed in one go.

Description: Kunst- und Kulturinstitutionen beschäftigen sich zunehmend mit der Digitalisierung ihrer Sammlungen, auch und gerade im Angesicht der Pandemie 2020. Dabei spielen nicht nur technische und organisatorische Fragen eine Rolle, vor allem rechtliche Aspekte führen oft zu Unsicherheit bei der digitalen Zugänglichmachung der Daten. Um diesen Unsicherheiten kompakt zu begegnen, gibt digiS die "Rechtsfibel" in Zusammenarbeit mit iRights und Paul Klimpel als Autor heraus. Darin werden unter anderem konkrete Fragen des Urheberrechts zu verschiedenen Objektgattungen, Lizenzfragen, Persönlichkeitsrecht und Datenschutz, die Online-Präsentation von Digitalisaten und zur Archivierung behandelt. Die Handreichung soll Mitarbeiter*innen in Kultur(-erbe)einrichtungen ermutigen, sich mit den rechtlichen Fragen bei der Digitalisierung auseinanderzusetzen, indem sie die vielen Facetten dieses Bereichs verständlich darstellt.

Description: As the natural gas market is moving towards short-term planning, accurate and robust short-term forecasts of the demand and supply of natural gas is of fundamental importance for a stable energy supply, a natural gas control schedule, and transport operation on a daily basis. We propose a hybrid forecast model, Functional AutoRegressive and Convolutional Neural Network model, based on state-of-the-art statistical modeling and artificial neural networks. We conduct short-term forecasting of the hourly natural gas flows of 92 distribution nodes in the German high-pressure gas pipeline network, showing that the proposed model provides nice and stable accuracy for different types of nodes. It outperforms all the alternative models, with an improved relative accuracy up to twofold for plant nodes and up to fourfold for municipal nodes. For the border nodes with rather flat gas flows, it has an accuracy that is comparable to the best performing alternative model.

Description: The choice of solvents influences crystalline solid formed during the crystallization of active pharmaceutical ingredients (API). The underlying effects are not always well understood because of the complexity of the systems. Theoretical models are often insufficient to describe this phenomenon. In this study, the crystallization behavior of the model drug paracetamol in different solvents was studied based on experimental and molecular dynamics data. The crystallization process was followed in situ using time-resolved Raman spectroscopy. Molecular dynamics with simulated annealing algorithm was used for an atomistic understanding of the underlying processes. The experimental and theoretical data indicate that paracetamol molecules adopt a particular geometry in a given solvent predefining the crystallization of certain polymorphs.

Description: We present an extension of Taylor's Theorem for the piecewise polynomial expansion of non-smooth evaluation procedures involving absolute value operations. Evaluation procedures are computer programs of mathematical functions in closed form expression and allow a different treatment of smooth operations or calls to the absolute value function. The well known classical Theorem of Taylor defines polynomial approximations of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential- or differential-algebraic equations, for the construction of solvers for continuous non-linear optimization of finite dimensional objective functions and for root solving of non-linear systems of equations. The long term goal is the stabilization and acceleration of already known methods and the derivation of new methods by incorporating piecewise polynomial Taylor expansions. The herein provided proof of the higher order approximation quality of the new generalized expansions is constructive and allows efficiently designed algorithms for the execution and computation of the piecewise polynomial expansions. As a demonstration towards the ultimate goal we will derive a prototype of a {\$}{\$}k{\$}{\$}k-step method on the basis of polynomial interpolation and the proposed generalized expansions.

Description: Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains.

Description: Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains.

Description: 混合整数計画法 (Mixed Integer Programming: MIP) は，MIP を解くソフトウェアである MIP ソルバが大規模な現実問題を解けるようになったこともあり，現実問題を解く有用な OR の手法として広く知られるようになった．しかしながら，MIP ソルバの開発に欠かせないベンチマーク・データセットおよび性能測定方法についてはそれほど広く知られているとは言い難い．ベンチマーク・データセットは注意を払って作成しないと，多くのバイアスがかかってしまう．それらのバイアスを可能な限りのぞき，真に有用なベンチマーク・テストの結果を得るためには複数の人数で多大な労力を割く必要がある．本稿では，そのような MIP ソルバ開発の背景として重要な役割を果たしてきた MIPLIB と Hans Mittelmann’s benchmarks について解説する．また，本稿において Hans Mittelmann’s benchmarks は，BENCHMARKS FOR OPTIMIZATION SOFTWAREのページ (http://plato.asu.edu/bench.html) に示されているベンチマークである．

Description: We present a transductive learning approach for morphometric osteophyte grading based on geometric deep learning. We formulate the grading task as semi-supervised node classification problem on a graph embedded in shape space. To account for the high-dimensionality and non-Euclidean structure of shape space we employ a combination of an intrinsic dimension reduction together with a graph convolutional neural network. We demonstrate the performance of our derived classifier in comparisons to an alternative extrinsic approach.

Description: A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5%.

Description: In order to better understand the relationship between shape of the nasal cavity and to find objective classification for breathing obstruction, a population of 25 cases of healthy nasal cavity and 27 cases with diagnosed nasal airway obstruction (NAO) was examined for correlations between morphological, clinical and CFD parameters. For this purpose a workflow was implemented in Tcl to perform automatic measurements of morphological parameters of nasal cavity surfaces in Amira, which has as output a table with all estimated values. Furthermore, the statistical analysis was designed using Python to find the most probable subset of parameters that are predictors of nasal cavity pathology and consisted of correlation analysis, the selection of the best possible subset of parameters that could be used as predictors of clinically stated pathology of the nasal cavity by a logistic regression classifier. As a result, 10 most promising parameters were identified: mean distance between the two isthmuses, left isthmus contour, area ratio between the two isthmuses, left isthmus height, height ratio between the two isthmuses, left isthmus width, right isthmus width, right isthmus hydraulic diameter, mean distance of septal curvature between the septum enclosing walls of the nasal cavity, velocities volume average by expiration. As it turns out, most parameters refer to the isthmus region. This was to be expected since this region plays an important role in the airflow system of the nasal cavity.

Description: The growing importance of mathematical software in everyday life—in applications such as internet communication, traffic, and artificial intelligence—necessitates advances in software documentation services to raise awareness of existing packages and their usage. Such information helps potential software developers and users make informed choices about packages that could advance their work in modeling, simulation, and analysis. At the same time, software presents novel challenges to information services that require the development of new methods and means of processing. swMATH provides users with an overview of a broad range of mathematical software and extends documentation services for publications related to such software. It acts as a counterpart to the established abstracting and reviewing services for mathematical publications and has nearly 30,000 entries, making it one of the most comprehensive documentation services in mathematics.

Description: More and more diseases have been found to be strongly correlated with disturbances in the microbiome constitution, e.g., obesity, diabetes, or some cancer types. Thanks to modern high-throughput omics technologies, it becomes possible to directly analyze human microbiome and its influence on the health status. Microbial communities are monitored over long periods of time and the associations between their members are explored. These relationships can be described by a time-evolving graph. In order to understand responses of the microbial community members to a distinct range of perturbations such as antibiotics exposure or diseases and general dynamical properties, the time-evolving graph of the human microbial communities has to be analyzed. This becomes especially challenging due to dozens of complex interactions among microbes and metastable dynamics. The key to solving this problem is the representation of the time-evolving graphs as fixed-length feature vectors preserving the original dynamics. We propose a method for learning the embedding of the time-evolving graph that is based on the spectral analysis of transfer operators and graph kernels. We demonstrate that our method can capture temporary changes in the time-evolving graph on both synthetic data and real-world data. Our experiments demonstrate the efficacy of the method. Furthermore, we show that our method can be applied to human microbiome data to study dynamic processes.

Description: Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.

Description: Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib.

Description: Conformational dynamics is essential to biomolecular processes. Markov State Models (MSMs) are widely used to elucidate dynamic properties of molecular systems from unbiased Molecular Dynamics (MD). However, the implementation of reweighting schemes for MSMs to analyze biased simulations is still at an early stage of development. Several dynamical reweighing approaches have been proposed, which can be classified as approaches based on (i) Kramers rate theory, (ii) rescaling of the probability density flux, (iii) reweighting by formulating a likelihood function, (iv) path reweighting. We present the state-of-the-art and discuss the methodological differences of these methods, their limitations and recent applications.

Description: Phage display biopanning with Illumina next-generation sequencing (NGS) is applied to reveal insights into peptide-based adhesion domains for polypropylene (PP). One biopanning round followed by NGS selects robust PP-binding peptides that are not evident by Sanger sequencing. NGS provides a significant statistical base that enables motif analysis, statistics on positional residue depletion/enrichment, and data analysis to suppress false-positive sequences from amplification bias. The selected sequences are employed as water-based primers for PP?metal adhesion to condition PP surfaces and increase adhesive strength by 100\% relative to nonprimed PP.

Description: The temporally and spatially resolved tracking of lithium intercalation and electrode degradation processes are crucial for detecting and understanding performance losses during the operation of lithium-batteries. Here, high-throughput X-ray computed tomography has enabled the identification of mechanical degradation processes in a commercial Li/MnO2 primary battery and the indirect tracking of lithium diffusion; furthermore, complementary neutron computed tomography has identified the direct lithium diffusion process and the electrode wetting by the electrolyte. Virtual electrode unrolling techniques provide a deeper view inside the electrode layers and are used to detect minor fluctuations which are difficult to observe using conventional three dimensional rendering tools. Moreover, the ‘unrolling’ provides a platform for correlating multi-modal image data which is expected to find wider application in battery science and engineering to study diverse effects e.g. electrode degradation or lithium diffusion blocking during battery cycling.

Description: On average, an approved drug today costs $2-3 billion and takes over ten years to develop1. In part, this is due to expensive and time-consuming wet-lab experiments, poor initial hit compounds, and the high attrition rates in the (pre-)clinical phases. Structure-based virtual screening (SBVS) has the potential to mitigate these problems. With SBVS, the quality of the hits improves with the number of compounds screened2. However, despite the fact that large compound databases exist, the ability to carry out large-scale SBVSs on computer clusters in an accessible, efficient, and flexible manner has remained elusive. Here we designed VirtualFlow, a highly automated and versatile open-source platform with perfect scaling behaviour that is able to prepare and efficiently screen ultra-large ligand libraries of compounds. VirtualFlow is able to use a variety of the most powerful docking programs. Using VirtualFlow, we have prepared the largest and freely available ready-to-dock ligand library available, with over 1.4 billion commercially available molecules. To demonstrate the power of VirtualFlow, we screened over 1 billion compounds and discovered a small molecule inhibitor (iKeap1) that engages KEAP1 with nanomolar affinity (Kd = 114 nM) and disrupts the interaction between KEAP1 and the transcription factor NRF2. We also identified a set of structurally diverse molecules that bind to KEAP1 with submicromolar affinity. This illustrates the potential of VirtualFlow to access vast regions of the chemical space and identify binders with high affinity for target proteins.

Description: Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.

Description: Structure-based virtual screening approaches have the ability to dramatically reduce the time and costs associated to the discovery of new drug candidates. Studies have shown that the true hit rate of virtual screenings improves with the scale of the screened ligand libraries. Therefore, we have recently developed an open source drug discovery platform (VirtualFlow), which is able to routinely carry out ultra-large virtual screenings. One of the primary challenges of molecular docking is the circumstance when the protein is highly dynamic or when the structure of the protein cannot be captured by a static pose. To accommodate protein dynamics, we report the extension of VirtualFlow to allow the docking of ligands using a grey wolf optimization algorithm using the docking program GWOVina, which substantially improves the quality and efficiency of flexible receptor docking compared to AutoDock Vina. We demonstrate the linear scaling behavior of VirtualFlow utilizing GWOVina up to 128 000 CPUs. The newly supported docking method will be valuable for drug discovery projects in which protein dynamics and flexibility play a significant role.

Description: The determination of time of death is one of the central tasks in forensic medicine. A standard method of time of death estimation elies on matching temperature measurements of the corpse with a post-mortem cooling model. In addition to widely used empirical post-mortem models, modelling based on a precise mathematical simulation of the cooling process have been gaining popularity. The simulation based cooling models and the resulting time of death estimates dependon a large variety of parameters. These include hermal properties for different body tissue types, environmental conditions such as temperature and air flow, and the presence of clothing and coverings. In this thesis we focus on a specific arameter - the contact between corpse and underground - and investigate its influence on the time of death estimation. Resulting we aim to answer the question whether it is necessary to consider contact mechanics in the underlying mathematical cooling model.

Description: Though gait asymmetry is used as a metric of functional recovery in clinical rehabilitation, there is no consensus on an ideal method for its evaluation. Various methods have been proposed but are limited in scope, as they can often use only positive signals or discrete values extracted from time-scale data as input. By defining five symmetry axioms, a framework for benchmarking existing methods was established and a new method was described here for the first time: the weighted universal symmetry index (wUSI), which overcomes limitations of other methods. Both existing methods and the wUSI were mathematically compared to each other and in respect to their ability to fulfill the proposed symmetry axioms. Eligible methods that fulfilled these axioms were then applied using both discrete and continuous approaches to ground reaction force (GRF) data collected from healthy gait, both with and without artificially induced asymmetry using a single instrumented elbow crutch. The wUSI with a continuous approach was the only symmetry method capable of determining GRF asymmetries in different walking conditions in all three planes of motion. When used with a continuous approach, the wUSI method was able to detect asymmetries while avoiding artificial inflation, a common problem reported in other methods. In conclusion, the wUSI is proposed as a universal method to quantify three-dimensional GRF asymmetries, which may also be expanded to other biomechanical signals.

Description: In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.

Description: In this paper, we introduce the Maximum Diversity Assortment Selection Problem (MADASS), which is a generalization of the 2-dimensional Cutting Stock Problem (2CSP). Given a set of rectangles and a rectangular container, the goal of 2CSP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. In MADASS, we need to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as minimum or average normalized Hamming-Distance of all assortment pairs. The MADASS Problem was used in the 11th AIMMS-MOPTA Competition in 2019. The methods we describe in this article and the computational results won the contest. In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2CSP literature.

Description: We present visual methods for the analysis and comparison of the results of curved fibre reconstruction algorithms, i.e., of algorithms extracting characteristics of curved fibres from X-ray computed tomography scans. In this work, we extend previous methods for the analysis and comparison of results of different fibre reconstruction algorithms or parametrisations to the analysis of curved fibres. We propose fibre dissimilarity measures for such curved fibres and apply these to compare multiple results to a specified reference. We further propose visualisation methods to analyse differences between multiple results quantitatively and qualitatively. In two case studies, we show that the presented methods provide valuable insights for advancing and parametrising fibre reconstruction algorithms, and support in improving their results in characterising curved fibres.

Description: Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.

Description: Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.

Description: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.

Description: The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality.

Description: We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.

Description: We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.

Description: Due to the increase in accessibility and robustness of sequencing technology, single cell RNA-seq (scRNA-seq) data has become abundant. The technology has made significant contributions to discovering novel phenotypes and heterogeneities of cells. Recently, there has been a push for using single-- or multiple scRNA-seq snapshots to infer the underlying gene regulatory networks (GRNs) steering the cells' biological functions. To date, this aspiration remains unrealised. In this paper, we took a bottom-up approach and curated a stochastic two gene interaction model capturing the dynamics of a complete system of genes, mRNAs, and proteins. In the model, the regulation was placed upstream from the mRNA on the gene level. We then inferred the underlying regulatory interactions from only the observation of the mRNA population through~time. We could detect signatures of the regulation by combining information of the mean, covariance, and the skewness of the mRNA counts through time. We also saw that reordering the observations using pseudo-time did not conserve the covariance and skewness of the true time course. The underlying GRN could be captured consistently when we fitted the moments up to degree three; however, this required a computationally expensive non-linear least squares minimisation solver. There are still major numerical challenges to overcome for inference of GRNs from scRNA-seq data. These challenges entail finding informative summary statistics of the data which capture the critical regulatory information. Furthermore, the statistics have to evolve linearly or piece-wise linearly through time to achieve computational feasibility and scalability.

Description: Molecular simulations of ligand–receptor interactions are a computational challenge, especially when their association- (‘on’-rate) and dissociation- (‘off’-rate) mechanisms are working on vastly differing timescales. One way of tackling this multiscale problem is to compute the free-energy landscapes, where molecular dynamics (MD) trajectories are used to only produce certain statistical ensembles. The approach allows for deriving the transition rates between energy states as a function of the height of the activation-energy barriers. In this article, we derive the association rates of the opioids fentanyl and N-(3-fluoro-1-phenethylpiperidin-4-yl)-N-phenyl propionamide (NFEPP) in a μ-opioid receptor by combining the free-energy landscape approach with the square-root-approximation method (SQRA), which is a particularly robust version of Markov modelling. The novelty of this work is that we derive the association rates as a function of the pH level using only an ensemble of MD simulations. We also verify our MD-derived insights by reproducing the in vitro study performed by the Stein Lab.

Description: The problem of determining the rate of rare events in dynamical systems is quite well-known but still difficult to solve. Recent attempts to overcome this problem exploit the fact that dynamic systems can be represented by a linear operator, such as the Koopman operator. Mathematically, the rare event problem comes down to the difficulty in finding invariant subspaces of these Koopman operators K. In this article, we describe a method to learn basis functions of invariant subspaces using an artificial neural Network.

Description: Molecular simulations of ligand-receptor interactions are a computational challenge, especially when their association- (``on''-rate) and dissociation- (``off''-rate) mechanisms are working on vastly differing timescales. In addition, the timescale of the simulations themselves is, in practice, orders of magnitudes smaller than that of the mechanisms; which further adds to the complexity of observing these mechanisms, and of drawing meaningful and significant biological insights from the simulation. One way of tackling this multiscale problem is to compute the free-energy landscapes, where molecular dynamics (MD) trajectories are used to only produce certain statistical ensembles. The approach allows for deriving the transition rates between energy states as a function of the height of the activation-energy barriers. In this article, we derive the association rates of the opioids fentanyl and N-(3-fluoro-1-phenethylpiperidin-4-yl)- N-phenyl propionamide (NFEPP) in a $\mu$-opioid receptor by combining the free-energy landscape approach with the square-root-approximation method (SQRA), which is a particularly robust version of Markov modelling. The novelty of this work is that we derive the association rates as a function of the pH level using only an ensemble of MD simulations. We also verify our MD-derived insights by reproducing the in vitro study performed by the Stein Lab, who investigated the influence of pH on the inhibitory constant of fentanyl and NFEPP (Spahn et al. 2017). MD simulations are far more accessible and cost-effective than in vitro and in vivo studies. Especially in the context of the current opioid crisis, MD simulations can aid in unravelling molecular functionality and assist in clinical decision-making; the approaches presented in this paper are a pertinent step forward in this direction.

Description: Growing demand, distributed generation, such as renewable energy sources (RES), and the increasing role of storage systems to mitigate the volatility of RES on a medium voltage level, push existing distribution grids to their limits. Therefore, necessary network expansion needs to be evaluated to guarantee a safe and reliable electricity supply in the future taking these challenges into account. This problem is formulated as an optimal power flow (OPF) problem which combines network expansion, volatile generation and storage systems, minimizing network expansion and generation costs. As storage systems introduce a temporal coupling into the system, a multiperiod OPF problem is needed and analysed in this thesis. To reduce complexity, the network expansion problem is represented in a continuous nonlinear programming formulation by using fundamental properties of electrical engeneering. This formulation is validated succesfully against a common mixed integer programming approach on a 30 and 57 bus network with respect to solution and computing time. As the OPF problem is, in general, a nonconvex, nonlinear problem and, thus, hard to solve, convex relaxations of the power flow equations have gained increasing interest. Sufficient conditions are represented which guarantee exactness of a second-order cone (SOC) relaxation of an operational OPF in radial networks. In this thesis, these conditions are enhanced for the network expansion planning problem. Additionally, nonconvexities introduced by the choice of network expansion variables are relaxed by using McCormick envelopes. These relaxations are then applied on the multiperiod OPF and compared to the original problem on a 30 and a 57 bus network. In particular, the computational time is decreased by an order up to 10^2 by the SOC relaxation while it provides either an exact solution or a sufficient lower bound on the original problem. Finally, a sensitivity study is performed on weights of network expansion costs showing strong dependency of both the solution of performed expansion and solution time on the chosen weights.

Description: Demand Side Management (DSM) is usually considered as a process of energy consumption shifting from peak hours to off-peak times. DSM does not always reduce total energy consumption, but it helps to meet energy demand and supply. For example, it balances variable generation from renewables (such as solar and wind) when energy demand differs from renewable generation.

Description: Natural gas is considered by many to be the most important energy source for the future. The objectives of energy commodities strategic problems can be mainly related to natural gas and deal with the definition of the “optimal” gas pipelines design which includes a number of related sub problems such as: Gas stations (compression) location and Gas storage locations, as well as compression station design and optimal operation.

Description: To attain the highest performance of energy supply systems, it is necessary to determine design specifications optimally in consideration of operational strategies corresponding to seasonal and hourly variations in energy demands. A hierarchical mixed-integer linear programming method has been proposed to solve such an optimal design problem efficiently. In this paper, a method of reducing model by clustering periods with the k-medoids method is applied to the relaxed optimal design problem at the upper level. Through a case study, it is clarified how the proposed method is effective to enhance the computation efficiency in a large scale optimal design problem.

Description: To attain the highest performance of energy supply systems, it is necessary to determine design specifications optimally in consideration of operational strategies corresponding to seasonal and hourly variations in energy demands. Mixed-integer linear programming (MILP) methods have been applied widely to such optimal design problems. A hierarchical MILP method has been proposed to solve the problems very efficiently. In addition, by utilizing features of the hierarchical MILP method, a method of reducing model by clustering periods based on the optimal operational strategies of equipment has been proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. In this paper, these methods are applied to the multiobjective optimal design of a cogeneration system by considering the annual total cost and primary energy consumption as the objective functions to be minimized. Through a case study, it turns out that the model reduction by the operation-based time-period clustering is effective in terms of the computation efficiency when importance is given to the first objective function, while it is not when importance is given to the second objective function.

Description: A robust optimal design method of energy supply systems under uncertain energy demands has been proposed using a mixed-integer linear model for constituent equipment. However, this method takes a long computation time, and thus it can be applied only to small-scale problems. In this paper, a hierarchical optimization method is applied to two types of optimization problems for evaluating robustness to solve them efficiently. In a case study, the proposed method is applied to a cogeneration system with a complex configuration, and the validity and effectiveness of the method are ascertained.

Description: A robust optimal design method of energy supply systems under uncertain energy demands has been proposed using a mixed- integer linear model for constituent equipment. A robust optimal design problem has been formulated as a three-level min-max- min optimization one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret criterion, and considering hierarchical relationships among design variables, uncertain energy demands, and operation variables. Since this problem must be solved by a special algorithm and is too difficult to solve even using a commercial solver, a hierarchical optimization approach has been applied to solve the problem but its application is limited only to small scale toy problems. In this paper, some strategies are introduced into the hierarchical optimization approach to enhance the computation efficiency for the purpose of applying the approach to large scale practical problems. In a case study, the proposed approach is applied to the robust optimal design of a cogeneration system with a complex configuration, and the validity and effectiveness of the method are ascertained.

Description: Dieses Dokument legt Parameter und Formate für die Übertragung sprachbasierter Daten zwischen verschiedenen KI-Ökosystemen fest.

Description: Cows typically have different numbers of follicular waves during their hormonal cycle. Understanding the underlying regulations leads to insights into the reasons for declined fertility, a phenomenon that has been observed during the last decades. We present a systematic approach based on Fourier analysis to examine how parameter changes in a model of the bovine estrous cycle lead to different wave patterns. Even without any biological considerations, this allows to detect the responsible model parameters that control the type of periodicity of the solution, thus supporting experimental planning of animal scientists.

Description: This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques.

Description: Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.

Description: Dieser Beitrag stellt mögliche Ansätze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ansätze bilden im Allgemeinen die Grundlage für konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien zählt die Verkleinerung der Modelldimensionen, was beispielsweise durch Ändern der zeitlichen, räumlichen oder technologischen Auflösung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar häufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivität werden jedoch meist nicht durchgeführt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Größenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verkürzte Betrachtungszeiträume das größte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-Lösungsverfahrens mit multiplen Threads unter Vernachlässigung des Cross-Over.

Description: The antiepileptic drug carbamazepine (CBZ) and its main metabolites carbamazepine-10,11-epoxide (EP-CBZ) and 10,11-dihydro-10,11-dihydroxy-carbamazepine (DiOH-CBZ) were chosen as test substances to assess chronic toxicity on the non-biting midge Chironomus riparius. All three substances were tested in a 40-day sediment full life cycle test (according to OECD 233) in which mortality, emergence, fertility, and clutch size were evaluated. In addition, these parameters were integrated into the population growth rate to reveal population relevant effects. With an LC50 of 0.203 mg/kg (time-weighted mean), the metabolite EP-CBZ was significantly more toxic than the parent substance CBZ (LC50: 1.11 mg/kg). Especially mortality, emergence, and fertility showed to be sensitive parameters under the exposure to CBZ and EP-CBZ. By using classical molecular dynamics (MD) simulations, the binding of CBZ to the ecdysone receptor was investigated as one possible mode of action but showed to be unlikely. The second metabolite DiOH-CBZ did not show any effects within the tested concentration rage (0.171 – 1.22 mg/kg). Even though CBZ was less toxic compared to EP-CBZ, CBZ is found in the environment at much higher concentrations and causes therefore a higher potential risk for sediment dwelling organisms compared to its metabolites. Nevertheless, the current study illustrates the importance of including commonly found metabolites into the risk assessment of parent substances.

Description: We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model’s nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.

Description: The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.

Description: Verteilte Dateisysteme, wie sie unter anderem in Cloud-Umgebungen eingesetzt werden, werden häufig von verschiedenen Anwendern und Anwendungen zeitgleich verwendet. Da diese Ressourcen in Cloud-Umgebungen gemietet sind, muss sichergestellt werden, dass ein Kunde nur die Ressourcen verwenden kann, für die er bezahlt hat. Andernfalls könnten andere Kunden beeinträchtigt werden. Solch eine Obergrenze wird auch als Quota bezeichnet. Speziell für objektbasierte Dateisysteme, bei denen die Metadaten einer Datei von den Dateiinhalten getrennt gespeichert und verwaltet werden, erfordert die Forcierung einer Quota ein verteiltes Protokoll. Im Rahmen der vorliegenden Arbeit wurde ein Quota-Protokoll für objektbasierte Dateisysteme entwickelt und implementiert. Bei einer aktiven Quota wird zunächst ein Teil des Speicherplatzes für eine bestimmte Datei blockiert, der als Voucher bezeichnet wird. Anschließend wird dem Client die maximale Dateigröße in signierter Form zugewiesen. Sie ergibt sich aus der Summe der bisherigen Dateigröße und allen erstellten Vouchers. Durch diesen Ansatz können die Speicherserver bei jedem Zugriff lokal prüfen, ob der Schreibzugriff die maximale Dateigröße überschreiten würde. Reicht diese nicht aus, muss ein zusätzlicher Voucher erstellt werden, sofern noch Speicherplatz verfügbar ist. Nicht verbrauchter Speicherplatz wird am Ende wieder freigegeben. Zusätzlich unterstützt das Protokoll die Verteilung der Inhalte einer Datei auf mehrere Server (Striping) sowie Sparse-Dateien, bei denen beliebige Bereiche der Datei leer bleiben. Die Implementierung erfolgte im objektbasierten Dateisystem XtreemFS. Dabei wurden spezielle Funktionen von XtreemFS, wie die Dateireplikation, mit einbezogen. In einer abschließenden Evaluation wurde der Einfluss des implementierten Quota- Protokolls bezüglich der Performanz von XtreemFS untersucht. Dabei zeigte sich zunächst, dass bei einer aktiven Quota die Performanz beim Schreiben großer Daten- mengen abhängig von der eingestellten Voucher-Größe ist. Ist diese zu niedrig gewählt, so muss der Client seine maximale Dateigröße durch zusätzliche Anfragen beim Metada- tenserver erhöhen, was die Performanz negativ beeinträchtigt. Bei einer Voucher-Größe von 100 MiB wurde beim Schreiben einer 10 GiB-Datei ein Performanzverlust von unter 2% gemessen, verglichen mit dem Entwicklungsstand ohne implementiertes Quota- Protokoll. Bei der Erstellung mehrerer 64 KiB-Dateien wurde aufgrund zusätzlicher Nachrichten ein Verlust von rund 8% gemessen.

Description: The application of advanced imaging techniques for the ultrasonic inspection of inhomogeneous anisotropic materials like austenitic and dissimilar welds requires information about acoustic wave propagation through the material, in particular travel times between two points in the material. Forward ray tracing is a popular approach to determine traveling paths and arrival times but is ill suited for inverse problems since a large number of rays have to be computed in order to arrive at prescribed end points. In this contribution we discuss boundary value problems for acoustic rays, where the ray path between two given points is determined by solving the eikonal equation. The implementation of such a two point boundary value ray tracer for sound field simulations through an austenitic weld is described and its efficiency as well as the obtained results are compared to those of a forward ray tracer. The results are validated by comparison with experimental results and commercially available UT simulation tools. As an application, we discuss an implementation of the method for SAFT (Synthetic Aperture Focusing Technique) reconstruction. The ray tracer calculates the required travel time through the anisotropic columnar grain structure of the austenitic weld. There, the formulation of ray tracing as a boundary value problem allows a straightforward derivation of the ray path from a given transducer position to any pixel in the reconstruction area and reduces the computational cost considerably.

Description: Digitale Langzeitarchivierung erfolgt auf Grundlage verbindlicher Regelungen zwischen Langzeitarchiv und Datengeber. Detaillierte organisatorische und technische Bedingungen für Datenübernahmen werden dabei in Absprache zwischen den Kooperationspartnern in einer Übernahmevereinbarung festgehalten. Im Rahmen der Entwicklung des Langzeitarchivs EWIG am Zuse Institute Berlin ist die hier dokumentierte Mustervorlage für Übernahmevereinbarungen entstanden.

Description: The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based on real data from a major hospital in Berlin.

Description: We consider the problem of a price-taker generating company that wants to select energy offering strategies for its generation units, to maximize the profit while considering the uncertainty of market price. First, we review central references available in literature about the use of Robust Optimization (RO) for price-uncertain energy offering, pointing out how they can expose to the risk of suboptimal and even infeasible offering. We then propose a new RO method for energy offering that overcomes all the limits of other RO methods. We show the effectiveness of the new method on realistic instances provided by our industrial partners, getting very high increases in profit. Our method is based on Multiband Robustness (MR - Büsing, D'Andreagiovanni, 2012), an RO model that refines the classical RO model by Bertsimas and Sim, while maintaining its computational tractability and accessibility. MR is essentially based on the use of histogram-like uncertainty sets, which result particularly suitable to represent empirical distributions commonly available in uncertain real-world optimization problems.

Description: This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.

Description: The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.

Description: We study in experiment and theory thermal energy and charge transfer close to the quantum limit in a ballistic nanodevice, consisting of multiply connected one-dimensional electron waveguides. The fabricated device is based on an AlGaAs/GaAs heterostructure and is covered by a global top-gate to steer the thermal energy and charge transfer in the presence of a temperature gradient, which is established by a heating current. The estimate of the heat transfer by means of thermal noise measurements shows the device acting as a switch for charge and thermal energy transfer. The wave-packet simulations are based on the multi-terminal Landauer-Büttiker approach and confirm the experimental finding of a mode-dependent redistribution of the thermal energy current, if a scatterer breaks the device symmetry.

Description: Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.

Description: While the majority of the photochemical states and pathways related to the biological capture of solar energy are now well understood and provide paradigms for artificial device design, additional low-energy states have been discovered in many systems with obscure origins and significance. However, as low-energy states are naively expected to be critical to function, these observations pose important challenges. A review of known properties of low energy states covering eight photochemical systems, and options for their interpretation, are presented. A concerted experimental and theoretical research strategy is suggested and outlined, this being aimed at providing a fully comprehensive understanding.

Description: This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.

Description: In many applications one is interested to compute transition probabilities of a Markov chain. This can be achieved by using Monte Carlo methods with local or global sampling points. In this article, we analyze the error by the difference in the $L^2$ norm between the true transition probabilities and the approximation achieved through a Monte Carlo method. We give a formula for the error for Markov chains with locally computed sampling points. Further, in the case of reversible Markov chains, we will deduce a formula for the error when sampling points are computed globally. We will see that in both cases the error itself can be approximated with Monte Carlo methods. As a consequence of the result, we will derive surprising properties of reversible Markov chains.

Description: In this paper we present a novel extended formulation for the line planning problem that is based on what we call “configurations” of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.

Description: One of the main goals of mathematical modelling in systems biology related to medical applications is to obtain patient-specific parameterisations and model predictions. In clinical practice, however, the number of available measurements for single patients is usually limited due to time and cost restrictions. This hampers the process of making patient-specific predictions about the outcome of a treatment. On the other hand, data are often available for many patients, in particular if extensive clinical studies have been performed. Using these population data, we propose an iterative algorithm for contructing an informative prior distribution, which then serves as the basis for computing patient-specific posteriors and obtaining individual predictions. We demonsrate the performance of our method by applying it to a low-dimensional parameter estimation problem in a toy model as well as to a high-dimensional ODE model of the human menstrual cycle, which represents a typical example from systems biology modelling.

Description: All relevant implementation aspects of finite element methods are discussed in this book. The focus is on algorithms and data structures as well as on their concrete implementation. Theory is covered as far as it gives insight into the construction of algorithms.Throughout the exercises a complete FE-solver for scalar 2D problems will be implemented in Matlab/Octave.

Description: We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex.