Bibliothek

Beschreibung: The Jacobi set of a bivariate scalar field is the set of points where the gradients of the two constituent scalar fields align with each other. It captures the regions of topological changes in the bivariate field. The Jacobi set is a bivariate analog of critical points, and may correspond to features of interest. In the specific case of time-varying fields and when one of the scalar fields is time, the Jacobi set corresponds to temporal tracks of critical points, and serves as a feature-tracking graph. The Jacobi set of a bivariate field or a time-varying scalar field is complex, resulting in cluttered visualizations that are difficult to analyze. This paper addresses the problem of Jacobi set simplification. Specifically, we use the time-varying scalar field scenario to introduce a method that computes a reduced Jacobi set. The method is based on a stability measure called robustness that was originally developed for vector fields and helps capture the structural stability of critical points. We also present a mathematical analysis for the method, and describe an implementation for 2D time-varying scalar fields. Applications to both synthetic and real-world datasets demonstrate the effectiveness of the method for tracking features.

Beschreibung: Computing an optimal cycle in a given homology class, also referred to as the homology localization problem, is known to be an NP-hard problem in general. Furthermore, there is currently no known optimality criterion that localizes classes geometrically and admits a stability property under the setting of persistent homology. We present a geometric optimization of the cycles that is computable in polynomial time and is stable in an approximate sense. Tailoring our search criterion to different settings, we obtain various optimization problems like optimal homologous cycle, minimum homology basis, and minimum persistent homology basis. In practice, the (trivial) exact algorithm is computationally expensive despite having a worst case polynomial runtime. Therefore, we design approximation algorithms for the above problems and study their performance experimentally. These algorithms have reasonable runtimes for moderate sized datasets and the cycles computed by these algorithms are consistently of high quality as demonstrated via experiments on multiple datasets.

Beschreibung: Das Papier gibt Hinweise zu URIs (Uniform Resource Identifiers) im GLAM-Sektor.

Beschreibung: We introduce time-varying extremum graph (TVEG), a topological structure to support visualization and analysis of a time- varying scalar field. The extremum graph is a substructure of the Morse-Smale complex. It captures the adjacency relationship between cells in the Morse decomposition of a scalar field. We define the TVEG as a time-varying extension of the extremum graph and demonstrate how it captures salient feature tracks within a dynamic scalar field. We formulate the construction of the TVEG as an optimization problem and describe an algorithm for computing the graph. We also demonstrate the capabilities of TVEG towards identification and exploration of topological events such as deletion, generation, split, and merge within a dynamic scalar field via comprehensive case studies including a viscous fingers and a 3D von Kármán vortex street dataset.

Beschreibung: The Bay of Bengal (BoB) has maintained its salinity distribution over the years despite a continuous flow of fresh water entering it through rivers on the northern coast, which is capable of diluting the salinity. This can be attributed to the cyclic flow of high salinity water (〉= 35 psu), coming from Arabian sea and entering BoB from the south, which moves northward and mixes with this fresh water. The movement of this high salinity water has been studied and analyzed in previous work (Singh et al., 2022). This paper extends the computational methods and analysis of salinity movement. Specifically, we introduce an advection based feature definition that represents the movement of high salinity water, and describe algorithms to track their evolution over time. This method allows us to trace the movement of high salinity water caused due to ocean currents. The method is validated via comparison with established observations on the flow of high salinity water in the BoB, including its entry from the Arabian Sea and its movement near Sri Lanka. Further, the visual analysis and tracking framework enables us to compare it with previous work and analyze the contribution of advection to salinity transport.

Beschreibung: Gesture recognition is a tool to enable novel interactions with different techniques and applications, like Mixed Reality and Virtual Reality environments. With all the recent advancements in gesture recognition from skeletal data, it is still unclear how well state-of- the-art techniques perform in a scenario using precise motions with two hands. This paper presents the results of the SHREC 2024 contest organized to evaluate methods for their recognition of highly similar hand motions using the skeletal spatial coordinate data of both hands. The task is the recognition of 7 motion classes given their spatial coordinates in a frame-by-frame motion. The skeletal data has been captured using a Vicon system and pre-processed into a coordinate system using Blender and Vicon Shogun Post. We created a small, novel dataset with a high variety of durations in frames. This paper shows the results of the contest, showing the techniques created by the 5 research groups on this challenging task and comparing them to our baseline method.

Beschreibung: Although Virtual Reality (VR) has undoubtedly improved human interaction with 3D data, users still face difficulties retaining important details of complex digital objects in preparation for physical tasks. To address this issue, we evaluated the potential of visuohaptic integration to improve the memorability of virtual objects in immersive visualizations. In a user study (N=20), participants performed a delayed match-to-sample task where they memorized stimuli of visual, haptic, or visuohaptic encoding conditions. We assessed performance differences between the conditions through error rates and response time. We found that visuohaptic encoding significantly improved memorization accuracy compared to unimodal visual and haptic conditions. Our analysis indicates that integrating haptics into immersive visualizations enhances the memorability of digital objects. We discuss its implications for the optimal encoding design in VR applications that assist professionals who need to memorize and recall virtual objects in their daily work.

Beschreibung: A major restriction to applying deep learning methods in cryo-electron tomography is the lack of annotated data. Many large learning-based models cannot be applied to these images due to the lack of adequate experimental ground truth. One appealing alternative solution to the time-consuming and expensive experimental data acquisition and annotation is the generation of simulated cryo-ET images. In this context, we exploit a public cryo-ET simulator called PolNet to generate three datasets of two macromolecular structures, namely the ribosomal complex 4v4r and Thermoplasma acidophilum 20S proteasome, 3j9i. We select these two specific particles to test whether our models work for macromolecular structures with and without rotational symmetry. The three datasets contain 50, 150, and 450 tomograms with a voxel size of 10 ̊A, respectively. Here, we publish patches of size 40 × 40 × 40 extracted from the medium-sized dataset with 26,703 samples of 4v4r and 40,671 samples of 3j9i. The original tomograms from which the samples were extracted are of size 500 × 500 × 250. Finally, it should be noted that the currently published test dataset is employed for reporting the results of our paper titled ”DeepOrientation: Deep Orientation Estimation of Macromolecules in Cryo-electron tomography” paper.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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).

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: 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.

Beschreibung: We consider a shape implant design problem that arises in the context of facial surgery. We introduce a reformulation as an optimal control problem, where the control acts as a boundary force. The state is modelled as a minimizer of a polyconvex hyperelastic energy functional. We show existence of optimal solutions and derive - on a formal level - first order optimality conditions. Finally, preliminary numerical results are presented.

Beschreibung: This paper presents efficient computational techniques for solving an optimization problem in cardiac defibrillation governed by the monodomain equations. Time-dependent electrical currents injected at different spatial positions act as the control. Inexact Newton-CG methods are used, with reduced gradient computation by adjoint solves. In order to reduce the computational complexity, adaptive mesh refinement for state and adjoint equations is performed. To reduce the high storage and bandwidth demand imposed by adjoint gradient and Hessian-vector evaluations, a lossy compression technique for storing trajectory data is applied. An adaptive choice of quantization tolerance based on error estimates is developed in order to ensure convergence. The efficiency of the proposed approach is demonstrated on numerical examples.

Beschreibung: In recent years Markov State Models (MSMs) have attracted a consid- erable amount of attention with regard to modelling conformation changes and associated function of biomolecular systems. They have been used successfully, e.g., for peptides including time-resolved spectroscopic ex- periments, protein function and protein folding , DNA and RNA, and ligand-receptor interaction in drug design and more complicated multi- valent scenarios. In this article a novel reweighting scheme is introduced that allows to construct an MSM for certain molecular system out of an MSM for a similar system. This permits studying how molecular proper- ties on long timescales differ between similar molecular systems without performing full molecular dynamics simulations for each system under con- sideration. The performance of the reweighting scheme is illustrated for simple test cases including one where the main wells of the respective en- ergy landscapes are located differently and an alchemical transformation of butane to pentane where the dimension of the state space is changed.

Beschreibung: We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.

Beschreibung: We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of edges to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.

Beschreibung: 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 the 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.

Beschreibung: One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique MIP solvers usually apply at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, the state-of-the-art hybrid branching rule can be improved this way as well. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.

Beschreibung: To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.

Beschreibung: We investigate the problem of finding modules (or clusters, communities) in directed networks. Until now, most articles on this topic have been oriented towards finding complete network partitions despite the fact that this often is unwanted. We present a novel random walk based approach for non-complete partitions of the directed network into modules in which some nodes do not belong to only one of the modules but to several or to none at all. The new random walk process is reversible even for directed networks but inherits all necessary information about directions and structure of the original network. We demonstrate the performance of the new method in application to a real-world earthquake network.

Beschreibung: Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de

Beschreibung: Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung im öffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten die Fahrerzufriedenheit deutlich steigern lässt.

Beschreibung: Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein.

Beschreibung: The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.

Beschreibung: This thesis deals with the hypergraph assignment problem (HAP), a set partitioning problem in a special type of hypergraph. The HAP generalizes the assignment problem from bipartite graphs to what we call bipartite hypergraphs, and is motivated by applications in railway vehicle rotation planning. The main contributions of this thesis concern complexity, polyhedral results, analyses of random instances, and primal methods for the HAP. We prove that the HAP is NP-hard and APX-hard even for small hyperedge sizes and hypergraphs with a special partitioned structure. We also study the complexity of the set packing and covering relaxations of the HAP, and present for certain cases polynomial exact or approximation algorithms. A complete linear description is known for the assignment problem. We therefore also study the HAP polytope. There, we have a huge number of facet-defining inequalities already for a very small problem size. We describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of the polytope. We propose the algorithm "HUHFA" for the classification that is applicable not only to the HAP but combinatorial optimization problems involving symmetries in general. In the largest possible HAP instance for which we could calculate the complete linear description, we have 14049 facets, which can be divided into 30 symmetry classes. We can combinatorially interpret 16 of these classes. This is possible by employing cliques to generalize the odd set inequalities for the matching problem. The resulting inequalities are valid for the polytope associated with the set packing problem in arbitrary hypergraphs and have a clear combinatorial meaning. An analysis of random instances provides a better insight into the structure of hyperassignments. Previous work has extensively analyzed random instances for the assignment problem theoretically and practically. As a generalization of these results for the HAP, we prove bounds on the expected value of a minimum cost hyperassignment that uses half of the maximum possible number of hyperedges that are not edges. In a certain complete partitioned hypergraph G2,2n with i. i. d. exponential random variables with mean 1 as hyperedge costs it lies between 0.3718 and 1.8310 if the vertex number tends to infinity. Finally, we develop an exact combinatorial solution algorithm for the HAP that combines three methods: A very large-scale neighborhood search, the composite columns method for the set partitioning problem, and the network simplex algorithm.

Beschreibung: Diese Arbeit beschäftigt sich mit dem Hypergraph Assignment Problem (Abkürzung "HAP", dt.: Zuordnungsproblem auf Hypergraphen), einem Mengenzerlegungsproblem auf einem speziellen Typ von Hypergraphen. Das HAP verallgemeinert das Zuordnungsproblem von bipartiten Graphen auf eine Struktur, die wir bipartite Hypergraphen nennen, und ist durch eine Anwendung in der Umlaufplanung im Schienenverkehr motiviert. Die Hauptresultate betreffen die Komplexität, polyedrische Ergebnisse, die Analyse von Zufallsinstanzen sowie primale Methoden für das HAP. Wir beweisen, dass das HAP NP-schwer und APX-schwer ist, sogar wenn wir uns auf kleine Hyperkantengrößen und Hypergraphen mit einer speziellen, partitionierten Struktur beschränken. Darüber hinaus untersuchen wir die Komplexität der Mengenpackungs- sowie Mengenüberdeckungsrelaxierung und geben für bestimmte Fälle Approximations- und exakte Algorithmen mit einer polynomiellen Laufzeit an. Für das Polytop des Zuordnungsproblems ist eine vollständige lineare Beschreibung bekannt. Wir untersuchen daher auch das HAP-Polytop. Dafür ist die Anzahl der Facettenungleichungen schon für sehr kleine Problemgrößen sehr groß. Wir beschreiben eine Methode zur Aufteilung der Ungleichungen in Äquivalenzklassen, die ohne die Verwendung von Normalformen auskommt. Die Facetten in jeder Klasse können durch Symmetrien ineinander überführt werden. Es genügt, einen Repräsentanten aus jeder Klasse anzugeben, um ein vollständiges Bild der Polytopstruktur zu erhalten. Wir beschreiben den Algorithmus "HUHFA", der diese Klassifikation nicht nur für das HAP, sondern für beliebige kombinatorische Optimierungsprobleme, die Symmetrien enthalten, durchführt. Die größtmögliche HAP-Instanz, für die wir die vollständige lineare Beschreibung berechnen konnten, hat 14049 Facetten, die in 30 Symmetrieklassen aufgeteilt werden können. Wir können 16 dieser Klassen kombinatorisch interpretieren. Dafür verallgemeinern wir Odd-Set-Ungleichungen für das Matchingproblem unter Verwendung von Cliquen. Die Ungleichungen, die wir erhalten, sind gültig für Mengenpackungsprobleme in beliebigen Hypergraphen und haben eine klare kombinatorische Bedeutung. Die Analyse von Zufallsinstanzen erlaubt einen besseren Einblick in die Struktur von Hyperzuordnungen. Eine solche ausführliche Analyse wurde in der Literatur theoretisch und praktisch bereits für das Zuordnungsproblem durchgeführt. Als eine Verallgemeinerung dieser Ergebnisse für das HAP beweisen wir Schranken für den Erwartungswert einer Hyperzuordnung mit minimalen Kosten, die genau die Hälfte der maximal möglichen Anzahl an Hyperkanten, die keine Kanten sind, benutzt. In einem sog. vollständigen partitionierten Hypergraphen G2,2n mit Hyperkantenkosten, die durch unabhängig identisch exponentiell verteilte Zufallsvariablen mit Erwartungswert 1 bestimmt sind, liegt dieser Wert zwischen 0.3718 und 1.8310, wenn die Knotenanzahl gegen unendlich strebt. Schließlich entwickeln wir eine exakte kombinatorische Lösungsmethode für das HAP, die drei Ansätze kombiniert: Eine Nachbarschaftssuche mit Nachbarschaften exponentieller Größe, die Composite-Columns-Methode für das Mengenzerlegungsproblem sowie den Netzwerksimplexalgorithmus.

Beschreibung: Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. We formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition. We solve MINLP single-scenario sub-problems and obtain valid bounds even without solving them to optimality. Heuristics prove capable of improving the initial solutions substantially. Results of computational experiments are presented.

Beschreibung: We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$.

Beschreibung: The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.

Beschreibung: We employ the adaptive resolution approach AdResS, in its recently developed Grand Canonicallike version (GC-AdResS) [Wang et al. Phys.Rev.X 3, 011018 (2013)], to calculate the excess chemical potential, $μ^{ex}$, of various liquids and mixtures. We compare our results with those obtained from full atomistic simulations using the technique of thermodynamic integration and show a satisfactory agreement. In GC-AdResS the procedure to calculate $μ^{ex}$ corresponds to the process of standard initial equilibration of the system; this implies that, independently of the specific aim of the study, $μ^{ex}$, for each molecular species, is automatically calculated every time a GC-AdResS simulation is performed.

Beschreibung: We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.

Beschreibung: A common technique in the solution of large or complex optimization problems is the use of micro–macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconveniently by underestimating the global optimal value.

Beschreibung: The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, such as vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing vehicle rotations often have to be re-optimized to deal with timetable changes or construction sites. We present an integrated modeling and algorithmic approach to this task as well as computational results for industrial problem instances of DB Fernverkehr AG.

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