Library

Description: While graph covering is a fundamental and well-studied problem, this field lacks a broad and unified literature review. The holistic overview of graph covering given in this article attempts to close this gap. The focus lies on a characterization and classification of the different problems discussed in the literature. In addition, notable results and common approaches are also included. Whenever appropriate, this review extends to the corresponding partitioning problems.

Description: We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.

Description: We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.

Description: The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis.

Description: Optimizing the transient control of gas networks is a highly challenging task. The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas transport. In this paper, we present the latest improvements of our ongoing work to solve this problem for real-world, large-scale problem instances: By adjusting our mixed-integer non-linear programming model regarding the gas compression capabilities in the network, we reflect the technical limits of the underlying units more accurately while maintaining a similar overall model size. In addition, we introduce a new algorithmic approach that is based on splitting the complexity of the problem by first finding assignments for discrete variables and then determining the continuous variables as locally optimal solution of the corresponding non-linear program. For the first task, we design multiple different heuristics based on concepts for general time-expanded optimization problems that find solutions by solving a sequence of sub-problems defined on reduced time horizons. To demonstrate the competitiveness of our approach, we test our algorithm on particularly challenging historic demand scenarios. The results show that high-quality solutions are obtained reliably within short solving times, making the algorithm well-suited to be applied at the core of time-critical industrial applications.

Description: Public transportation networks are typically operated with a periodic timetable. The periodic event scheduling problem (PESP) is the standard mathematical modeling tool for periodic timetabling. PESP is a computationally very challenging problem: For example, solving the instances of the benchmarking library PESPlib to optimality seems out of reach. Since PESP can be solved in linear time on trees, and the treewidth is a rather small graph parameter in the networks of the PESPlib, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth, or even better, fixed-parameter tractable algorithms. 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. Moreover, we show W[1]-hardness of the general feasibility problem with respect to treewidth, which means that we can most likely only accomplish pseudo-polynomial-time algorithms on input networks with bounded tree- or branchwidth. We present two such algorithms based on dynamic programming. 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: Cut selection is a subroutine used in all modern mixed-integer linear programming solvers with the goal of selecting a subset of generated cuts that induce optimal solver performance. These solvers have millions of parameter combinations, and so are excellent candidates for parameter tuning. Cut selection scoring rules are usually weighted sums of different measurements, where the weights are parameters. We present a parametric family of mixed-integer linear programs together with infinitely many family-wide valid cuts. Some of these cuts can induce integer optimal solutions directly after being applied, while others fail to do so even if an infinite amount are applied. We show for a specific cut selection rule, that any finite grid search of the parameter space will always miss all parameter values, which select integer optimal inducing cuts in an infinite amount of our problems. We propose a variation on the design of existing graph convolutional neural networks, adapting them to learn cut selection rule parameters. We present a reinforcement learning framework for selecting cuts, and train our design using said framework over MIPLIB 2017. Our framework and design show that adaptive cut selection does substantially improve performance over a diverse set of instances, but that finding a single function describing such a rule is difficult. Code for reproducing all experiments is available at https://github.com/Opt-Mucca/Adaptive-Cutsel-MILP.

Description: Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improves the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58%.

Description: It is well known as the Kelvin-Helmholtz instability (KHI) that an interface of tangential velocity discontinuity is necessarily unstable, regardless of the velocity difference's strength. However, the KHI is suppressed for shallow water flows if the Froude number, defined by the ratio of the velocity difference to the gravity wave's speed, is sufficiently large. In this investigation, we examine the effect of the depth difference of two fluid layers on the KHI. The depth difference enhances instability. Given the Froude number in the instability range, the growth rate sensitively depends on the depth ratio and increases monotonically with the depth ratio difference from unity. The critical value of the Froude number for stabilization varies with the depth ratio and attains the minimum value √8 for equal depth. This behavior is verified by asymptotic analysis.

Description: The European energy system has been through a fundamental transformation since the Paris Agreement to reduce greenhouse gas emissions. 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 the electri city grid. Thus, holistic planning of pathways towards decarbonized energy systems also involves assessing the gas infrastructure to provide such a flexibility and support for the security of supply. In this paper, we propose a workflow to investigate such 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. In a case study on a pan-European scale between 2020-2050, we show that carbon neutrality can be reached within feasible additional costs and in time. However, the manifestation of the potential pathways strongly depends on political and technological constraints. Sector coupling acts as an enabler of cross-border cooperation to achieve both, decarbonization and security of supply.

Description: Biological armors derive their mechanical integrity in part from their geometric architectures, often involving tessellations: individual structural elements tiled together to form surface shells. The carapace of boxfish, for example, is comprised of mineralized polygonal plates, called scutes, arranged in a complex geometric pattern and nearly completely encasing the body. In contrast to artificial armors, the boxfish exoskeleton grows with the fish; the relationship between the tessellation and the gross structure of the armor is therefore critical to sustained protection throughout growth. To clarify whether or how the boxfish tessellation is maintained or altered with age, we quantify architectural aspects of the tessellated carapace of the longhorn cowfish Lactoria cornuta through ontogeny (across nearly an order of magnitude in standard length) and in a high-throughput fashion, using high-resolution microCT data and segmentation algorithms to characterize the hundreds of scutes that cover each individual. We show that carapace growth is canalized with little variability across individuals: rather than continually adding scutes to enlarge the carapace surface, the number of scutes is surprisingly constant, with scutes increasing in volume, thickness, and especially width with age. As cowfish and their scutes grow, scutes become comparatively thinner, with the scutes at the edges (weak points in a boxy architecture) being some of the thickest and most reinforced in younger animals and thinning most slowly across ontogeny. In contrast, smaller scutes with more variable curvature were found in the limited areas of more complex topology (e.g. around fin insertions, mouth, and anus). Measurements of Gaussian and mean curvature illustrate that cowfish are essentially tessellated boxes throughout life: predominantly zero curvature surfaces comprised of mostly flat scutes, and with scutes with sharp bends used sparingly to form box edges. Since growth of a curved, tiled surface with a fixed number of tiles would require tile restructuring to accommodate the surface’s changing radius of curvature, our results therefore illustrate a previously unappreciated advantage of the odd boxfish morphology: by having predominantly flat surfaces, it is the box-like body form that in fact permits a relatively straightforward growth system of this tessellated architecture (i.e. where material is added to scute edges). Our characterization of the ontogeny and maintenance of the carapace tessellation provides insights into the potentially conflicting mechanical, geometric and developmental constraints of this species, but also perspectives into natural strategies for constructing mutable tiled architectures.

Description: The electric conductivity of cardiac tissue determines excitation propagation and is important for quantifying ischemia and scar tissue and for building personalized models. Estimating conductivity distributions from endocardial mapping data is a challenging inverse problem due to the computational complexity of the monodomain equation, which describes the cardiac excitation. For computing a maximum posterior estimate, we investigate different optimization approaches based on adjoint gradient computation: steepest descent, limited memory BFGS, and recursive multilevel trust region methods, which are using mesh hierarchies or heterogeneous model hierarchies. We compare overall performance, asymptotic convergence rate, and pre-asymptotic progress on selected examples in order to assess the benefit of our multifidelity acceleration.

Description: Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance 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.The converted BQOP is much simpler than the original QAP tai256c and it also inherits some of the symmetry properties. However, it is still very difficult to solve. We present an efficient branch and bound method for improving the lower bound effectively. A new lower bound with 1.36% gap is also provided.

Description: The combination of Monte Carlo methods and deep learning has recently led to efficient algorithms for solving partial differential equations (PDEs) in high dimensions. Related learning problems are often stated as variational formulations based on associated stochastic differential equations (SDEs), which allow the minimization of corresponding losses using gradient-based optimization methods. In respective numerical implementations it is therefore crucial to rely on adequate gradient estimators that exhibit low variance in order to reach convergence accurately and swiftly. In this article, we rigorously investigate corresponding numerical aspects that appear in the context of linear Kolmogorov PDEs. In particular, we systematically compare existing deep learning approaches and provide theoretical explanations for their performances. Subsequently, we suggest novel methods that can be shown to be more robust both theoretically and numerically, leading to substantial performance improvements.

Description: We establish a connection between stochastic optimal control and generative models based on stochastic differential equations (SDEs) such as recently developed diffusion probabilistic models. In particular, we derive a Hamilton-Jacobi-Bellman equation that governs the evolution of the log-densities of the underlying SDE marginals. This perspective allows to transfer methods from optimal control theory to generative modeling. First, we show that the evidence lower bound is a direct consequence of the well-known verification theorem from control theory. Further, we develop a novel diffusion-based method for sampling from unnormalized densities -- a problem frequently occurring in statistics and computational sciences.

Description: This study investigates the progress made in LP and MILP solver performance during the last two decades by comparing the solver software from the beginning of the millennium with the codes available today. On average, we found out that for solving LP/MILP, computer hardware got about 20 times faster, and the algorithms improved by a factor of about nine for LP and around 50 for MILP, which gives a total speed-up of about 180 and 1,000 times, respectively. However, these numbers have a very high variance and they considerably underestimate the progress made on the algorithmic side: many problem instances can nowadays be solved within seconds, which the old codes are not able to solve within any reasonable time.

Description: We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K4 and K5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K4 or K5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.

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

Description: Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Borndörfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances.

Description: OASIcs, Volume 106, ATMOS 2022, Complete Volume

Description: Extracting information about dynamical systems from models learned off simulation data has become an increasingly important research topic in the natural and engineering sciences. Modeling the Koopman operator semigroup has played a central role in this context. As the approximation quality of any such model critically depends on the basis set, recent work has focused on deriving data-efficient representations of the Koopman operator in low-rank tensor formats, enabling the use of powerful model classes while avoiding over-fitting. On the other hand, detailed information about the system at hand can be extracted from models for the infinitesimal generator, also called Kolmogorov backward operator for stochastic differential equations. In this work, we present a data-driven method to efficiently approximate the generator using the tensor train (TT) format. The centerpiece of the method is a TT representation of the tensor of generator evaluations at all data sites. We analyze consistency and complexity of the method, present extensions to practically relevant settings, and demonstrate its applicability to benchmark numerical examples.

Description: Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts.

Description: We consider autocovariance operators of a stationary stochastic process on a Polish space that is embedded into a reproducing kernel Hilbert space. We investigate how empirical estimates of these operators converge along realizations of the process under various conditions. In particular, we examine ergodic and strongly mixing processes and obtain several asymptotic results as well as finite sample error bounds. We provide applications of our theory in terms of consistency results for kernel PCA with dependent data and the conditional mean embedding of transition probabilities. Finally, we use our approach to examine the nonparametric estimation of Markov transition operators and highlight how our theory can give a consistency analysis for a large family of spectral analysis methods including kernel-based dynamic mode decomposition.

Description: This work addresses the problem of determining the number of components from sequential spectroscopic data analyzed by non-negative matrix factorization without separability assumption (SepFree NMF). These data are stored in a matrix M of dimension “measured times” versus “measured wavenumbers” and can be decomposed to obtain the spectral fingerprints of the states and their evolution over time. SepFree NMF assumes a memoryless (Markovian) process to underline the dynamics and decomposes M so that M=WH, with W representing the components’ fingerprints and H their kinetics. However, the rank of this decomposition (i.e., the number of physical states in the process) has to be guessed from pre-existing knowledge on the observed process. We propose a measure for determining the number of components with the computation of the minimal memory effect resulting from the decomposition; by quantifying how much the obtained factorization is deviating from the Markovian property, we are able to score factorizations of a different number of components. In this way, we estimate the number of different entities which contribute to the observed system, and we can extract kinetic information without knowing the characteristic spectra of the single components. This manuscript provides the mathematical background as well as an analysis of computer generated and experimental sequentially measured Raman spectra.

Description: We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. The symmetry gap is provably small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.

Description: In this paper, we consider the eigenvalue PDE problem of the infinitesimal generators of metastable diffusion processes. We propose a numerical algorithm based on training artificial neural networks for solving the leading eigenvalues and eigenfunctions of such high-dimensional eigenvalue problem. The algorithm is useful in understanding the dynamical behaviors of metastable processes on large timescales. We demonstrate the capability of our algorithm on a high-dimensional model problem, and on the simple molecular system alanine dipeptide.

Description: We propose new Markov Chain Monte Carlo algorithms to sample probability distributions on submanifolds, which generalize previous methods by allowing the use of set-valued maps in the proposal step of the MCMC algorithms. The motivation for this generalization is that the numerical solvers used to project proposed moves to the submanifold of interest may find several solutions. We show that the new algorithms indeed sample the target probability measure correctly, thanks to some carefully enforced reversibility property. We demonstrate the interest of the new MCMC algorithms on illustrative numerical examples.

Description: As a result of the legislation for gas markets introduced by the European Union in 2005, separate independent companies have to conduct the transport and trading of natural gas. The current gas market of Germany, which has a market value of more than 54 billion USD, consists of Transmission System Operators (TSO), network users, and traders. Traders can nominate a certain amount of gas anytime and anywhere in the network. Such unrestricted access for the traders, on the other hand, increase the uncertainty in the gas supply management. Some customers’ behaviors may cause abrupt structural changes in gas flow time series. In particular, it is a challenging task for the TSO operators to predict gas nominations 6 to 10 h-ahead. In our study, we aim to investigate the regime changes in time series of nominations to predict the 6 to 10 h-ahead of gas nominations.

Description: During the apparition of comet 67P/Churyumov-Gerasimenko (67P/C-G) solar irradiation causes varying rates for sublimation of volatile species from the cometary nucleus. Because sublimation processes take place close to the cometary surface, the relative abundance of volatiles in the coma and the ice composition are related to each other. To quantify this relation we assume a model for the expansion of a collisionless gas from the surface into the surrounding space. We use an inverse model approach to relate the in situ measurements of gas densities from the two Rosetta instruments COPS (COmet Pressure Sensor) and DFMS (Double Focusing Mass Spectrometer) at the positions of the spacecraft to the locations of surface gas emissions during the Rosetta mission 2014-2016. We assume the temporally integrated gas emissions to be representative for the ice composition close to the surface. Our analysis shows characteristic differences in the ice compositions between both hemispheres of 67P/C-G. In particular CO2 ice has a reduced abundance on the northern hemisphere. In contrast to the hemispherical differences, the two lobes do not show significant differences in terms of their ice composition.

Description: The Rosetta mission to comet 67P/C-G provided a detailed view of the near nucleus environment of an active Jupiter family comet. The continuous monitoring of the gas pressure with the ROSINA experiment at the location of the Rosetta spacecraft in combination with the images of the dust environment acquired by the OSIRIS cameras allows one to test different hypotheses about the origin of the dust and gas emissions. In addition the orbital elements and the rotation axis and spin rate of the nucleus are affected by the gas release.

Description: The Moon as our nearest celestial object is one of the most important bodies for space resource exploration and planetary science. However, knowledge of the physical properties of the lunar regolith is required for the exploitation of lunar resources and for understanding the Moon's geologic history. This knowledge comes mainly from Apollo in-situ experiments and returned samples, but the global distribution of these properties is still poorly understood. Remote sensing measurements offer the opportunity to derive properties of unsampled areas with the help of models. In our study, a microphysical thermal model for the lunar regolith was developed and the simulated surface temperatures were compared with thermal emission measurements from the Diviner radiometer on board the Lunar Reconnaissance Orbiter (LRO) to derive regolith properties. This work expands upon previous investigations of lunar regolith properties using Diviner data, by more directly simulating physical properties such as particle size and porosity.

Description: Recently developed Concentric Tube Continuum Robots (CTCRs) are widely exploited in, for example in minimally invasive surgeries which involve navigating inside narrow body cavities close to sensitive regions. These CTCRs can be controlled by extending and rotating the tubes in order to reach a target point or perform some task. The robot must deviate as little as possible from this narrow space and avoid damaging neighbouring tissue. We consider \emph{open-loop} optimal control of CTCRs parameterized over pseudo-time, primarily aiming at minimizing the robot's working volume during its motion. External loads acting on the system like tip loads or contact with tissues are not considered here. We also discussed the inclusion of tip's orientation in the optimal framework to perform some tasks. We recall a quaternion-based formulation of the robot configuration, discuss discretization, develop optimization objectives addressing different criteria, and investigate their impact on robot path planning for several numerical examples. This optimal framework can be applied to any backbone based continuum robots.

Description: Image segmentation is an active area of research for more than 30 years. Traditional image segmentation algorithms are problem-specific and limited in scope. On the other hand, machine learning offers an alternative paradigm where predefined features are combined into different classifiers, providing pixel-level classification and segmentation. However, machine learning only can not address the question as to which features are appropriate for a certain classification problem. This paper presents a project supported in part by the International Neuroinformatics Coordination Facility through the Google Summer of code. The project resulted in an automated image segmentation and classification platform, called Active Segmentation for ImageJ (AS/IJ). The platform integrates a set of filters computing differential geometrical invariants and combines them with machine learning approaches.

Description: Agent-based epidemiological models have been applied widely successfully during the SARS-CoV-2 pandemic and assisted policymakers in assessing the effectiveness of intervention strategies. The computational complexity of agent-based models is still challenging, and therefore it is important to utilize modern multi-core systems as good as possible. In this paper, we are presenting our work on parallelizing the epidemiological simulation model MATSim Episim. Episim combines a large-scale person-centric human mobility model with a mechanistic model of infection and a person-centric disease progression model. In general, the parallelization of agent-based models with an inherent sequential structure — in the case of epidemiological models, the temporal order of the individual movements of the agents — is challenging. Especially when the underlying social network is irregular and dynamic, they require frequent communication between the processing elements. In Episim, however, we were able to take advantage of the fact that people are not contagious on the same day they become infected, and therefore immediate health synchronization is not required. By parallelizing some of the most computationally intensive submodels, we are now able to run MATSim Episim simulations up to eight times faster than the serial version. This makes it feasible to increase the number of agents, e.g. to run simulations for the whole of Germany instead of just Berlin as before.

Description: Portable Standard LISP (PSL, Version 3.4) and REDUCE 3 were implemented for CRAY1 and Cray X- MP computers at the Konrad-Zuse-Zentrum Berlin in 1986. As an special aspect of the implementation of PSL, an interface to the vector hardware of CRAY processors was defined. With that interface and mostly driven by the needs of REDUCE applications (e.g. extensive calculations of Gröbner bases), the arbitrary precision integer arithmetic of PSL was rebuild using full power of the vector hardware. A modular arithmetic using vector hardware was also constructed.

Description: Induction heating of large steel slabs can be described by a coupled system of nonlinear evolution equations of Stefan type representing the temporal and spatial distribution of the induced magnetic field and the generated temperature within the slab. Discretizing these equations implicitly in time and by finite differences in space, at each time step the solution of a system of difference inclusions is required. For the solution of that system two multi-grid algorithms are given which combined with a nested iteration type continuation strategy to proceed in time result in computationally highly efficient schemes for the numerical simulation of the induction heating process. {\bf Keywords:} induction heating, system of two coupled Stefan equations, multi-grid algorithms. {\bf Subject Classification:} AMS(MOS): 35K60, 35R35, 65H10, 65N05, 65N20, 78A25, 78A55.

Description: Gröbner bases are the main tool for solving systems of algebraic equations and some other problems in connection with polynomial ideals using Computer Algebra Systems. The procedure for the computation of Gröbner bases in REDUCE 3.3 has been modified in order to solve more complicated algebraic systems of equations by some general improvements and by some tools based on the specific resources of the CRAY X-MP. We present this modification and illustrate it by examples.

Description: The paper presents the mathematical concepts underlying the new adaptive finite element code KASKADE, which, in its present form, applies to linear scalar second-order 2-D elliptic problems on general domains. Starting point for the new development is the recent work on hierarchical finite element bases due to Yserentant (1986). It is shown that this approach permits a flexible balance between iterative solver, local error estimator, and local mesh refinement device - which are the main components of an adaptive PDE code. Without use of standard multigrid techniques, the same kind of computational complexity is achieved - independent of any uniformity restrictions on the applied meshes. In addition, the method is extremely simple and all computations are purely local - making the method particularly attractive in view of parallel computing. The algorithmic approach is illustrated by a well-known critical test problem. {\bf Keywords:} finite elements, hierarchical basis, adaptive mesh refinement, preconditioned conjugate gradient methods.

Description: This document describes operating procedures for running REDUCE specific to the CRAY 1 and CRAY X-MP computers running the Operating System UNICOS. The document was derived from the corresponding document for Vax/UNIX prepared by A. C. Hearn and L. R. Seward, The Rand Corporation, Santa Monica, (CP85).

Description: The paper presents a new approach to the computational treatment of polyreaction kinetics. This approach is characterized by a Galerkin method based on orthogonal polynomials of a discrete variable, the polymer degree (or chain length). In comparison with the known competing approaches (statistical moment treatment, Galerkin methods for continuous polymer models), the suggested method is shown to avoid the disadvantages and preserve the adventages of either of them. The basic idea of the method is the construction of a discrete inner product associated with a reasonably chosen probability density function. For the so-called Schulz-Flory distribution one thus obtains the discrete Laguerre polynomials, whereas the Poisson distribution leads to the Charlier polynomials. Numerical experiments for selected polyreaction mechanisms illustrate the efficiency of the proposed method.

Description: The paper presents a new application of computer algebra to the treatment of steady states of reaction systems. The method is based on the Buchberger algorithm. This algorithm was modified such that it can exploit the special structure of the equations derived from reaction systems, so even large systems can be handled. In contrast to numerical approximation techniques, the algebraic solution gives a complete and definite overview of the solution space and it is even applicable when parameter values are unknown or undetermined. The algorithm, its adaptation to the problem class and its application to selected examples are presented.

Description: This guide describes the CRAY/UNICOS REDUCE distribution tape and the procedures for installing, testing and maintaining REDUCE on a CRAY 1 or CRAY X-MP running UNICOS. This document was derived from the corresponding document for Vax/UNIX prepared by A. C. Hearn and L.R. Seward, The Rand Corporation, Santa Monica, publication CP84.

Description: We model a symmetric system of coupled oscillators as a graph with symmetry group $\gamma$. Each vertex of the graph represents an "oscillator" or a "cell" of reactants. The magnitude (concentration) of the reactants in the $ i $ th cell is represented by a vector $ x^i $. The edges represent the coupling of the cells. The cells are assumed to evolve by identical reaction-diffusion equation which depends on the sum of the reactants in the nearest neighbors. Thus the dynamics of the system is described by a nonlinear differential system \begin{flushleft} \[ \mbox {(*) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \dot{x}^i = f (x^i,\sum_{j \in N_i} x^j), \mbox { \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \] \end{flushleft} where the sum ranges over the set $ N_i $ of neighbors of cell $ i $ . If $ f $ also has a symmetry (e.g., oddness), there are geometric conditions on the graph such that the nonlinear system $ (*) $ decouples globally into a product flow on certain sums of isotropy subspaces. Thus we may detect higher-dimensional tori of solutions of $ (*) $ which are not amenable to other types of analysis. We present a number of examples, such as bipartite graphs, complete graphs, the square, the octahedron, and a 6-dimensional cube.

Description: The Buchberger algorithm is a basic tool for the solution of systems of polynomial equations in an environment of computer algebra applications. A model for overlapped processing of different steps of the algorithm is presented, which uses the data structure of the polynomials (distributive representation) for synchronization. The model can be applied for multi processors with fast access to shared data. It is tested with Cray X-MP multi processors based on a parallel version of Portable Standard Lisp (PSL 3.4).