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: While energy-intensive industries like the steel industry plan to switch to renewable energy sources, other industries, such as the cement industry, have to rely on carbon capture storage and utilization technologies to reduce the inevitable carbon dioxide (CO2) emissions of their production processes. In this context, we investigate the problem of finding optimal pipeline diameters from a discrete set of diameters for a tree-shaped network transporting captured CO2 from multiple sources to a single sink. The general problem of optimizing arc capacities in potential-based fluid networks is a challenging mixed-integer nonlinear program. Additionally, the behaviour of CO2 is highly sensitive and nonlinear regarding temperature and pressure changes. We propose an iterative algorithm splitting the problem into two parts: a) the pipe-sizing problem under a fixed supply scenario and temperature distribution and b) the thermophysical modelling including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We show the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany.

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

Description: Reliable numerical simulations of nano-optical structures are the key for design and pre-fabrication processes in diverse disciplines such as lithography in semiconductor industries, spectroscopy of biological molecules, optimization of quantum dot cavities for single-photon sources, and computation of atomic forces like the Casimir Effect. For these purposes a variety of different methods, e.g. FDTD, FEM and RCWA, are in use. On the one hand, FDTD and FEM are investigated intensively - both in mathematics and numerical experiments - and their approximations and convergence properties are well known. On the other hand, there is a lack of these insights in RCWA. In spite of this, RCWA is commonly used to simulate a wide range of systems. We review historical and modern contributions to convergence improvements with respect to RCWA from the early sugesstions to modern developments. We study the convergence rates of the open-source software S4 and analyze the algorithmic properties in detail. Furthermore, we compare RCWA and FEM simulations for different classes of problems including 1D-binary gratings and 2D-periodic photonic crystals.

Description: In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.

Description: Markov Decision Processes (MDP) or Partially Observable MDPs (POMDP) are used for modelling situations in which the evolution of a process is partly random and partly controllable. These MDP theories allow for computing the optimal control policy for processes that can continuously or frequently be observed, even if only partially. However, they cannot be applied if state observation is very costly and therefore rare (in time). We present a novel MDP theory for rare, costly observations and derive the corresponding Bellman equation. In the new theory, state information can be derived for a particular cost after certain, rather long time intervals. The resulting information costs enter into the total cost and thus into the optimization criterion. This approach applies to many real world problems, particularly in the medical context, where the medical condition is examined rather rarely because examination costs are high. At the same time, the approach allows for efficient numerical realization. We demonstrate the usefulness of the novel theory by determining, from the national economic perspective, optimal therapeutic policies for the treatment of the human immunodeficiency virus (HIV) in resource-rich and resource-poor settings. Based on the developed theory and models, we discover that available drugs may not be utilized efficiently in resource-poor settings due to exorbitant diagnostic costs.

Description: Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.

Description: As a basis for meaningful simulation and optimization efforts with regard to traffic engineering or energy consumption in telecommunication networks, suitable models are indispensable. This concerns not only realistic network topologies but also models for the geographical distribution and the temporal dynamics of traffic, as well as the assumptions on network components and technology. This paper derives such a model from the practice of a large national carrier. Applying the network and traffic model, we demonstrate its use by presenting various optimization cases related to energy-efficient telecommunication. Here, we focus on load adaptivity by employing sleep modes to the network hardware, where several constraints on the reconfigurability of the network over time are considered.

Description: We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.

Description: In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.

Description: We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.

Description: We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.

Description: One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. The challenging question is how to expand and operate the network in order to facilitate the transportation of specified gas quantities at minimum cost. This task can be formulated as a mathematical optimization problem that reflects to real-world instances of enormous size and complexity. The aim of this thesis is the development of novel theory and optimization algorithms which make it possible to solve these problems. Gas network topology optimization problems can be modeled as nonlinear mixed-integer programs (MINLPs). Such an MINLP gives rise to a so-called active transmission problem (ATP), a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. The key to solving the ATP as well as the overall gas network topology optimization problem and the main contribution of this thesis is a novel domain relaxation of the variable bounds and constraints in combination with a penalization in the objective function. In case the domain relaxation does not yield a primal feasible solution for the ATP we offer novel sufficient conditions for proving the infeasibility of the ATP. These conditions can be expressed in the form of an MILP, i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. If the gas network consists only of pipes and valves, the ATP turns into a passive transmission problem (PTP). Although its constraints are non-convex, its domain relaxation can be proven to be convex. Consequently, the feasibility of the PTP can be checked directly in an efficient way. Another advantage of the passive case is that the solution of the domain relaxation gives rise to a cutting plane for the overall topology optimization problem that expresses the infeasibility of the PTP. This cut is obtained by a Benders argument from the Lagrange function of the domain relaxation augmented by a specially tailored pc-regularization. These cuts provide tight lower bounds for the passive gas network topology optimization problem. The domain relaxation does not only provide certificates of infeasibility and cutting planes, it can also be used to construct feasible primal solutions. We make use of parametric sensitivity analysis in order to identify binary variables to be switched based on dual information. This approach allows for the first time to compute directly MINLP solutions for large-scale gas network topology optimization problems. All the research in this thesis has been realized within the collaborative research project "Forschungskooperation Netzoptimierung (ForNe)". The developed software is in use by the cooperation partner Open Grid Europe GmbH. Parts of this thesis have been published in book chapters, journal articles and technical reports. An overview of the topics and solution approaches within the research project is given by Martin et al. (2011) and Fügenschuh et al. (2013). Gas network operation approaches and solution methods are described in detail by Pfetsch et al. (2014) and with a special focus on topology optimization in Fügenschuh et al. (2011). The primal heuristic presented in this thesis is published by Humpola et al. (2014b). The method for pruning nodes of the branch-and-bound tree for an approximation of the original problem is described in Fügenschuh and Humpola (2013) and Humpola et al. (2014a). The Benders like inequality is introduced by Humpola and Fügenschuh (2013).

Description: Ein Viertel des europäischen Energiebedarfs wird durch Gas gedeckt, das durch ein europaweites Pipelinesystem verteilt wird. Aufgrund von Ausbaukosten von 1 Mio. Euro pro Kilometer ist der Netzausbau ein Milliardenunterfangen. Die größte Herausforderung besteht darin zu entscheiden, wie das Netzwerk kostengünstig ausgebaut und genutzt werden kann, um notwendige Gasmengen zu transportieren. Diese Aufgabe kann mit Hilfe eines mathematischen Optimierungsproblems formuliert werden, wobei anwendungsnahe Instanzen eine enorme Größe und Komplexität aufweisen. Ziel der vorliegenden Arbeit ist die Entwicklung neuer mathematischer Theorien und damit einhergehender Optimierungsalgorithmen, die es ermöglichen, derartige Probleme zu lösen. Die Optimierung der Topologie eines Gasnetzwerks kann mit Hilfe eines nichtlinearen gemischt-ganzzahligen Programms (MINLP) modelliert werden. Durch Fixierung aller ganzzahligen Variablen ergibt sich ein kontinuierliches Zulässigkeitsproblem, das als aktives Transmissionsproblem (ATP) bezeichnet wird. Die zentrale Methode um dieses ATP zu lösen, ist eine neuartige Relaxierung, welche Variablenschranken und einige Nebenbedingungen relaxiert und in der Zielfunktion bestraft. Diese Relaxierung bildet den Kern der in dieser Arbeit vorgestellten Theorie und ermöglicht so die effiziente Lösung der Topologieoptimierung eines Gasnetzwerkes. Für den Fall, dass die Relaxierung keine Primallösung für das ATP liefert, ist es uns gelungen, hinreichende Bedingungen für die Unzulässigkeit des ATP zu formulieren, die durch ein MILP dargestellt werden. Kurz gefasst kann die Unzulässigkeit eines nicht-konvexen NLP durch Lösung eines MILP bewiesen werden. Beide Methoden liefern effiziente Schranken in einem branch-and-bound Lösungsverfahren. Besteht ein Gasnetzwerk nur aus Rohren und Schiebern, dann wird das ATP als passives Transmissionsproblem (PTP) bezeichnet. Obwohl die Nebenbedingungen des PTP nicht konvex sind, konnten wir zeigen, dass seine Relaxierung konvex ist. Daher kann die Unzulässigkeit des PTP direkt auf effiziente Weise geprüft werden. Außerdem können mit Hilfe der Relaxierung in diesem speziellen Fall Schnittebenen für das Topologieoptimierungsproblem aufgestellt werden. Diese repräsentieren die Unzulässigkeit des PTP und folgen aus der Lagrange Funktion der Relaxierung zusammen mit einer speziellen Erweiterung, der sogenannten pc-Regularisierung. Abgesehen von den genannten Klassifizierungen kann die Relaxierung auch genutzt werden, um primale Lösungen zu konstruieren. Hier nutzen wir die parametrische Sensitivitätsanalyse, um mit Hilfe dualer Informationen Binärvariablen des ATP zu identifizieren, deren Werte angepasst werden müssen. Dieser Ansatz erlaubt es zum ersten Mal, direkt MINLP Lösungen für das Topologieoptimierungsproblem realer Gasnetzwerke zu berechnen. Die Resultate dieser Arbeit wurden im Rahmen des Forschungsprojekts "Forschungskooperation Netzoptimierung (ForNe)" erarbeitet. Die entwickelte Software wird vom Kooperationspartner Open Grid Europe GmbH aktiv genutzt. Teile dieser Arbeit sind in Buchkapiteln, Journalen und technischen Berichten publiziert. Eine Übersicht über die Themen und Lösungsansätze im ForNe-Projekt veröffentlichten Martin u. a. (2011) und Fügenschuh u. a. (2013). Für Lösungsmethoden für die operative Nutzung von Gasnetzwerken verweisen wir auf Pfetsch u. a. (2014). Ansätze für eine Topologieoptimierung wurden von Fügenschuh u. a. (2011) beschrieben. Die in dieser Arbeit präsentierte primale Heuristik ist publiziert von Humpola u. a. (2014b). Die genannte Methode, um Knoten innerhalb des branch-and-bound Baums abzuschneiden, wurde für eine Approximation des Topologieproblems von Fügenschuh und Humpola (2013) und Humpola u. a. (2014a) beschrieben. Ein Bericht über die Ungleichungen nach Benders ist in Humpola und Fügenschuh (2013) nachzulesen.

Description: Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.

Description: Die Anforderungen an das Liniennetz eines Verkehrsunternehmens sind vielfältig: kurze Fahrzeiten, viele Direktverbindungen und geringe Kosten. Mathematische Optimierungsmethoden können die Planung von Liniennetzen unterstützen und beste Kompromisse bzgl. aller Anforderungen berechnen.

Description: We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model based on the explicit use of signal-to-interference quantities. Moreover, to address the uncertain nature of the jamming problem and tackle the peculiar right-hand-side uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from multiband robust optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances.

Description: Coding da Vinci, der erste deutsche Kultur-Hackathon, wurde gemeinsam von der Open Knowledge Foundation Deutschland, der Servicestelle Digitalisierung Berlin, Wikimedia Deutschland und der Deutschen Digitalen Bibliothek veranstaltet. Zwischen Ende April und Anfang Juli haben 150 Teilnehmer (Coder, Webdesigner, Kulturinteressierte u.a.) an Webseiten, mobilen Apps,Spielen, Hardwareprojekten und anderen Anwendungen offener Daten gearbeitet. Die Daten wurden von 16 Kultur-Einrichtungen bereitgestellt. Im Verlauf des Hackathons wurden daraus 17 funktionsfähige Prototypen entwickelt, öffentlich präsentiert und fünf davon auch prämiert.Doch was genau ist ein Hackathon? Wie kommen Kulturinstitutionen und Hacker zusammen? Wie gelangt eine Kulturinstitution zu offenen Daten? Welche Herausforderungen und Chancen bietet ein Hackathon für den Kulturbereich? Welche neue Qualität erwächst aus einem partizipativen Zugang zum digitalen Kulturerbe und der Möglichkeit mit Daten zu arbeiten? Was bleibt zu tun,um die Ergebnisse nachhaltig zu sichern? Diese Fragen sollen anhand der Ergebnisse von CdV diskutiert werden. Unter dem Motto „lessons learned“ wagen wir den Ausblick auf Coding da Vinci 2015.

Description: In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are: - Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation, - a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP, - an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures, - RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution, - Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP, - Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs, - Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection. Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes. The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.

Description: Nano-optical scattering problems play an important role in our modern, technologically driven society. Computers, smartphones and all kinds of electronic devices are manufactured by the semiconductor industry which relies on production using photomasks as well as optical process control. The digital world, e.g. the world wide web, is based on optical interconnects and so-called quantum computers based on optics are supposed to be next generation computers. Moreover, global economic progress demands new and sustainable energy resources and one option is to make use of the power stored in optical radiation from the sun. Additionally, understanding fundamental physics such as the optical properties of asymmetric, or chiral, structures could promote future innovations in engineering. In order to understand and manipulate these kinds of processes, physics provides a well established model: the so-called Maxwell’s equations. Stated by James Clerk Maxwell in 1862, this description of the interaction of light and matter still provides a profound basis for the analysis of electromagnetic phenomena. However, real world problems cannot be calculated using simple mathematics. Rather, computer simulations are needed to obtain solutions of the physical model. Finding suitable methods to solve these problems opens up a wide variety of possibilities. On the one hand, there are methods which require long computing times. On the other hand, some algorithms depend on high memory usage. That is why the field of numerics deals with the question which method is optimally suited for specific problems. The aim of this work is to investigate the applicability of the so-called Fourier Modal Method (FMM) to nano-optical scattering problems in general. Since simple analytical solutions are non-existent for most recent physical problems, we use the Finite Element Method (FEM) to double-check performance of the FMM. Mathematics provide reliable procedures to control the errors of numerics using the FEM. Yet up to now it has not been possible to rigorously classify the quality of the Fourier Modal Method’s results. It is not fully understood whether the process of investing more and more computing resources yields more accurate results. So, we have to ask ourselves: does the numerical method invariably converge? In spite of this uncertainty when using the FMM, it is a well established method dating back to the 1980s. This numerical method has recently been used to optimize performance of solar cells [19] as well as to improve the optical properties of so-called single-photon sources [41] which are essential for quantum cryptography. The latter is a promising candidate to increase digital security and revolutionise cryptography techniques. Furthermore, with the help of the Fourier Modal Method an important issue in optics has been partly resolved: angular filtering of light was made possible by using a mirror which becomes transparent at a certain viewing angle [77]. In addition, an improved numerical technique to design so-called Photonic Crystal waveguides based on the FMM was developed recently [15]. Photonic Crystals are used in the fields of optical bio-sensing and for the construction of novel semiconductor devices. Moreover, approaches to link the FMM and the FEM try to combine advantages of both methods to obtain fast and accurate results [81]. These ideas are closely linked to the well-known concept of Domain Decomposition within the FEM [88]. Here, one possibility to couple domains is to use the scattering matrix formalism as it is done in the FMM. In the scope of this convergence study, we state Maxwell’s equations, particularly for periodic geometries. We describe two physical phenomena of nano-optics, namely chirality and opto-electrical coupling, and define the errors of our simulations. Afterwards, the two investigated methods are analysed with respect to their general properties and a way to unify modelling physics when using both algorithms is presented. With the help of various numerical experiments, we explore convergence characteristics of the FMM and draw conclusions about the ability of this approach to provide accurate results and, consequently, its potential for research on technological innovations.