Library

Description: Im Rahmen ihrer Strategie zur Langzeitarchivierung forscht die Deutsche Kinemathek in einer Kooperation mit dem Zuse-Institut Berlin (ZIB) an der digitalen Langzeitarchivierung von AV-Materialien. Ausgangspunkt des Projektes sind die enormen Dateigrößen und die heterogenen Dateiformate, die einem Werk und einer Fassung zugeordnet werden müssen. Die Verwendung von persistenten Identifikatoren stellt den Lösungsansatz dar.

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: Die Sicherung und längerfristige Archivierung persönlich relevanter Dokumente und Dateien, in der Fachliteratur als Personal Digital Archiving (PDA) bezeichnet, ist eine für Privatpersonen zunehmend wichtiger werdende Aufgabe. Praktische Anleitungen und weiterführende Hinweise zur Umsetzung dieser Aufgabe gibt die auf unterschiedliche Nutzer:innenperspektiven ausgerichtete Webseite meinDigitalesArchiv.de, die seit 2020 von der nestor-AG PDA bereitgestellt wird. Mit den Informationen dieser Webseite können und sollten Bibliotheken und andere Einrichtungen, die Informationskompetenz vermitteln, Privatpersonen für die Sicherung ihrer persönlichen digitalen Daten sensibilisieren und schulen. Mit der Umsetzung dieser Aufgabe können Öffentliche wie Wissenschaftliche Bibliotheken zur Sicherung auch gesamtgesellschaftlich relevanter Erinnerungsbausteine beitragen.

Description: 二次割当問題は線形緩和が弱いことが知られ，強化のため多様な緩和手法が考案されているが，その一つである二重非負値計画緩和（ DNN 緩和）及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し，それらに基づく分枝限定法の実装及び数値実験結果について報告する．

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: Der Kooperative Bibliotheksverbund Berlin-Brandenburg wird heute 25 Jahre alt. Seit dem 1. April 1997 entwickelt der KOBV neue Dienstleistungen für Nutzende und Bibliotheken, baut Informationsinfrastrukturen in Berlin und Brandenburg aus, vernetzt Bibliotheken aus der Region und informiert über aktuelle Themen. Im Sondernewsletter geben uns aktuelle und ehemalige KOBV-Mitarbeitende/Mitglieder Antworten auf Fragen zur Entstehung und Weiterentwicklung des Verbundes. Lesen und feiern Sie mit uns zusammen!

Description: Mit DeepGreen wurde eine Infrastruktur aufgebaut und etabliert, die Zeitschriftenartikel von wissenschaftlichen Verlagen abholt und berechtigten Bibliotheken zur Veröffentlichung in ihren Repositorien sendet. DeepGreen unterstützt Bibliotheken als Dienstleister für Hochschulen, außeruniversitäre Einrichtungen und die dort tätigen Wissenschaftler*innen, Publikationen auf Open-Access-Repositorien frei zugänglich zu machen und fördert das Zusammenspiel von wissenschaftlichen Einrichtungen und Verlagen. DeepGreen wurde von Januar 2016 bis Juni 2021 von der Deutschen Forschungsgemeinschaft gefördert und wird nun vom Kooperativen Bibliotheksverbund Berlin-Brandenburg, von der Bayerischen Staatsbibliothek und von der Universitätsbibliothek Erlangen-Nürnberg in arbeitsteiliger Eigenleistung für zwei Jahre weiterbetrieben. Der vorliegende Beitrag beleuchtet vielfältige Aspekte bei der Realisierung von DeepGreen und geht auf die Perspektiven dieser zentralen Open-Access-Infrastruktur für deutsche Wissenschaftseinrichtungen ein.

Description: DeepGreen wurde vom 01.08.2018 bis zum 30.06.2021 in einer zweiten Projektphase von der Deutschen Forschungsgemeinschaft (DFG) gefördert. DeepGreen unterstützt Bibliotheken als Dienstleister für Hochschulen, außeruniversitäre Forschungseinrichtungen und die dort tätigen Wissenschaftler:innen dabei, Publikationen auf Open-Access-Repositorien frei zugänglich zu machen und fördert das Zusammenspiel von wissenschaftlichen Einrichtungen und Verlagen. An der zweiten Projektphase waren der Kooperative Bibliotheksverbund Berlin-Brandenburg, die Bayerische Staatsbibliothek, der Bibliotheksverbund Bayern, die Universitätsbibliotheken der Friedrich-Alexander-Universität Erlangen-Nürnberg und der Technischen Universität Berlin und das Helmholtz Open Science Office beteiligt. In dem Projekt wurde erfolgreich eine technische und organisatorische Lösung zur automatisierten Verteilung von Artikeldaten wissenschaftlicher Verlage an institutionelle und fachliche Repositorien entwickelt. In der zweiten Projektphase lag der Fokus auf der Erprobung der Datendrehscheibe in der Praxis und der Ausweitung auf weitere Datenabnehmer und weitere Verlage. Im Anschluss an die DFG-geförderte Projektlaufzeit ist DeepGreen in einen zweijährigen Pilotbetrieb übergegangen. Ziel des Pilotbetriebs ist es, den Übergang in einen bundesweiten Real-Betrieb vorzubereiten.

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: Convexity is an important property in nonlinear optimization since it allows to apply efficient local methods for finding global solutions. We propose to apply symbolic methods to prove or disprove convexity of rational functions over a polyhedral domain. Our algorithms reduce convexity questions to real quantifier elimination problems. Our methods are implemented and publicly available in the open source computer algebra system REDUCE. Our long term goal is to integrate REDUCE as a workhorse'' for symbolic computations into a numerical solver.

Description: Applications which need exclusive access to a shared resource in distributed systems require a fault-tolerant and scalable mechanism to coordinate this exclusive access. Examples of such applications include distributed file systems and master/slave data replication. We present Flease, an algorithm for decentralized and fault-tolerant lease coordination in distributed systems. Our algorithm allows the processes competing for a resource to coordinate exclusive access through leases among themselves without a central component. The resulting system easily scales with an increasing number of nodes and resources. We prove that Flease ensures exclusive access, i.e. guarantees that there is at most one valid lease at any time.

Description: We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.

Description: In optimal control problems with nonlinear time-dependent 3D PDEs, full 4D discretizations are usually prohibitive due to the storage requirement. For this reason gradient and quasi-Newton methods working on the reduced functional are often employed. The computation of the reduced gradient requires one solve of the state equation forward in time, and one backward solve of the adjoint equation. The state enters into the adjoint equation, again requiring the storage of a full 4D data set. We propose a lossy compression algorithm using an inexact but cheap predictor for the state data, with additional entropy coding of prediction errors. As the data is used inside a discretized, iterative algorithm, lossy coding maintaining an error bound is sufficient.

Description: Bovine fertility is the subject of extensive research in animal sciences, especially because fertility of dairy cows has declined during the last decades. The regulation of estrus is controlled by the complex interplay of various organs and hormones. Mathematical modeling of the bovine estrous cycle could help in understanding the dynamics of this complex biological system. In this paper we present a mathematical model of the bovine estrous cycle that includes the processes of follicle and corpus luteum development and the key hormones that interact to control these processes. Focus in this paper is on development of the model, but also some simulation results are presented, showing that a set of equations and parameters is obtained that describes the system consistent with empirical knowledge. Even though the majority of the mechanisms that are included are only known qualitatively as stimulatory or inhibitory effects, the model surprisingly well features quantitative observations made in reality. This model of the bovine estrous cycle could be used as a basis for more elaborate models with the ability to study effects of external manipulations and genetic differences.

Description: Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.

Description: We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL, DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on three realistic network topologies as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks. These results are independent of the ratio between the demand and capacity granularities, the time scale and the network topology, and show little dependency on the demand structure.

Description: We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by “connection capacities” into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.

Description: The aim of this paper is to devise an adaptive timestep control in the contact--stabilized Newmark method (CONTACX) for dynamical contact problems between two viscoelastic bodies in the framework of Signorini's condition. In order to construct a comparative scheme of higher order accuracy, we extend extrapolation techniques. This approach demands a subtle theoretical investigation of an asymptotic error expansion of the contact--stabilized Newmark scheme. On the basis of theoretical insight and numerical observations, we suggest an error estimator and a timestep selection which also cover the presence of contact. Finally, we give a numerical example.

Description: Railway scheduling is based on the principle of the construction of a conflict-free timetable. This leads to a strict definition of capacity: in contrast with road transportation, it can be said in advance whether a given railway infrastructure can accommodate - at least in theory - a certain set of train requests. Consequently, auctions for railway capacity are modeled as auctions of discrete goods -- the train slots. We present estimates for the efficiency gain that may be generated by slot auctioning in comparison with list price allocation. We introduce a new class of allocation and auction problems, the feasible assignment problem, that is a proper generalization of the well-known combinatorial auction problem. The feasible assignment class was designed to cover the needs for an auction mechanism for railway slot auctions, but is of interest in its own right. As a practical instance to state and solve the railway slot allocation problem, we present an integer programming formulation, briefly the ACP, which turns out to be an instance of the feasible assignment problem and whose dual problem yields prices that can be applied to define a useful activity rule for the linearized version of the Ausubel Milgrom Proxy auction. We perform a simulation aiming to measure the impact on efficiency and convergence rate.

Description: We consider a variant of the classical lot-sizing problem in which the capacity in each period is an integer multiple of some basic batch size. Pochet and Wolsey (Math. Oper. Res. 18, 1993) presented an O(n^2 min{n,C}) algorithm to solve this problem and a linear program with O(n^3) variables and inequalities, where n is the number of periods and C the batch size. We provide a linear program of size O(n^2 min{n,C}), that is, in case that C 〈 n, our formulation is smaller.

Description: Providing realistic performance indicators of online algorithms for a given online optimization problem is a difficult task in general. Due to significant drawbacks of other concepts like competitive analysis, Markov decision problems (MDPs) may yield an attractive alternative whenever reasonable stochastic information about future requests is available. However, the number of states in MDPs emerging from real applications is usually exponential in the original input parameters. Therefore, the standard methods for analyzing policies, i.e., online algorithms in our context, are infeasible. In this thesis we propose a new computational tool to evaluate the behavior of policies for discounted MDPs locally, i.e., depending on a particular initial state. The method is based on a column generation algorithm for approximating the total expected discounted cost of an unknown optimal policy, a concrete policy, or a single action (which assumes actions at other states to be made according to an optimal policy). The algorithm determines an $\varepsilon$-approximation by inspecting only relatively small local parts of the total state space. We prove that the number of states required for providing the approximation is independent of the total number of states, which underlines the practicability of the algorithm. The approximations obtained by our algorithm are typically much better than the theoretical bounds obtained by other approaches. We investigate the pricing problem and the structure of the linear programs encountered in the column generation. Moreover, we propose and analyze different extensions of the basic algorithm in order to achieve good approximations fast. The potential of our analysis tool is exemplified for discounted MDPs emerging from different online optimization problems, namely online bin coloring, online target date assignment, and online elevator control. The results of the experiments are quite encouraging: our method is mostly capable to provide performance indicators for online algorithms that much better reflect observations made in simulations than competitive analysis does. Moreover, the analysis allows to reveal weaknesses of the considered online algorithms. This way, we developed a new online algorithm for the online bin coloring problem that outperforms existing ones in our analyses and simulations.

Description: This paper presents concepts and implementation of the finite element toolbox Kaskade 7, a flexible C++ code for solving elliptic and parabolic PDE systems. Issues such as problem formulation, assembly and adaptivity are discussed at the example of optimal control problems. Trajectory compression for parabolic optimization problems is considered as a case study.

Description: In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.

Description: The paper considers linear elliptic equations with regular Borel measures as inhomogeneity. Such equations frequently appear in state-constrained optimal control problems. By a counter-example of Serrin, it is known that, in the presence of non-smooth data, a standard weak formulation does not ensure uniqueness for such equations. Therefore several notions of solution have been developed that guarantee uniqueness. In this note, we compare different definitions of solutions, namely the ones of Stampacchia and the two notions of solutions of Casas and Alibert-Raymond, and show that they are the same. As side results, we reformulate the solution in the sense of Stampacchia, and prove the existence and uniqueness of solutions in in case of mixed boundary conditions.

Description: This cumulative thesis collects the following six papers for obtaining the habilitation at the Technische Universität Berlin, Fakultät II – Mathematik und Naturwissenschaften: (1) Set packing relaxations of some integer programs. (2) Combinatorial packing problems. (3) Decomposing matrices into blocks. (4) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. (5) Models for railway track allocation. (6) A column-generation approach to line planning in public transport. Some changes were made to the papers compared to the published versions. These pertain to layout unifications, i.e., common numbering, figure, table, and chapter head layout. There were no changes with respect to notation or symbols, but some typos have been eliminated, references updated, and some links and an index was added. The mathematical content is identical. The papers are about the optimization of public transportation systems, i.e., bus networks, railways, and airlines, and its mathematical foundations, i.e., the theory of packing problems. The papers discuss mathematical models, theoretical analyses, algorithmic approaches, and computational aspects of and to problems in this area. Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of packing problems as a general framework that can be used to study traffic optimization problems. Indeed, traffic optimization problems can often be modelled as path packing, partitioning, or covering problems, which lead directly to set packing, partitioning, and covering models. Such models are used in papers 4, 5, and 6 to study a variety of problems concerning the planning of line systems, buses, trains, and crews. The common aim is always to exploit as many degrees of freedom as possible, both at the level of the individual problems by using large-scale integer programming techniques, as well as on a higher level by integrating hitherto separate steps in the planning process.