Library

Description: In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.

Description: The landscape of applications and subroutines relying on shortest path computations continues to grow steadily. This growth is driven by the undeniable success of shortest path algorithms in theory and practice. It also introduces new challenges as the models and assessing the optimality of paths become more complicated. Hence, multiple recent publications in the field adapt existing labeling methods in an ad-hoc fashion to their specific roblem variant without considering the underlying general structure: they always deal with multi-criteria scenarios and those criteria define different partial orders on the paths. In this paper, we introduce the partial order shortest path problem (POSP), a generalization of the multi-objective shortest path problem (MOSP) and in turn also of the classical shortest path problem. POSP captures the particular structure of many shortest path applications as special cases. In this generality, we study optimality conditions or the lack of them, depending on the objective functions’ properties. Our final contribution is a big lookup table summarizing our findings and providing the reader an easy way to choose among the most recent multicriteria shortest path algorithms depending on their weight structures. Examples range from time-dependent shortest path and bottleneck path problems to the fuzzy shortest path problem and complex financial weight functions studied in the public transportation community. Our results hold for general digraphs and therefore surpass previous generalizations that were limited to acyclic graphs.

Description: The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.

Description: We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed.

Description: Our faces and facial expressions are an important means of communication and social interaction. One goal of the behavioral sciences is to better understand how the features of the faces that we look at influence our behavior. These include static features like facial proportions or the shape and color of certain parts of a face which primarily constitute facial identity, as well as dynamic movements resulting from the activation of the mimic musculature. Experimental psychology provides an empirical approach to this endeavor. In experiments, participants are typically exposed to images or videos of realistic faces with specifically controlled features. By analysis of the reactions to such stimuli, conclusions can be drawn about the influence of facial features on the participants’ behavior. Psychologists today mostly generate face stimuli with the help of digital tools. Image editing with Photoshop is highly flexible, but also time-consuming and subjective. Using tools like Psychomorph or Fantamorph is easier and more objective, but does not allow specific control over facial features. In contrast, stimulus generation with 3D Morphable Face Models (3DMMs) offers a better balance between objectivity, ease of use, and flexibility. 3DMMs are statistical models which have been determined from 3D scans of real people’s faces and facial expressions. After these training scans have been brought into correspondence, methods like principal component analysis (PCA) can be used to determine the major modes of variation of facial shape and texture in the data. Such modes typically vary the overall facial proportions, expressions, or skin color. They can be individually controlled and flexibly combined to generate new faces and facial expressions. The plausibility of the generated faces can be ensured by having the mode combinations follow the multivariate distribution of the training data. 3DMMs have been mostly used by psychologists for the generation of stimulus images of faces with neutral expression. Static and dynamic stimuli of facial expressions are also of great interest, but generation with 3DMMs is less common. A problem is that the majority of current 3DMMs can only generate facial movements according to the six prototypic expressions of anger, disgust, fear, happiness, sadness, and surprise. More diverse or subtle expressions are often impossible. Among other reasons, this is due to the difficulty in establishing accurate correspondence in the training data. Further, the modes of most 3DMMs were created by means of PCA. These modes often lack interpretability, fail to generate facial details, and rarely provide psychologists a specific control over identity or expression features. Some 3DMMs also generate subtle artifacts that might lead to undesired effects during face perception. They are also less realistic than faces which were designed by artistic experts for recent computer games and animated movies. Last but not least, current 3DMMs have probably not yet been used for interactive experiments in virtual reality (VR) for technical reasons. Although they provide many advantages also beyond the generation of static or dynamic stimuli, the limitations of current 3DMMs have so far prevented a widespread usage in experimental psychology. The goal of this dissertation is to foster the creation and usage of 3DMMs in this context. To this end, we make three major contributions. First, we describe a matching method that establishes correspondence for 3D face scans with a very high accuracy. Unlike the most commonly used methods, it transforms the facial features into a 2D intermediate representation so that they can be aligned to a reference using image registration. We perform experiments with a large database of 3D scans of faces and facial expressions showing that our method outperforms previous approaches. Second, the 3D scans which were previously brought into correspondence are used for the creation of a 3DMM whose resolution is an order of magnitude higher than that of most existing models. We learn a variety of meaningful modes that, e.g., vary features only in specific regions of the face, or that are related to demographic factors such as ethnicity and age. Further, modes of local facial movements are established that can be flexibly combined into a large variety of expressions. We evaluate the quality of the newly created 3DMM in two experiments. Our results show its advantages over previous models, especially the higher degree of realism of dynamic stimuli of facial expressions which were created with our model. Third, we demonstrate that 3DMMs can not only be used for the generation of stimuli. We develop two experimental methods that are readily applicable in experimental psychology. Initially, we create 3D avatar faces with our 3DMM that are readily applicable in VR. They are used in a new open source framework for virtual mirror experiments on self-face perception. A study is conducted which demonstrates the advantages of the framework over previous methods. Furthermore, our 3DMM is used to create a method for improved control of facial asymmetry in existing stimulus photographs. We show that the method accounts for different dimensions of facial asymmetry and is less sensitive than previous approaches to extrinsic factors like the posture of the head. The different methods are evaluated in a study investigating the influence of facial asymmetry on ratings of attractiveness, femininity, and masculinity. The results indicate the benefits and validity of our method.

Description: Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.

Description: Flight planning, the computation of optimal routes in view of flight time and fuel consumption under given weather conditions, is traditionally done by finding globally shortest paths in a predefined airway network. Free flight trajectories, not restricted to a network, have the potential to reduce the costs significantly, and can be computed using locally convergent continuous optimal control methods. Hybrid methods that start with a discrete global search and refine with a fast continuous local optimization combine the best properties of both approaches, but rely on a good switchover, which requires error estimates for discrete paths relative to continuous trajectories. Based on vertex density and local complete connectivity, we derive localized and a priori bounds for the flight time of discrete paths relative to the optimal continuous trajectory, and illustrate their properties on a set of benchmark problems. It turns out that localization improves the error bound by four orders of magnitude, but still leaves ample opportunities for tighter bounds using a posteriori error estimators.

Description: It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.

Description: Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.

Description: The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.

Description: The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.

Description: The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.

Description: Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a 4% decrease in solve time, and an 8% decrease in number of nodes over affected instances of MIPLIB 2017.

Description: Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.

Description: A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.

Description: A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML.

Description: Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident and multiple works in recent years have focused on this task. In this work, using a unified framework, we show that there exists a polyhedron that simultaneously encodes, in its facial structure, all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample size. Notably, the size of the polyhedral representation depends only linearly on the sample size, and a better dependency on several other network parameters is unlikely. Using this general result, we compute the size of the polyhedral encoding for commonly used neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal strong structure arising from these problems.

Description: The physiology of every living cell is regulated at some level by transporter proteins which constitute a relevant portion of membrane-bound proteins and are involved in the movement of ions, small and macromolecules across bio-membranes. The importance of transporter proteins is unquestionable. The prediction and study of previously unknown transporters can lead to the discovery of new biological pathways, drugs and treatments. Here we present PortPred, a tool to accurately identify transporter proteins and their substrate starting from the protein amino acid sequence. PortPred successfully combines pre-trained deep learning-based protein embeddings and machine learning classification approaches and outperforms other state-of-the-art methods. In addition, we present a comparison of the most promising protein sequence embeddings (Unirep, SeqVec, ProteinBERT, ESM-1b) and their performances for this specific task.

Description: Stochastic optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. Because the latter is often unknown, distributionally robust optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy that converges at a rate of O(log T/T−−√), where T is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.

Description: In this paper we discuss the notion of research data for the field of mathematics and report on the status quo of research-data management and planning. A number of decentralized approaches are presented and compared to needs and challenges faced in three use cases from different mathematical subdisciplines. We highlight the importance of tailoring research-data management plans to mathematicians’ research processes and discuss their usage all along the data life cycle.

Description: Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult.

Description: In this work, we adapt an established model for the Ca2+-induced fusion dynamics of synaptic vesicles and employ a lumping method to reduce its complexity. In the reduced system, sequential Ca2+-binding steps are merged to a single releasable state, while keeping the important dependence of the reaction rates on the local Ca2+ concentration. We examine the feasibility of this model reduction for a representative stimulus train over the physiologically relevant site-channel distances. Our findings show that the approximation error is generally small and exhibits an interesting nonlinear and non-monotonic behavior where it vanishes for very low distances and is insignificant at intermediary distances. Furthermore, we give expressions for the reduced model’s reaction rates and suggest that our approach may be used to directly compute effective fusion rates for assessing the validity of a fusion model, thereby circumventing expensive simulations.

Description: This thesis addresses the problem of synthetic-to-real image refinement applied to tilt series of cryogenic electron micrographs. It explores the possibility of improving the realism of synthesized micrographs using generative adversarial networks, which could help to improve the automatic segmentation of cellular structures based on deep learning methods. For image refinement, three image-to-image translation networks were used to transfer the appearance of real micrographs to synthetic micrographs while preserving their original content, including the location and shape of particles. The first model, called SimGAN, was unable to produce any meaningful refinement. Instead, the content of the synthetic micrographs was corrupted by the addition of extensive noise, making SimGAN unsuitable for the problem of this thesis. As a result, CycleGAN was introduced and its refinement of synthetic micrographs matches the appearance of real micrographs very well. However, structural changes in the position and shape of particles were observed after translation. To avoid this behavior, CUT was used as a third model on an exploratory basis but its performance was inferior to that of CycleGAN. In conclusion, CycleGAN proved to be the most promising image-to-image translation model for the images presented, although it does not solve the main problem of this thesis. In order to do so, further modifications, such as the addition of a structural constraint during translation, are required.

Description: A Balancing Domain Decomposition by Constraints (BDDC) preconditioner is constructed and analyzed for the solution of hybrid Discontinuous Galerkin discretizations of reaction-diffusion systems of ordinary and partial differential equations arising in cardiac cell-by-cell models. The latter are different from the classical Bidomain and Monodomain cardiac models based on homogenized descriptions of the cardiac tissue at the macroscopic level, and therefore they allow the representation of individual cardiac cells, cell aggregates, damaged tissues and nonuniform distributions of ion channels on the cell membrane. The resulting discrete cell-by-cell models have discontinuous global solutions across the cell boundaries, hence the proposed BDDC preconditioner is based on appropriate dual and primal spaces with additional constraints which transfer information between cells (subdomains) without influencing the overall discontinuity of the global solution. A scalable convergence rate bound is proved for the resulting BDDC cell-by-cell preconditioned operator, while numerical tests validate this bound and investigate its dependence on the discretization parameters.

Description: The cardiac extracellular-membrane-intracellular (EMI) model enables the precise geometrical representation and resolution of aggregates of individual myocytes. As a result, it not only yields more accurate simulations of cardiac excitation compared to homogenized models but also presents the challenge of solving much larger problems. In this paper, we introduce recent advancements in three key areas: (i) the creation of artificial, yet realistic grids, (ii) efficient higher-order time stepping achieved by combining low-overhead spatial adaptivity on the algebraic level with progressive spectral deferred correction methods, and (iii) substructuring domain decomposition preconditioners tailored to address the complexities of heterogeneous problem structures. The efficiency gains of these proposed methods are demonstrated through numerical results on cardiac meshes of different sizes.

Description: A depinning transition is observed in a variety of contexts when a certain threshold force must be applied to drive a system out of an immobile state. A well-studied example is the depinning of colloidal particles from a corrugated landscape, whereas its active-matter analogue has remained unexplored. We discuss how active noise due to self-propulsion impacts the nature of the transition: it causes a change of the critical exponent from 1/2 for quickly reorienting particles to 3/2 for slowly reorienting ones. In between these analytically tractable limits, the drift velocity exhibits a superexponential behavior as is corroborated by high-precision data. Giant diffusion phenomena occur in the two different regimes. Our predictions appear amenable to experimental tests, lay foundations for insight into the depinning of collective variables in active matter, and are relevant for any system with a saddle-node bifurcation in the presence of a bounded noise.

Description: The reaction-diffusion master equation (RDME) is a lattice-based stochastic model for spatially resolved cellular processes. It is often interpreted as an approximation to spatially continuous reaction-diffusion models, which, in the limit of an infinitely large population, may be described by means of reaction-diffusion partial differential equations. Analyzing and understanding the relation between different mathematical models for reaction-diffusion dynamics is a research topic of steady interest. In this work, we explore a route to the hydrodynamic limit of the RDME which uses gradient structures. Specifically, we elaborate on a method introduced in [J. Maas and A. Mielke, J. Stat. Phys., 181 (2020), pp. 2257–2303] in the context of well-mixed reaction networks by showing that, once it is complemented with an appropriate limit procedure, it can be applied to spatially extended systems with diffusion. Under the assumption of detailed balance, we write down a gradient structure for the RDME and use the method in order to produce a gradient structure for its hydrodynamic limit, namely, for the corresponding RDPDE.

Description: This theoretical study concerns a pH oscillator based on the urea-urease reaction confined to giant lipid vesicles. Under suitable conditions, differential transport of urea and hydrogen ion across the unilamellar vesicle membrane periodically resets the pH clock that switches the system from acid to basic, resulting in self-sustained oscillations. We analyse the structure of the phase flow and of the limit cycle, which controls the dynamics for giant vesicles and dominates the pronouncedly stochastic oscillations in small vesicles of submicrometer size. To this end, we derive reduced models, which are amenable to analytic treatments that are complemented by numerical solutions, and obtain the period and amplitude of the oscillations as well as the parameter domain, where oscillatory behavior persists. We show that the accuracy of these predictions is highly sensitive to the employed reduction scheme. In particular, we suggest an accurate two-variable model and show its equivalence to a three-variable model that admits an interpretation in terms of a chemical reaction network. The faithful modeling of a single pH oscillator appears crucial for rationalizing experiments and understanding communication of vesicles and synchronization of rhythms.

Description: In this letter we present a stochastic dynamic model which can explain economic cycles. We show that the macroscopic description yields a complex dynamical landscape consisting of multiple stable fixed points, each corresponding to a split of the population into a large low and a small high income group. The stochastic fluctuations induce switching between the resulting metastable states, and excitation oscillations just below a deterministic bifurcation. The shocks are caused by the decisions of a few agents who have a disproportionate influence over the macroscopic state of the economy due to the unequal distribution of wealth among the population. The fluctuations have a long-term effect on the growth of economic output and lead to business cycle oscillations exhibiting coherence resonance, where the correlation time is controlled by the population size which is inversely proportional to the noise intensity.

Description: Temperature-based time of death estimation (TTDE) using simulation methods such as the finite element (FE) method promises higher accuracy and broader applicability in nonstandard cooling scenarios than established phenomenological methods. Their accuracy depends crucially on the simulation model to capture the actual situation. The model fidelity in turn hinges on the representation of the corpse’s anatomy in form of computational meshes as well as on the thermodynamic parameters. While inaccuracies in anatomy representation due to coarse mesh resolution are known to have a minor impact on the estimated time of death, the sensitivity with respect to larger differences in the anatomy has so far not been studied. We assess this sensitivity by comparing four independently generated and vastly different anatomical models in terms of the estimated time of death in an identical cooling scenario. In order to isolate the impact of shape variation, the models are scaled to a reference size, and the possible impact of measurement location variation is excluded explicitly, which gives a lower bound on the impact of anatomy on the estimated time of death.

Description: Extracting the kinetic properties of a system whose dynamics depend on the pH of the environment with which it exchanges energy and atoms requires sampling the Grand Canonical Ensemble. As an alternative, we present a novel strategy that requires simulating only the most recurrent Canonical Ensembles that compose the Grand Canonical Ensemble. The simulations are used to estimate the Gran Canonical distribution for a specific pH value by reweighting and to construct the transition rate matrix by discretizing the Fokker-Planck equation by Square Root Approximation and robust Perron Cluster Cluster Analysis. As an application, we have studied the tripeptide Ala-Asp-Ala.

Description: At chemical synapses, an arriving electric signal induces the fusion of vesicles with the presynaptic membrane, thereby releasing neurotransmitters into the synaptic cleft. After a fusion event, both the release site and the vesicle undergo a recovery process before becoming available for reuse again. Of central interest is the question which of the two restoration steps acts as the limiting factor during neurotrans-mission under high-frequency sustained stimulation. In order to investigate this question, we introduce a novel non-linear reaction network which involves explicit recovery steps for both the vesicles and the release sites, and includes the induced time-dependent output current. The associated reaction dynamics are formulated by means of ordinary differential equations (ODEs), as well as via the associated stochastic jump process. While the stochastic jump model describes a single release site, the average over many release sites is close to the ODE solution and shares its periodic structure. The reason for this can be traced back to the insight that recovery dynamics of vesicles and release sites are statistically almost independent. A sensitivity analysis on the recovery rates based on the ODE formulation reveals that neither the vesicle nor the release site recovery step can be identified as the essential rate-limiting step but that the rate- limiting feature changes over the course of stimulation. Under sustained stimulation the dynamics given by the ODEs exhibit transient dynamics leading from an initial depression of the postsynaptic response to an asymptotic periodic orbit, while the individual trajectories of the stochastic jump model lack the oscillatory behavior an asymptotic periodicity of the ODE-solution.

Description: We consider time-continuous Markovian discrete-state dynamics on random networks of interacting agents and study the large population limit. The dynamics are projected onto low-dimensional collective variables given by the shares of each discrete state in the system, or in certain subsystems, and general conditions for the convergence of the collective variable dynamics to a mean-field ordinary differential equation are proved. We discuss the convergence to this mean-field limit for a continuous-time noisy version of the so-called "voter model" on Erdős-Rényi random graphs, on the stochastic block model, as well as on random regular graphs. Moreover, a heterogeneous population of agents is studied. For each of these types of interaction networks, we specify the convergence conditions in dependency on the corresponding model parameters.

Description: The chemical diffusion master equation (CDME) describes the probabilistic dynamics of reaction--diffusion systems at the molecular level [del Razo et al., Lett. Math. Phys. 112:49, 2022]; it can be considered the master equation for reaction--diffusion processes. The CDME consists of an infinite ordered family of Fokker--Planck equations, where each level of the ordered family corresponds to a certain number of particles and each particle represents a molecule. The equations at each level describe the spatial diffusion of the corresponding set of particles, and they are coupled to each other via reaction operators --linear operators representing chemical reactions. These operators change the number of particles in the system, and thus transport probability between different levels in the family. In this work, we present three approaches to formulate the CDME and show the relations between them. We further deduce the non-trivial combinatorial factors contained in the reaction operators, and we elucidate the relation to the original formulation of the CDME, which is based on creation and annihilation operators acting on many-particle probability density functions. Finally we discuss applications to multiscale simulations of biochemical systems among other future prospects.

Description: With the emergence of ”Big Data” the analysis of large data sets of high-dimensional energy time series in network structures have become feasible. However, building large-scale data-driven and computationally efficient models to accurately capture the underlying spatial and temporal dynamics and forecast the multivariate time series data remains a great challenge. Additional constraints make the problem more challenging to solve with conventional methods. For example, to ensure the security of supply, energy networks require the demand and supply to be balanced. This paper introduces a novel large-scale Hierarchical Network Regression model with Relaxed Balance constraint (HNR-RB) to investigate the network dynamics and predict multistep-ahead flows in the natural gas transmission network, where the total in- and out-flows of the network have to be balanced over a period of time. We concurrently address three main challenges: high dimensionality of networks with more than 100 nodes, unknown network dynamics, and constraint of balanced supply and demand in the network. The effectiveness of the proposed model is demonstrated through a real-world case study of forecasting demand and supply in a large-scale natural gas transmission network. The results demonstrate that HNR-RB outperforms alternative models for short- and mid-term horizons.

Description: We develop a functional framework suitable for the treatment of partial differential equations and variational problems posed on evolving families of Banach spaces. We propose a definition for the weak time derivative which does not rely on the availability of an inner product or Hilbertian structure and explore conditions under which the spaces of weakly differentiable functions (with values in an evolving Banach space) relate to the classical Sobolev--Bochner spaces. An Aubin--Lions compactness result in this setting is also proved. We then analyse several concrete examples of function spaces over time-evolving spatial domains and hypersurfaces for which we explicitly provide the definition of the time derivative and verify isomorphism properties with the aforementioned Sobolev--Bochner spaces. We conclude with the formulation and proof of well posedness for a class of nonlinear monotone problems on an abstract evolving space (generalising in particular the evolutionary p-Laplace equation on a moving domain or surface) and identify some additional evolutionary problems that can be appropriately formulated with the abstract setting developed in this work.

Description: Presolving has become an essential component of modern mixed integer program (MIP) solvers, both in terms of computational performance and numerical robustness. In this paper, we present PaPILO, a new C++ header-only library that provides a large set of presolving routines for MIP and linear programming problems from the literature. The creation of PaPILO was motivated by the current lack of (a) solver-independent implementations that (b) exploit parallel hardware and (c) support multiprecision arithmetic. Traditionally, presolving is designed to be fast. Whenever necessary, its low computational overhead is usually achieved by strict working limits. PaPILO’s parallelization framework aims at reducing the computational overhead also when presolving is executed more aggressively or is applied to large-scale problems. To rule out conflicts between parallel presolve reductions, PaPILO uses a transaction-based design. This helps to avoid both the memory-intensive allocation of multiple copies of the problem and special synchronization between presolvers. Additionally, the use of Intel’s Threading Building Blocks library aids PaPILO in efficiently exploiting recursive parallelism within expensive presolving routines, such as probing, dominated columns, or constraint sparsification. We provide an overview of PaPILO’s capabilities and insights into important design choices.

Description: Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations.

Description: Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a $4\%$ decrease in solve time, and an $8\%$ decrease in number of nodes over affected instances of MIPLIB 2017.

Description: Digital communication has made the public discourse considerably more complex, and new actors and strategies have emerged as a result of this seismic shift. Aside from the often-studied interactions among individuals during opinion formation, which have been facilitated on a large scale by social media platforms, the changing role of traditional media and the emerging role of "influencers" are not well understood, and the implications of their engagement strategies arising from the incentive structure of the attention economy even less so. Here we propose a novel opinion dynamics model that accounts for these different roles, namely that media and influencers change their own positions on slower time scales than individuals, while influencers dynamically gain and lose followers. Numerical simulations show the importance of their relative influence in creating qualitatively different opinion formation dynamics: with influencers, fragmented but short-lived clusters emerge, which are then counteracted by more stable media positions. Mean-field approximations by partial differential equations reproduce this dynamic. Based on the mean-field model, we study how strategies of influencers to gain more followers can influence the overall opinion distribution. We show that moving towards extreme positions can be a beneficial strategy for influencers to gain followers. Finally, we demonstrate that optimal control strategies allow other influencers or media to counteract such attempts and prevent further fragmentation of the opinion landscape. Our modelling framework contributes to better understanding the different roles and strategies in the increasingly complex information ecosystem and their impact on public opinion formation.

Description: Due to the coexistence of different gases in underground storage, this work explores the interface stability's impact on energy storage, specifically during the injection and withdrawal of gases such as hydrogen and natural gas. A new approach of combing simulation and time series analysis is used to accurately predict instability modes in energy systems. Our simulation is based on the 2D Euler equations, solved using a second-order finite volume method with a staggered grid. The solution is validated by comparing them to experimental data and analytical solutions, accurately predicting the instability's behavior. We use time series analysis and state-of-the-art regime-switching methods to identify critical features of the interface dynamics, providing crucial insights into system optimization and design.

Description: The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.

Description: In this repository are all files necessary to run the agent-based model of the paper "Insights into drivers of mobility and cultural dynamics of African hunter–gatherers over the past 120 000 years", Royal Society Open Science, 10(11), 2023.

Description: This repository contains the Julia code accompanying the paper "Modelling opinion dynamics under the impact of influencer and media strategies", Scientific Reports, Vol.13, p. 19375, 2023.

Description: Humans have a unique capacity to innovate, transmit and rely on complex, cumulative culture for survival. While an important body of work has attempted to explore the role of changes in the size and interconnectedness of populations in determining the persistence, diversity and complexity of material culture, results have achieved limited success in explaining the emergence and spatial distribution of cumulative culture over our evolutionary trajectory. Here, we develop a spatio-temporally explicit agent-based model to explore the role of environmentally driven changes in the population dynamics of hunter–gatherer communities in allowing the development, transmission and accumulation of complex culture. By modelling separately demography- and mobility-driven changes in interaction networks, we can assess the extent to which cultural change is driven by different types of population dynamics. We create and validate our model using empirical data from Central Africa spanning 120 000 years. We find that populations would have been able to maintain diverse and elaborate cultural repertoires despite abrupt environmental changes and demographic collapses by preventing isolation through mobility. However, we also reveal that the function of cultural features was also an essential determinant of the effects of environmental or demographic changes on their dynamics. Our work can therefore offer important insights into the role of a foraging lifestyle on the evolution of cumulative culture.

Description: In recent years, European gas transport has been affected by major disruptive events like political issues such as, most recently, the Russian war on Ukraine. To incorporate the impacts of such events into decision-making during the energy transition, more complex models for gas network analysis are required. However, the limited availability of consistent data presents a significant obstacle in this endeavor. We use a mathematical-modeling-based scenario generator to deal with this obstacle. The scenario generator consists of capacitated network flow models representing the gas network at different aggregation levels. In this study, we present the coarse-to-fine approach utilized in this scenario generator.

Description: Most recently, the European energy system has undergone a fundamental transformation to meet decarbonization targets without compromising the security of the energy supply. The transition involves several energy-generating and consuming sectors emphasizing sector coupling. The increase in the share of renewable energy sources has revealed the need for flexibility in supporting the electricity grid to cope with the resulting high degree of uncertainty. The new technologies accompanying the energy system transition and the recent political crisis in Europe threatening the security of the energy supply have invalidated the experience from the past by drastically changing the conventional scenarios. Hence, supporting strategic planning tools with detailed operational energy network models with appropriate mathematical precision has become more important than ever to understand the impacts of these disruptive changes. In this paper, we propose a workflow to investigate optimal energy transition pathways considering sector coupling. This workflow involves an integrated operational analysis of the electricity market, its transmission grid, and the gas grid in high spatio-temporal resolution. Thus, the workflow enables decision-makers to evaluate the reliability of high-level models even in case of disruptive events. We demonstrate the capabilities of the proposed workflow using results from a pan-European case study. The case study, spanning 2020-2050, illustrates that feasible potential pathways to carbon neutrality are heavily influenced by political and technological constraints. Through integrated operational analysis, we identify scenarios where strategic decisions become costly or infeasible given the existing electricity and gas networks.

Description: Modern potential energy surfaces have shifted attention to molecular simulations of chemical reactions. While various methods can estimate rate constants for conformational transitions in molecular dynamics simulations, their applicability to studying chemical reactions remains uncertain due to the high and sharp energy barriers and complex reaction coordinates involved. This study focuses on the thermal cis-trans isomerization in retinal, employing molecular simulations and comparing rate constant estimates based on one-dimensional rate theories with those based on sampling transitions and grid-based models for low-dimensional collective variable spaces. Even though each individual method to estimate the rate passes its quality tests, the rate constant estimates exhibit disparities of up to four orders of magnitude. Rate constant estimates based on one-dimensional reaction coordinates prove challenging to converge, even if the reaction coordinate is optimized. However, consistent estimates of the rate constant are achieved by sampling transitions and by multi-dimensional grid-based models.

Description: It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization (QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate- scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights regarding current benchmark instances and modeling.

Description: Polymorphism is the property exhibited by many inorganic and organic molecules to crystallize in more than one crystal structure. There is a strong need for understanding the influencing factors on polymorphism, as it is responsible for differences in many physicochemical properties such as stability and solubility. Nearly 80 % of marketed drugs exhibit polymorphism. In this work, we took the model system of paracetamol to investigate the influence of solvent choice on its polymorphism. Different methods were developed and employed to understand the influence of small organic solvents on the crystallization of paracetamol. Non-equilibrium molecular dynamics simulations with periodic simulated annealing were used as a tool to probe the nature of precursors of the metastable intermediates occurring in the crystallization process. Using this method, it was found that the structures of the building blocks of crystals of paracetamol is governed by solvent-solute interactions. In situ Raman spectroscopy was used with a custom-made acoustic levitator to follow crystallization. This set-up is a reliable method for investigating solvent influence, attenuating heterogeneous nucleation and stabilizing other environmental factors. It was established that as a solvent, ethanol is much stronger than methanol in its effect of driving paracetamol solutions to their crystal form. The time-resolved Raman spectroscopy crystallization data was processed using a newly developed objective function based non-negative matrix factorization method (NMF). An orthogonal time-lapse photography was used in conjunction with NMF to get unique and accurate factors that pertain to the spectra and concentrations of different moieties of paracetamol crystallization existing as latent components in the untreated data.

Description: We study a functional autoregressive model for high-frequency time series. We approach the estimation of the proposed model using a Mixed Integer Optimisation method. The proposed model captures serial dependence in the functional time series by including high-dimensional curves. We illustrate our methodology on large-scale natural gas network data. Our model provides more accurate day-ahead hourly out-of-sample forecast of the gas in and out-flows compared to alternative prediction models.

Description: In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: Constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.

Description: Energy systems are complex networks consisting of various interconnected components. Accurate energy demand and supply forecasts are crucial for efficient system operation and decision-making. However, high-dimensional data, complex network structures, and dynamic changes and disruptions in energy networks pose significant challenges for forecasting models. To address this, we propose a hybrid approach for resilient forecasting of network time series (HRF-NTS) in the energy domain. Our approach combines mathematical optimization methods with state-of-the-art machine learning techniques to achieve accurate and robust forecasts for high-dimensional energy network time series. We incorporate an optimization framework to account for uncertainties and disruptive changes in the energy system. The effectiveness of the proposed approach is demonstrated through a case study of forecasting energy demand and supply in a complex, large-scale natural gas transmission network. The results show that the hybrid approach outperforms alternative prediction models in terms of accuracy and resilience to structural changes and disruptions, providing stable, multi-step ahead forecasts for different short to mid-term forecasting horizons.

Description: High-dimensional metastable molecular dynamics (MD) can often be characterised by a few features of the system, that is, collective variables (CVs). Thanks to the rapid advance in the area of machine learning and deep learning, various deep learning-based CV identification techniques have been developed in recent years, allowing accurate modelling and efficient simulation of complex molecular systems. In this paper, we look at two different categories of deep learning-based approaches for finding CVs, either by computing leading eigenfunctions of transfer operator associated to the underlying dynamics, or by learning an autoencoder via minimisation of reconstruction error. We present a concise overview of the mathematics behind these two approaches and conduct a comparative numerical study of these two approaches on illustrative examples.

Description: For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided.

Description: Nowadays railway networks are highly complex and often very fragile systems. A wide variety of individual operations that influence each other have to go hand in hand to end up with a smoothly and efficiently running system. Many of these operations suffer from uncertainty as trains could be delayed, the signaling system be disrupted or scheduled crews could be ill. Usually these opartions could be organized hierarchically from long term strategical decisions to real time decision management. Each stage in the hierarchy defines a different mathematical optimization problem, which is solved sequentially. At every stage the knowledge about preceding or succeeding planning stages may vary and also the interaction between two stages in this chain of problems may vary from almost no interaction to highly dependent situations. This paper deals with a topic that is an example for the latter case, namely the interaction between vehicle schedules, vehicle punctuality, and crew schedules. To reduce the number of potential rescheduling actions we developed a software tool in cooperation with our practical partner DB Fernverkehr AG (DBF) to predict a certain set of critical crew schedules. This tool evaluates, predicts, and determines "bottlenecks" in the crew schedule in the sense of potentially required rescheduling actions due to likely delays. The approach was tested on real life crew and train timetable data of DBF and can be regarded as the computation of key performance indicators, which is often desired. For our experiments we had access to the operated timetable and crew schedule of DBF for periods of two and six weeks in 2019.

Description: A generalized understanding of protein dynamics is an unsolved scientific problem, the solution of which is critical to the interpretation of the structure-function relationships that govern essential biological processes. Here, we approach this problem by constructing coarse-grained molecular potentials based on artificial neural networks and grounded in statistical mechanics. For training, we build a unique dataset of unbiased all-atom molecular dynamics simulations of approximately 9 ms for twelve different proteins with multiple secondary structure arrangements. The coarse-grained models are capable of accelerating the dynamics by more than three orders of magnitude while preserving the thermodynamics of the systems. Coarse-grained simulations identify relevant structural states in the ensemble with comparable energetics to the all-atom systems. Furthermore, we show that a single coarse-grained potential can integrate all twelve proteins and can capture experimental structural features of mutated proteins. These results indicate that machine learning coarse-grained potentials could provide a feasible approach to simulate and understand protein dynamics.

Description: Machine-learned coarse-grained (CG) models have the potential for simulating large molecular complexes beyond what is possible with atomistic molecular dynamics. However, training accurate CG models remains a challenge. A widely used methodology for learning bottom-up CG force fields maps forces from all-atom molecular dynamics to the CG representation and matches them with a CG force field on average. We show that there is flexibility in how to map all-atom forces to the CG representation and that the most commonly used mapping methods are statistically inefficient and potentially even incorrect in the presence of constraints in the all-atom simulation. We define an optimization statement for force mappings and demonstrate that substantially improved CG force fields can be learned from the same simulation data when using optimized force maps. The method is demonstrated on the miniproteins chignolin and tryptophan cage and published as open-source code.

Description: The successful recent application of machine learning methods to scientific problems includes the learning of flexible and accurate atomic-level force-fields for materials and biomolecules from quantum chemical data. In parallel, the machine learning of force-fields at coarser resolutions is rapidly gaining relevance as an efficient way to represent the higher-body interactions needed in coarse-grained force-fields to compensate for the omitted degrees of freedom. Coarse-grained models are important for the study of systems at time and length scales exceeding those of atomistic simulations. However, the development of transferable coarse-grained models via machine learning still presents significant challenges. Here, we discuss recent developments in this field and current efforts to address the remaining challenges.

Description: We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constraints. The library builds upon MathOptInterface, thus leveraging the rich ecosystem of solvers and composing well with modeling languages like JuMP. DiffOpt offers both forward and reverse differentiation modes, enabling multiple use cases from hyperparameter optimization to backpropagation and sensitivity analysis, bridging constrained optimization with end-to-end differentiable programming. DiffOpt is built on two known rules for differentiating quadratic programming and conic programming standard forms. However, thanks to its ability to differentiate through model transformations, the user is not limited to these forms and can differentiate with respect to the parameters of any model that can be reformulated into these standard forms. This notably includes programs mixing affine conic constraints and convex quadratic constraints or objective function.

Description: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.

Description: The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.

Description: The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension , where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, the formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures.

Description: A major step in the planning process of passenger railway operators is the assignment of rolling stock, i.e., train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the Composition model and the Hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in a rolling stock scheduling setting similar to that of NS, which we show to be strongly NP-hard, and propose different variants of the Hypergraph model to tune the model to the NS setting. We prove that, in this setting, the linear programming bounds of both models are equally strong as long as a Hypergraph model variant is chosen that is sufficiently expressive. However, through a numerical evaluation on NS instances, we show that the Composition model is generally more compact in practice and can find optimal solutions in the shortest running time.

Description: In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: Constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.

Description: The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation’s feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Borndörfer et al., 2016] on a test set of real world instances.

Description: The recent COVID-19 pandemic has thrown the importance of accurately forecasting contagion dynamics and learning infection parameters into sharp focus. At the same time, effective policy-making requires knowledge of the uncertainty on such predictions, in order, for instance, to be able to ready hospitals and intensive care units for a worst-case scenario without needlessly wasting resources. In this work, we apply a novel and powerful computational method to the problem of learning probability densities on contagion parameters and providing uncertainty quantification for pandemic projections. Using a neural network, we calibrate an ODE model to data of the spread of COVID-19 in Berlin in 2020, achieving both a significantly more accurate calibration and prediction than Markov-Chain Monte Carlo (MCMC)-based sampling schemes. The uncertainties on our predictions provide meaningful confidence intervals e.g. on infection figures and hospitalisation rates, while training and running the neural scheme takes minutes where MCMC takes hours. We show convergence of our method to the true posterior on a simplified SIR model of epidemics, and also demonstrate our method's learning capabilities on a reduced dataset, where a complex model is learned from a small number of compartments for which data is available.

Description: We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.

Description: We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse- quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.

Description: We previously reported the successful design, synthesis and testing of the prototype opioid painkiller NFEPP that does not elicit adverse side effects. The design process of NFEPP was based on mathematical modelling of extracellular interactions between G-protein coupled receptors (GPCRs) and ligands, recognizing that GPCRs function differently under pathological versus healthy conditions. We now present an additional and novel stochastic model of GPCR function that includes intracellular dissociation of G-protein subunits and modulation of plasma membrane calcium channels and their dependence on parameters of inflamed and healthy tissue (pH, radicals). The model is validated against in vitro experimental data for the ligands NFEPP and fentanyl at different pH values and radical concentrations. We observe markedly reduced binding affinity and calcium channel inhibition for NFEPP at normal pH compared to lower pH, in contrast to the effect of fentanyl. For increasing radical concentrations, we find enhanced constitutive G-protein activation but reduced ligand binding affinity. Assessing the different effects, the results suggest that, compared to radicals, low pH is a more important determinant of overall GPCR function in an inflamed environment. Future drug design efforts should take this into account.

Description: In our previous studies, a new opioid (NFEPP) was developed to only selectively bind to the 𝜇-opoid receptor (MOR) in inflamed tissue and thus avoid the severe side effects of fentanyl. We know that NFEPP has a reduced binding affinity to MOR in healthy tissue. Inspired by the modelling and simulations performed by Sutcliffe et al., we present our own results of coarse-grained molecular dynamics simulations of fentanyl and NFEPP with regards to their interaction with the 𝜇-opioid receptor embedded within the lipid cell membrane. For technical reasons, we have slightly modified Sutcliffe’s parametrisation of opioids. The pH-dependent opioid simulations are of interest because while fentanyl is protonated at the physiological pH, NFEPP is deprotonated due to its lower pKa value than that of fentanyl. Here, we analyse for the first time whether pH changes have an effect on the dynamical behaviour of NFEPP when it is inside the cell membrane. Besides these changes, our analysis shows a possible alternative interaction of NFEPP at pH 7.4 outside the binding region of the MOR. The interaction potential of NFEPP with MOR is also depicted by analysing the provided statistical molecular dynamics simulations with the aid of an eigenvector analysis of a transition rate matrix. In our modelling, we see differences in the XY-diffusion profiles of NFEPP compared with fentanyl in the cell membrane.

Description: Opioids are essential pharmaceuticals due to their analgesic properties, however, lethal side effects, addiction, and opioid tolerance are extremely challenging. The development of novel molecules targeting the μ-opioid receptor (MOR) in inflamed, but not in healthy tissue, could significantly reduce these unwanted effects. Finding such novel molecules can be achieved by maximizing the binding affinity to the MOR at acidic pH while minimizing it at neutral pH, thus combining two conflicting objectives. Here, this multi-objective optimal affinity approach is presented, together with a virtual drug discovery pipeline for its practical implementation. When applied to finding pH-specific drug candidates, it combines protonation state-dependent structure and ligand preparation with high-throughput virtual screening. We employ this pipeline to characterize a set of MOR agonists identifying a morphine-like opioid derivative with higher predicted binding affinities to the MOR at low pH compared to neutral pH. Our results also confirm existing experimental evidence that NFEPP, a previously described fentanyl derivative with reduced side effects, and recently reported β-fluorofentanyls and -morphines show an increased specificity for the MOR at acidic pH when compared to fentanyl and morphine. We further applied our approach to screen a 〉50K ligand library identifying novel molecules with pH-specific predicted binding affinities to the MOR. The presented differential docking pipeline can be applied to perform multi-objective affinity optimization to identify safer and more specific drug candidates at large scale.

Description: Rolling stock is one of the major assets for a railway transportation company. Hence, their utilization should be as efficiently and effectively as possible. Railway undertakings are facing rolling stock scheduling challenges in different forms - from rather idealized weekly strategic problems to very concrete operational ones. Thus, a vast of optimization models with different features and objectives exist. Thorlacius et al. (2015) provides a comprehensive and valuable collection on technical requirements, models, and methods considered in the scientific literature. We contribute with an update including recent works. The main focus of the paper is to present a classification and elaboration of the major features which our solver R-OPT is able to handle. Moreover, the basic optimization model and algorithmic ingredients of R-OPT are discussed. Finally, we present computational results for a cargo application at SBB CARGO AG and other railway undertakings for passenger traffic in Europe to show the capabilities of R-OPT.

Description: We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.

Description: We propose a generic spatiotemporal framework to analyze manifold-valued measurements, which allows for employing an intrinsic and computationally efficient Riemannian hierarchical model. Particularly, utilizing regression, we represent discrete trajectories in a Riemannian manifold by composite Bézier splines, propose a natural metric induced by the Sasaki metric to compare the trajectories, and estimate average trajectories as group-wise trends. We evaluate our framework in comparison to state-of-the-art methods within qualitative and quantitative experiments on hurricane tracks. Notably, our results demonstrate the superiority of spline-based approaches for an intensity classification of the tracks.

Description: The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver.

Description: Docking is a fundamental problem in computational biology and drug discovery that seeks to predict a ligand’s binding mode and affinity to a target protein. However, the large search space size and the complexity of the underlying physical interactions make docking a challenging task. Here, we review a docking method, based on the ant colony optimization algorithm, that ranks a set of candidate ligands by solving a minimization problem for each ligand individually. In addition, we propose an augmented version that takes into account all energy functions collectively, allowing only one minimization problem to be solved. The results show that our modification outperforms in accuracy and efficiency.