TY - GEN ED - COMPASS '18, T1 - Two Approximate Dynamic Programming Algorithms for Managing Complete SIS Networks N2 - Inspired by the problem of best managing the invasive mosquito Aedes albopictus across the 17 Torres Straits islands of Australia, we aim at solving a Markov decision process on large Susceptible-Infected-Susceptible (SIS) networks that are highly connected. While dynamic programming approaches can solve sequential decision-making problems on sparsely connected networks, these approaches are intractable for highly connected networks. Inspired by our case study, we focus on problems where the probability of nodes changing state is low and propose two approximate dynamic programming approaches. The first approach is a modified version of value iteration where only those future states that are similar to the current state are accounted for. The second approach models the state space as continuous instead of binary, with an on-line algorithm that takes advantage of Bellman's adapted equation. We evaluate the resulting policies through simulations and provide a priority order to manage the 17 infested Torres Strait islands. Both algorithms show promise, with the continuous state approach being able to scale up to high dimensionality (50 nodes). This work provides a successful example of how AI algorithms can be designed to tackle challenging computational sustainability problems. Y1 - 2018 SN - 978-1-4503-5816-3 U6 - https://doi.org/10.1145/3209811.3209814 PB - ACM New York, NY, USA ER - TY - JOUR A1 - Hassan, Irtaza A1 - Donati, Luca A1 - Stensitzki, Till A1 - Keller, Bettina G A1 - Heyne, Karsten A1 - Imhof, Petra T1 - The vibrational spectrum of the hydrated alanine-leucine peptide in the amide region from IR experiments and first principles calculations JF - Chemical Physics Letters N2 - We have combined infrared (IR) experiments with molecular dynamics (MD) simulations in solution at finite temperature to analyse the vibrational signature of the small floppy peptide Alanine-Leucine. IR spectra computed from first-principles MD simulations exhibit no distinct differences between conformational clusters of -helix or -sheet-like folds with different orientations of the bulky leucine side chain. All computed spectra show two prominent bands, in good agreement with the experiment, that are assigned to the stretch vibrations of the carbonyl and carboxyl group, respectively. Variations in band widths and exact maxima are likely due to small fluctuations in the backbone torsion angles. Y1 - 2018 U6 - https://doi.org/10.1016/j.cplett.2018.03.026 VL - 698 SP - 227 EP - 233 ER - TY - CHAP A1 - Keller, Bettina G. A1 - Aleksić, Stevan A1 - Donati, Luca T1 - Markov State Models in Drug Design T2 - Biomolecular Simulations in Structure‐Based Drug Discovery N2 - This chapter explains the different ways in which Markov State Models (MSMs) can be helpful in structure-based drug design. MSMs are constructed from the time series of molecular dynamics (MD), which can be generated by classical MD simulations. Several features of the MSMs can be utilized for rational drug design. The discretization of a validated MSM is particularly suited to extract meaningful representatives from the conformational ensemble, because the discretization yields a small number of microstates and mirrors the features of the free energy landscape. Long-lived conformations consist of a set of microstates which show high transition rates within the set and low transition rates to microstates outside of the set. The Bayesian agglomerative clustering engine (BACE) algorithm uses the observed transition counts to extract long-lived conformations from an MSM. By iteratively merging microstates according to the Bayes factor and recalculating the Bayes-factor matrix, the algorithm yields an aggregation of the microstates into long-lived conformations. Y1 - 2018 SN - 1865-0562 U6 - https://doi.org/10.1002/9783527806836.ch4 SP - 67 EP - 86 PB - Wiley-Interscience, Weinheim ER - TY - JOUR A1 - Donati, Luca A1 - Keller, Bettina G. T1 - Girsanov reweighting for metadynamics simulations JF - The Journal of Chemical Physics N2 - Metadynamics is a computational method to explore the phase space of a molecular system. Gaussian functions are added along relevant coordinates on the fly during a molecular-dynamics simulation to force the system to escape from minima in the potential energy function. The dynamics in the resulting trajectory are however unphysical and cannot be used directly to estimate dynamical properties of the system. Girsanov reweighting is a recent method used to construct the Markov State Model (MSM) of a system subjected to an external perturbation. With the combination of these two techniques—metadynamics/Girsanov-reweighting—the unphysical dynamics in a metadynamics simulation can be reweighted to obtain the MSM of the unbiased system. We demonstrate the method on a one-dimensional diffusion process, alanine dipeptide, and the hexapeptide Val-Gly-Val-Ala-Pro-Gly (VGVAPG). The results are in excellent agreement with the MSMs obtained from direct unbiased simulations of these systems. We also apply metadynamics/Girsanov-reweighting to a β-hairpin peptide, whose dynamics is too slow to efficiently explore its phase space by direct simulation Y1 - 2018 U6 - https://doi.org/10.1063/1.5027728 VL - 149 IS - 7 SP - 072335 ER - TY - JOUR A1 - Wakayama, Yuki A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakui, Tetsuya T1 - エネルギー供給システムの設計および運用の階層的関係を考慮した最適化(時間集約によるモデル縮約とその効果) T1 - Optimization of Energy Supply Systems in Consideration of Hierarchical Relationship Between Design and Operation(Model Reduction by Time Aggregation and Its Effect) JF - エネルギー・資源学会第34回エネルギーシステム・経済・環境コンファレンス講演論文集 N2 - A hierarchical mixed-integer linear programming method to solve optimal design problems of energy supply systems efficiently has been proposed. The original problem is solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of each other at the lower level. In this paper, a method of reducing model by time aggregation is proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. On one hand, the method may decrease the number of design variables and costraints at the upper level, and thus the computation time at the upper level. On the other hand, it may increase the numbers of generated design solution candidates and solved optimal operation problems, and thus the computation time at both the levels. Though a case study on the optimal design of a cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency. Y1 - 2018 SP - 401 EP - 404 ER - TY - JOUR A1 - Wakayama, Yuki A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakui, Tetsuya T1 - 階層的最適化によるエネルギ ー供給システムの最適設計・運用 (期間のクラスタリングに よるモデル縮約とその効果) T1 - Optimal Design and Operation of Energy Supply Systems by Hierarchical Optimization (Model Reduction by Clustering Periods and Its Effect) JF - 日本機械学会関西支部第93期定時総会講演会講演論文集 N2 - Ahierarchical mixed-integer linear programmingmethod has been proposed to solve optimal design problems of energy supply systems efficiently. In this paper, a method of reducing model by clustering periods is proposed to search design solution candidates efficiently in the relaxed optimal design problem at the upper level. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. Through acase study on the optimaldesign of a cogeneration system, ti is clarified how the model reduction si effective ot enhance the computation efficiency. Y1 - 2018 SP - 259 EP - 260 ER - TY - CHAP A1 - Kramer, Tobias A1 - Läuter, Matthias T1 - Modelling the inner coma of comet 67P/Churyumov-Gerasimenko T2 - Europlanet Science Congress N2 - Based on about 1 million of pressure measurements around comet 67P/Churyumov-Gerasimenko we reconstruct the gas emission across the entire nucleus. Dust particles are seeded in the gas model and the resulting dust distribution follows a daily pattern which agrees with observations if a uniform dust release across the entire sunlit surface is assumed. Y1 - 2018 VL - 12 SP - EPSC2018-115-1 PB - Europlanet Science Congress ER - TY - CHAP A1 - Läuter, Matthias A1 - Kramer, Tobias A1 - Rubin, Martin A1 - Altwegg, Kathrin T1 - Gas production of comet 67P/Churyumov-Gerasimenko reconstructed from DFMS/COPS data T2 - Europlanet Science Congress N2 - We reconstruct the temporal evolution of surface emissions for the four major gas species H2O, CO2, CO, and O2 emitted during the 2015 apparition of comet 67P/Churyumov-Gerasimenko (67P/C-G). Measurements from the Double Focusing Mass Spectrometer (DFMS) of the Rosetta Orbiter Spectrometer for Ion and Neutral Analysis (ROSINA) and the COmet Pressure Sensor (COPS) are used to determine the gas sources on the surface with an inverse gas model for the entire coma. For all species, peak production rates and integrated production rates per orbit are evaluated separately for the northern and the southern hemisphere. Complemented with the total mass production, this allows us to estimate the dust-to-gas ratio of the emitted material. Y1 - 2018 VL - 12 SP - EPSC2018-515-1 PB - Europlanet Science Congress ER - TY - JOUR A1 - Bonami, Pierre A1 - Gleixner, Ambros A1 - Linderoth, Jeff A1 - Misener, Ruth T1 - Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081) JF - Dagstuhl Reports N2 - Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms. Y1 - 2018 U6 - https://doi.org/10.4230/DagRep.8.2.64 VL - 8 IS - 2 SP - 64 EP - 87 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - An Online-Learning Approach to Inverse Optimization Y1 - 2018 ER - TY - JOUR A1 - Bienenstock, Daniel A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - Principled Deep Neural Network Training through Linear Programming N2 - Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting. Y1 - 2018 ER - TY - THES A1 - Dill, Sabrina T1 - Joint Feature Learning and Classification - Deep Learning for Surgical Phase Detection N2 - In this thesis we investigate the task of automatically detecting phases in surgical workflow in endoscopic video data. For this, we employ deep learning approaches that solely rely on frame-wise visual information, instead of using additional signals or handcrafted features. While previous work has mainly focused on tool presence and temporal information for this task, we reason that additional global information about the context of a frame might benefit the phase detection task. We propose novel deep learning architectures: a convolutional neural network (CNN) based model for the tool detection task only, called Clf-Net, as well as a model which performs joint (context) feature learning and tool classification to incorporate information about the context, which we name Context-Clf-Net. For the phase detection task lower-dimensional feature vectors are extracted, which are used as input to recurrent neural networks in order to enforce temporal constraints. We compare the performance of an online model, which only considers previous frames up to the current time step, to that of an offline model that has access to past and future information. Experimental results indicate that the tool detection task benefits strongly from the introduction of context information, as we outperform both Clf-Net results and stateof-the-art methods. Regarding the phase detection task our results do not surpass state-of-the-art methods. Furthermore, no improvement of using features learned by the Context-Clf-Net is observed in the phase detection task for both online and offline versions Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81745 ER - TY - THES A1 - Schotte, Merlind T1 - Finite-Elemente-Techniken zur mechanischen Stabilitätsanalyse der Hyomandibula von Rochen N2 - Haie und Rochen sind die einzigen Wirbeltiere, die sich durch ein Knorpelskelett auszeichnen, das mit winzigen mineralisierten Elementen bedeckt ist, die sogenannten Tesserae. Obwohl dieser mineralisierte Knorpel seit hunderten von Millionen Jahren ein charakteristisches Merkmal dieser Tiere ist, ist der funktionelle Vorteil dieses Gewebestruktur bisher unklar geblieben. In dieser Masterarbeit wird diese Struktur mithilfe der Finite-Elemente-Methode(FEM) untersucht, wobei biologische Informationen zu den Muskeln und der geometrischen Gegebenheiten aus einem hochaufgelösten, kontrastgefärbten μCT-Scan einer Stechrochenhyomandibula verwendet werden. Für die Analyse werden Computer-Aided-Design(CAD)-Modelle und FE-Modelle konstruiert sowie vorhandene Methoden erweitert, um bei den Berechnungen die Charakteristika des biologischen Objektes bestmöglich zu berücksichtigen. Die Modelle bauen auf einer Segmentierung der Hyomandibula auf, wobei die mehreren tausend Tesserae in diesem Datensatz bereits voneinander isoliert sind. Für die Modellierung der Hyomandibula wird als erstes ein CAD-Modell konstruiert. Bei dieser Konstruktion wird eine Tesserae-Mittelfläche erstellt und im Anschluss nach innen und außen verschoben. Der nächste Schritt basiert auf dem Einbau von Zwischenwänden, die die Tesserae voneinander separieren. Auf Grundlage dieses Modells wird ein Tetraedergitter generiert, das die Basis für den zweiten Teil dieser Arbeit darstellt - die Berechnungen mit der FEM. Die wesentliche Aufgabe des zweiten Teils beinhaltet die Konstruktion eines FE-Modells, das in die lineare FEM einzuordnen ist. In dieses fließen die Randbedingungen und die Materialeigenschaften des Skelettelements ein. Mithilfe der FEM lassen sich die durch Krafteinwirkung auftretenden Verschiebungen und Spannungen der Hyomandibula ermitteln. Die Ergebnisse geben Rückschlüsse über das Verhalten des Materials, die Besonderheiten der Geometrie und damit über die Stabilität des Objektes. Der dritte Teil der Abschlussarbeit beschäftigt sich mit zusätzlichen Anpassungen und Änderungen der Modelle (CAD-Modell und FE-Modell), um diese Resultate mit dem Modell zu vergleichen, das der Biologie am nächsten kommt. Diese Anpassungen beinhalten das Variieren der Dicke der mineralisierten Schicht, die Konstellation des Materials und den Abstand zwischen den Tesserae. Die Ergebnisse zeigen, dass sowohl die Tesserae-Struktur als auch die zwischen den Tesserae liegenden Kollagenfasern vermutlich keinen Einfluss auf die Mechanik und dementsprechend die Stabilität haben. Jedoch lassen die unterschiedlichen Resultate im Fall verschieden gewählter Tesserae-Dicken annehmen, dass diese sehr wohl einen Einfluss besitzen. N2 - Sharks and rays are the only vertebrates characterized by a peculiar cartilage skeleton covered with minute mineralized tiles called tesserae. Although this tessellated cartilage has been a defining feature of this lineage for hundreds of millions of years, the functional advantage of this tissue design has remained obscure. In this Master’s thesis, the finite element method (FEM) is used to investigate the role of tiling in the skeleton, using biological information on the muscles and shape from a high-resolution, contrast-stained μCT-scan of a stingray hyomandibula. For this purpose, computer aided design (CAD) models and FE models are constructed and existing methods will be extended to take the best possible account of the characteristics of the biological object. The analysis builds from a segmentation of the hyomandibula, with the dataset’s several thousand tesserae pre-isolated from one another. For the modeling of the hyomandibula a CAD model is constructed. In this construction, a medial surface is created using the tesserae which is subsequently moved to the inside and outside. The next step is to integrate partition walls separating the tesserae elements. Based on this model, a tetrahedral grid is then generated, which is the content of the second part of this thesis, the calculation with the FEM. A finite element model is constructed including boundary conditions and material properties of the skeletal element to compute the results using the linear FEM theory. The FEM is used to determine the displacements and stresses resulting from biological forces acting on the hyomandibula. The results allow conclusions of the material behavior, geometric characteristics (tesselation) and therefore the object stability. Important contributions of this thesis are additional adjustments and changes to the models (CAD model and FE model) to make it more appropriate to study the biological data at hand. The tesserae thickness, the length of the collagenious fibres and the constellation of the material are the parameters, which are changed. In contrast to the tesserae thicknesses, the results suggest that both the arrangement of the tesserae and its interposed collagen fibers have no substantial influence on the mechanics. Y1 - 2018 ER - TY - THES A1 - Weltsch, André T1 - Fast Approximation of Equations of transient Gasflow Y1 - 2018 ER - TY - CHAP A1 - Inanlouganji, A. A1 - Pedrielli, G. A1 - Fainekos, G. A1 - Pokutta, Sebastian T1 - Continuous Simulation Optimization with Model Mismatch Using Gaussian Process Regression T2 - Proceedings of the 2018 Winter Simulation Conference Y1 - 2018 ER - TY - CHAP A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - Efficient algorithms for robust submodular maximization under matroid constraints T2 - ICML Workshop Paper Y1 - 2018 N1 - Additional Note: https://arxiv.org/abs/1807.09405 N1 - URL of the PDF: https://sites.google.com/view/icml2018nonconvex/papers ER - TY - JOUR A1 - Le Bodic, P. A1 - Pfetsch, Marc A1 - Pavelka, J. A1 - Pokutta, Sebastian T1 - Solving MIPs via Scaling-based Augmentation JF - Discrete Optimization Y1 - 2018 N1 - Additional Note: doi: 10.1016/j.disopt.2017.08.004 N1 - URL of the PDF: http://dx.doi.org/10.1016/j.disopt.2017.08.004 VL - 27 SP - 1 EP - 25 ER - TY - JOUR A1 - Braun, Gábor A1 - Roy, Aurko A1 - Pokutta, Sebastian T1 - Stronger Reductions for Extended Formulations JF - to appear in Mathematical Programming B Y1 - 2018 N1 - Additional Note: available at \url{http://arxiv.org/abs/1512.04932} ER - TY - JOUR A1 - Song, R. A1 - Xie, Y. A1 - Pokutta, Sebastian T1 - On the effect of model mismatch for sequential Info-Greedy Sensing JF - EURASIP Journal on Advances in Signal Processing Y1 - 2018 N1 - URL of the PDF: https://asp-eurasipjournals.springeropen.com/articles/10.1186/s13634-018-0551-y ER - TY - CHAP A1 - Paetsch, Olaf T1 - Möglichkeiten und Grenzen automatischer Merkmalserkennung am Beispiel von Risserkennungen in 3D-CT-Aufnahmen von Betonproben N2 - Die Auswertungen der großen Datenmengen moderner bildgebender Verfahren der ZfP können manuell kaum noch bewältigt werden. Hochauflösende 3D-CT-Aufnahmen bestehen oft aus über 1000 Schichtbildern mit einer Datenmenge von mehreren Gigabytes. Aktuelle Computer können diese zwar problemlos visualisieren und erlauben somit eine visuelle Inspektion, aber die möglichst vollständige Erkennung bestimmter Merkmale in den Daten und deren qualitative wie quantitative Auswertung ist durch Experten manuell nicht mehr zu bewältigen. Das gilt insbesondere im Kontext der Schadensaufklärung für die quantitative Analyse verschiedenartig induzierter Risse in Betonen (z.B. durch mechanische Belastungen sowie Frost, Sulfat und Alkali-Kieselsäure-Reaktion). Eine dazu notwendige Segmentierung und Merkmalserkennung kann nur automatisch durchgeführt werden. Dabei ergibt sich (auch fast automatisch) die Frage nach der Verlässlichkeit der verwendeten Algorithmen. Inwieweit kann man davon ausgehen, dass alle gesuchten Merkmale auch tatsächlich gefunden worden sind? Sind die gefundenen Merkmale quantitativ auswertbar und wie wirken sich Parameteränderungen auf die Ergebnisse aus? Sollten immer dieselben, einmal mit gutem Ergebnis angewandten, Parameter auch bei anderen Proben zur besseren Vergleichbarkeit genutzt werden? Anhand eines Risserkennungsalgorithmus basierend auf Formerkennung und Bildverarbeitung wird die Problematik diskutiert. Als Grundlage zur Bewertung des Ansatzes dienen 3D-CT-Aufnahmen von geschädigten Betonprobekörpern und Datensätze, in denen sich aufgrund ihres homogenen Aufbaus mit einfachen Mitteln Risse sicher und eindeutig erkennen lassen. Zur Auswertung der erkannten Risse gehört auch deren Einbettung in das umliegende Material. Das erfordert neben einer automatischen Risserkennung auch eine Segmentierung des gesamten Probekörpers in Zementsteinmatrix, Gesteinskörnung und Porenraum. Da eine solche Segmentierung aufgrund der Datenmenge nur schwer manuell erfolgen kann, werden erste Ergebnisse aus einer Segmentierung mit Hilfe selbstlernender Convolutional Neural Networks gezeigt. Y1 - 2018 PB - iCT 2019 CY - https://www.ndt.net/article/ctc2019/papers/iCT2019_Full_paper_29.pdf ER - TY - JOUR A1 - Chen, Ying A1 - Chua, Wee Song A1 - Koch, Thorsten T1 - Forecasting day-ahead high-resolution natural-gas demand and supply in Germany JF - Applied Energy N2 - Forecasting natural gas demand and supply is essential for an efficient operation of the German gas distribution system and a basis for the operational decisions of the transmission system operators. The German gas market is moving towards more short-term planning, in particular, day-ahead contracts. This increases the difficulty that the operators in the dispatching centre are facing, as well as the necessity of accurate forecasts. This paper presents a novel predictive model that provides day-ahead forecasts of the high resolution gas flow by developing a Functional AutoRegressive model with eXogenous variables (FARX). The predictive model allows the dynamic patterns of hourly gas flows to be described in a wide range of historical profiles, while also taking the relevant determinants data into account. By taking into account a richer set of information, FARX provides stronger performance in real data analysis, with both accuracy and high computational efficiency. Compared to several alternative models in out-of-sample forecasts, the proposed model can improve forecast accuracy by at least 12% and up to 5-fold for one node, 3% to 2-fold and 2-fold to 4-fold for the other two nodes. The results show that lagged 1-day gas flow and nominations are important predictors, and with their presence in the forecast model, temperature becomes insignificant for short-term predictions. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1016/j.apenergy.2018.06.137 IS - Volume 228 SP - 1091 EP - 1110 ER - TY - THES A1 - Scheizel, Jenia T1 - A fast Flow based Heuristic for MIP modelled SCM Problems Y1 - 2018 ER - TY - JOUR A1 - Berthold, Timo A1 - Farmer, James A1 - Heinz, Stefan A1 - Perregaard, Michael T1 - Parallelization of the FICO Xpress Optimizer JF - Optimization Methods and Software N2 - Computing hardware has mostly thrashed out the physical limits for speeding up individual computing cores. Consequently, the main line of progress for new hardware is growing the number of computing cores within a single CPU. This makes the study of efficient parallelization schemes for computation-intensive algorithms more and more important. A natural precondition to achieving reasonable speedups from parallelization is maintaining a high workload of the available computational resources. At the same time, reproducibility and reliability are key requirements for software that is used in industrial applications. In this paper, we present the new parallelization concept for the state-of-the-art MIP solver FICO Xpress-Optimizer. MIP solvers like Xpress are expected to be deterministic. This inevitably results in synchronization latencies which render the goal of a satisfying workload a challenge in itself. We address this challenge by following a partial information approach and separating the concepts of simultaneous tasks and independent threads from each other. Our computational results indicate that this leads to a much higher CPU workload and thereby to an improved, almost linear, scaling on modern high-performance CPUs. As an added value, the solution path that Xpress takes is not only deterministic in a fixed environment, but also, to a certain extent, thread-independent. This paper is an extended version of Berthold et al. [Parallelization of the FICO Xpress-Optimizer, in Mathematical Software – ICMS 2016: 5th International Conference, G.-M. Greuel, T. Koch, P. Paule, and A. Sommere, eds., Springer International Publishing, Berlin, 2016, pp. 251–258] containing more detailed technical descriptions, illustrative examples and updated computational results. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1333612 VL - 33 IS - 3 SP - 518 EP - 529 ER - TY - CHAP A1 - Péron, Martin A1 - Bartlett, Peter L. A1 - Becker, Kai-Helge A1 - Helmstedt, Kate A1 - Chadès, Iadine T1 - Two Approximate Dynamic Programming Algorithms for Managing Complete SIS Networks T2 - COMPASS '18 Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies N2 - Inspired by the problem of best managing the invasive mosquito Aedes albopictus across the 17 Torres Straits islands of Australia, we aim at solving a Markov decision process on large Susceptible-Infected-Susceptible (SIS) networks that are highly connected. While dynamic programming approaches can solve sequential decision-making problems on sparsely connected networks, these approaches are intractable for highly connected networks. Inspired by our case study, we focus on problems where the probability of nodes changing state is low and propose two approximate dynamic programming approaches. The first approach is a modified version of value iteration where only those future states that are similar to the current state are accounted for. The second approach models the state space as continuous instead of binary, with an on-line algorithm that takes advantage of Bellman's adapted equation. We evaluate the resulting policies through simulations and provide a priority order to manage the 17 infested Torres Strait islands. Both algorithms show promise, with the continuous state approach being able to scale up to high dimensionality (50 nodes). This work provides a successful example of how AI algorithms can be designed to tackle challenging computational sustainability problems. Y1 - 2018 U6 - https://doi.org/10.1145/3209811.3209814 PB - ACM ER - TY - BOOK A1 - Abbink, Erwin A1 - Bärmann, Andreas A1 - Bešinovic, Nikola A1 - Bohlin, Markus A1 - Cacchiani, Valentina A1 - Caimi, Gabrio A1 - de Fabris, Stefano A1 - Dollevoet, Twan A1 - Fischer, Frank A1 - Fügenschuh, Armin A1 - Galli, Laura A1 - Goverde, Rob M.P. A1 - Hansmann, Ronny A1 - Homfeld, Henning A1 - Huisman, Dennis A1 - Johann, Marc A1 - Klug, Torsten A1 - Törnquist Krasemann, Johanna A1 - Kroon, Leo A1 - Lamorgese, Leonardo A1 - Liers, Frauke A1 - Mannino, Carlo A1 - Medeossi, Giorgio A1 - Pacciarelli, Dario A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schmidt, Marie A1 - Schöbel, Anita A1 - Schülldorf, Hanno A1 - Stieber, Anke A1 - Stiller, Sebastian A1 - Toth, Paolo A1 - Zimmermann, Uwe ED - Borndörfer, Ralf ED - Klug, Torsten ED - Lamorgese, Leonardo ED - Mannino, Carlo ED - Reuther, Markus ED - Schlechte, Thomas T1 - Handbook of Optimization in the Railway Industry N2 - This book promotes the use of mathematical optimization and operations research methods in rail transportation. The editors assembled thirteen contributions from leading scholars to present a unified voice, standardize terminology, and assess the state-of-the-art. There are three main clusters of articles, corresponding to the classical stages of the planning process: strategic, tactical, and operational. These three clusters are further subdivided into five parts which correspond to the main phases of the railway network planning process: network assessment, capacity planning, timetabling, resource planning, and operational planning. Individual chapters cover: Simulation Capacity Assessment Network Design Train Routing Robust Timetabling Event Scheduling Track Allocation Blocking Shunting Rolling Stock Crew Scheduling Dispatching Delay Propagation Y1 - 2018 SN - 978-3-319-72152-1 U6 - https://doi.org/10.1007/978-3-319-72153-8 VL - 268 PB - Springer Verlag ER - TY - CHAP A1 - Berthold, Timo A1 - Perregaard, Michael A1 - Mészáros, Csaba T1 - Four Good Reasons to Use an Interior Point Solver Within a MIP Solver T2 - Kliewer N., Ehmke J., Borndörfer R. (eds) Operations Research Proceedings 2017 N2 - “Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex” This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_22 SP - 159 EP - 164 ER - TY - THES A1 - Dill, Sabrina Patricia T1 - Joint Feature Learning and Classification - Deep Learning for Surgical Phase Detection Y1 - 2018 ER - TY - JOUR A1 - Hettich, G. A1 - Schierjott, R. A. A1 - Schilling, C. A1 - Maas, A. A1 - Ramm, Heiko A1 - Bindernagel, Matthias A1 - Lamecker, Hans A1 - Grupp, T. M. T1 - Validation of a Statistical Shape Model for Acetabular Bone Defect Analysis JF - ISTA 2018 London Abstract Book N2 - Acetabular bone defects are still challenging to quantify. Numerous classification schemes have been proposed to categorize the diverse kinds of defects. However, these classification schemes are mainly descriptive and hence it remains difficult to apply them in pre-clinical testing, implant development and pre-operative planning. By reconstructing the native situation of a defect pelvis using a Statistical Shape Model (SSM), a more quantitative analysis of the bone defects could be performed. The aim of this study is to develop such a SSM and to validate its accuracy using relevant clinical scenarios and parameters. Y1 - 2018 ER - TY - GEN A1 - Plöntzke, Julia A1 - Berg, Mascha A1 - Röblitz, Susanna T1 - A mathematical modelling approach to the insight of dynamic networks: Potassium homeostasis and glucose-insulin in dairy cows T2 - ADSA 2018 Annual Meeting N2 - Lactating dairy cows require a particular composition of nutritional ingredients depending on their production status. The optimal supply of energy and minerals in diet, one of them potassium, is indispensable for the prevention of disbalances like hypokalemia or hypoglycaemia. Potassium balance in cows is the result of potassium intake, distribution in the organism, and excretion, and closely interacts with glucose and electrolyte metabolism, in which postpartum veterinary treatments frequently intervene. We present a mechanistic, dynamic model for potassium balance together with a glucose insulin model in non-lactating and lactating dairy cows based on ordinary differential equations. Parameter values were obtained from data of a clinical trial as well as from literature. To verify the mechanistic functioning of the model, we validate the model by comparing simulation outcomes with clinical study findings. Furthermore we perform numerical experiments and compare them with expected behaviour according to mechanistic knowledge. The results give insight into the dynamic behaviour of the network and open the way for further open questions and hypothesis to be tested. Y1 - 2018 UR - https://www.adsa.org/Portals/0/SiteContent/Docs/Meetings/PastMeetings/Annual/2018/223.pdf VL - 101 Suppl. 2 SP - 226 EP - 227 PB - American Dairy Science Association ET - Journal of Dairy Science ER - TY - JOUR A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming JF - Mathematical Programming Computation N2 - Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP. Y1 - 2018 ER - TY - JOUR A1 - Wende, Florian A1 - Marsman, Martijn A1 - Kim, Jeongnim A1 - Vasilev, Fedor A1 - Zhao, Zhengji A1 - Steinke, Thomas T1 - OpenMP in VASP: Threading and SIMD JF - International Journal of Quantum Chemistry N2 - The Vienna Ab initio Simulation Package (VASP) is a widely used electronic structure code that originally exploits process-level parallelism through the Message Passing Interface (MPI) for work distribution within and across nodes. Architectural changes of modern parallel processors urge programmers to address thread- and data-level parallelism as well to benefit most from the available compute resources within a node. We describe for VASP how to approach for an MPI + OpenMP parallelization including data-level parallelism through OpenMP SIMD constructs together with a generic high-level vector coding scheme. We can demonstrate an improved scalability of VASP and more than 20% gain over the MPI-only version, as well as a 2x increased performance of collective operations using the multiple-endpoint MPI feature. The high-level vector coding scheme applied to VASP's general gradient approximation routine gives up 9x performance gain on AVX512 platforms with the Intel compiler. Y1 - 2018 U6 - https://doi.org/10.1002/qua.25851 IS - Emerging Architectures in Computational Chemistry SP - e25851 PB - Wiley Online Library ER - TY - CHAP A1 - Dalitz, Wolfgang A1 - Chrapary, Hagen T1 - Software Products, Software Versions, Archiving of Software, and swMATH T2 - Mathematical Software – ICMS 2018 N2 - Management of software information is difficult for various reasons. First, software typically cannot be reduced to a single object: information about software is an aggregate of software code, APIs, documentation, installations guides, tutorials, user interfaces, test data, dependencies on hardware and other software, etc. Moreover, secondary information about software, especially use cases and experience with employing the software, is important to communicate. Second, typically named software, which we term here a `software product', is taken to stand for all versions of the software which can have different features and properties and may produced different results from the same input data. Software production is a dynamic process and software development is, increasingly, widely distributed. Therefore GitHub, GitLab, Bitbucket and other platforms for sharing are used. Information about software is alos provided in different locations, on websites, repositories, portals, etc. Each resource provides information about software from a particular point of view, but the information is often not linked together. Therefore swMATH has developed a conception which covers portals and a search engines for mathematical software, persistent and citable landing pages for specific software, and a method for software archiving. Based on the publication-based approach, swMATH collects and analyses semi-automatically the existing information about mathematical software found on the Web and makes it available in a user-oriented way. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-96418-8_15 SP - 123 EP - 127 ER - TY - CHAP A1 - Dalitz, Wolfgang A1 - Chrapary, Hagen A1 - Sperber, Wolfram T1 - Software Knowledge Management and swMATH T2 - Fachgruppe Didaktik der Mathematik der Universität Paderborn N2 - Mathematische Software ist heute ein weitverbreitetes Werkzeug in der Forschung, aber auch in der mathematischen Bildung. Die Anzahl mathematischer Softwareprodukte wächst, nicht zuletzt durch die Anforderungen der Anwender, stark. Anders als für mathematische Publikationen sind für das Management mathematischer Software viele Fragen offen und werden noch diskutiert, etwa die Standardisierung von Software Zitationen. Der Aufbau einer effizienten Infrastruktur für Software ist eine notwendige Voraussetzung für die Überprüfung von Forschungsergebnissen, die mittels Software erzielt worden sind und wichtig für die Entscheidung, ob eine bestimmte Software zur Lösung eines Problems verwendet werden soll. Das swMATH [1] Portal gibt einen weitgehend vollständigen Überblick über die existierende mathematische Software. Es ist ein Dienst entstanden, der automatisiert die im Web vorhandenen Informationen zu einer Software identifiziert, auswertet und verfügbar macht. Der Dienst soll insbesondere durch die Verknüpfung mit anderen Quellen, etwa dem Internet Archive, persistente Informationen über ein Software Produkt und dessen Versionen liefern. Y1 - 2018 U6 - https://doi.org/10.17877/DE290R-19281 SP - 401 EP - 404 ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakayama, Yuki A1 - Wakui, Tetsuya T1 - Model Reduction by Time Aggregation for Optimal Design of Energy Supply Systems by an MILP Hierarchical Branch and Bound Method T2 - Proceedings of the 31st International Conference on Efficiency, Cost, Optimization, Simulation and Environmental Impact of Energy Systems (ECOS 2018) N2 - Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems effi- ciently. An original problem has been solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of one another at the lower level. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. In this paper, a method of reducing model by time aggregation is proposed as a novel strategy to search design candidates efficiently in the relaxed optimal design problem at the upper level. In addition, the previous strategies are modified in accordance with the novel strategy. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solu- tion. The method can decrease the number of design variables and constraints at the upper level, and thus may decrease the computation time at the upper level. Through a case study on the optimal design of a gas turbine cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency in comparison and combination with the modified previous strategies. Y1 - 2018 ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakayamaa, Yuji A1 - Wakui, Tetsuya T1 - Optimal Design of a Gas Turbine Cogeneration Plant by a Hierarchical Optimization Method With Parallel Computing T2 - ASME Turbo Expo 2018: Turbomachinery Technical Conference and Exposition N2 - 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. Mixed-integer linear programming (MILP) approaches have been applied widely to such optimal design problems. The authors have proposed a MILP method utilizing the hierarchical relationship between design and operation variables to solve the optimal design problems of energy supply systems efficiently. In addition, some strategies to enhance the computation efficiency have been adopted: bounding procedures at both the levels and ordering of the optimal operation problems at the lower level. In this paper, as an additional strategy to enhance the computation efficiency, parallel computing is adopted to solve multiple optimal operation problems in parallel at the lower level. In addition, the effectiveness of each and combinations of the strategies adopted previously and newly is investigated. This hierarchical optimization method is applied to an optimal design of a gas turbine cogeneration plant, and its validity and effectiveness are clarified through some case studies. Y1 - 2018 UR - http://proceedings.asmedigitalcollection.asme.org/proceeding.aspx?articleid=2700845 VL - 3 ER - TY - CHAP A1 - Anderson, Daniel A1 - Hendel, Gregor A1 - Le Bodic, Pierre A1 - Viernickel, Jan Merlin T1 - Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation T2 - AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence N2 - We propose a simple and general online method to measure the search progress within the branch-and-bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases. Y1 - 2018 ER - TY - JOUR A1 - Zhang, Wei A1 - Hartmann, Carsten A1 - von Kleist, Max T1 - Optimal control of Markov jump processes: Asymptotic analysis, algorithms and applications to the modeling of chemical reaction systems JF - Communications in Mathematical Sciences N2 - Markov jump processes are widely used to model natural and engineered processes. In the context of biological or chemical applications one typically refers to the chemical master equation (CME), which models the evolution of the probability mass of any copy-number combination of the interacting particles. When many interacting particles (“species”) are considered, the complexity of the CME quickly increases, making direct numerical simulations impossible. This is even more problematic when one aims at controlling the Markov jump processes defined by the CME. In this work, we study both open loop and feedback optimal control problems of the Markov jump processes in the case that the controls can only be switched at fixed control stages. Based on Kurtz’s limit theorems, we prove the convergence of the respective control value functions of the underlying Markov decision problem as the copy numbers of the species go to infinity. In the case of the optimal control problem on a finite time-horizon, we propose a hybrid control policy algorithm to overcome the difficulties due to the curse of dimensionality when the copy number of the involved species is large. Two numerical examples demonstrate the suitability of both the analysis and the proposed algorithms. Y1 - 2018 U6 - https://doi.org/10.4310/CMS.2018.v16.n2.a1 SP - 293 EP - 331 ER - TY - JOUR A1 - Deuflhard, Peter T1 - The Grand Four. Affine Invariant Globalizations of Newton's Method JF - Vietnam Journal of Mathematics Y1 - 2018 U6 - https://doi.org/10.1007/s10013-018-0301-3 VL - 46 IS - 4 SP - 761 EP - 777 ER - TY - JOUR A1 - Lorenz-Spreen, Philipp A1 - Wolf, Frederik A1 - Braun, Jonas A1 - Ghoshal, Gourab A1 - Djurdjevac Conrad, Natasa A1 - Hövel, Philipp T1 - Tracking online topics over time: understanding dynamic hashtag communities JF - Computational Social Networks N2 - Background: Hashtags are widely used for communication in online media. As a condensed version of information, they characterize topics and discussions. For their analysis, we apply methods from network science and propose novel tools for tracing their dynamics in time-dependent data. The observations are characterized by bursty behaviors in the increases and decreases of hashtag usage. These features can be reproduced with a novel model of dynamic rankings. Hashtag communities in time: We build temporal and weighted co-occurrence networks from hashtags. On static snapshots, we infer the community structure using customized methods. On temporal networks, we solve the bipartite matching problem of detected communities at subsequent timesteps by taking into account higher-order memory. This results in a matching protocol that is robust toward temporal fluctuations and instabilities of the static community detection. The proposed methodology is broadly applicable and its outcomes reveal the temporal behavior of online topics. Modeling topic-dynamics: We consider the size of the communities in time as a proxy for online popularity dynamics. We find that the distributions of gains and losses, as well as the interevent times are fat-tailed indicating occasional, but large and sudden changes in the usage of hashtags. Inspired by typical website designs, we propose a stochastic model that incorporates a ranking with respect to a time-dependent prestige score. This causes occasional cascades of rank shift events and reproduces the observations with good agreement. This offers an explanation for the observed dynamics, based on characteristic elements of online media. Y1 - 2018 U6 - https://doi.org/10.1186/s40649-018-0058-6 VL - 5 IS - 9 ER - TY - JOUR A1 - Agudo Jácome, Leonardo A1 - Hege, Hans-Christian A1 - Paetsch, Olaf A1 - Pöthkow, Kai T1 - Three-dimensional reconstruction and quantification of dislocation substructures from transmission electron microscopy stereo pairs JF - Ultramicroscopy N2 - A great amount of material properties is strongly influenced by dislocations, the carriers of plastic deformation. It is therefore paramount to have appropriate tools to quantify dislocation substructures with regard to their features, e.g., dislocation density, Burgers vectors or line direction. While the transmission electron microscope (TEM) has been the most widely-used equipment implemented to investigate dislocations, it usually is limited to the two-dimensional (2D) observation of three-dimensional (3D) structures. We reconstruct, visualize and quantify 3D dislocation substructure models from only two TEM images (stereo pairs) and assess the results. The reconstruction is based on the manual interactive tracing of filiform objects on both images of the stereo pair. The reconstruction and quantification method are demonstrated on dark field (DF) scanning (S)TEM micrographs of dislocation substructures imaged under diffraction contrast conditions. For this purpose, thick regions (>300 nm) of TEM foils are analyzed, which are extracted from a Ni-base superalloy single crystal after high temperature creep deformation. It is shown how the method allows 3D quantification from stereo pairs in a wide range of tilt conditions, achieving line length and orientation uncertainties of 3% and 7°, respectively. Parameters that affect the quality of such reconstructions are discussed. Y1 - 2018 U6 - https://doi.org/10.1016/j.ultramic.2018.08.015 VL - 195 SP - 157 EP - 170 ER - TY - THES A1 - Helfmann, Luzie T1 - Stochastic Modeling of Interacting Agent Systems Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71887 ER - TY - JOUR A1 - Kork, F. A1 - Spies, Claudia A1 - Conrad, Tim A1 - Weiss, B. A1 - Roenneberg, T. A1 - Wernecke, K.-D. A1 - Balzer, Felix T1 - Associations of postoperative mortality with the time of day, week and year JF - Anaesthesia Y1 - 2018 ER - TY - JOUR A1 - Obermeier, Patrick A1 - Heim, A. A1 - Biere, Barbara A1 - Hage, E. A1 - Alchikh, Maren A1 - Conrad, Tim A1 - Schweiger, Brunhilde A1 - Rath, Barbara T1 - Clinical characteristics and disease severity associated with adenovirus infections in infants and children - discovery of a novel adenovirus, HAdV-D80 JF - Clinical Infectious Diseases Y1 - 2018 ER - TY - THES A1 - Anderson, Lovis T1 - The Computation of the Volume of the Union of Polytopes via a Sweep-Plane Algorithm N2 - Das Thema dieser Arbeit ist ein Volumen-Algorithmus für die Vereinigung von Polytopen. Der Algorithmus basiert auf der Arbeit von Bieri und Nef. Er berechnet das Volumen der Vereinigung von Polytopen mit einem Sweep-Verfahren. Dabei wird eine Hyperebene im Raum verschoben und das Volumen auf der einen Seite der Hyperebene berechnet. Umso weiter die Hyperebene verschobe wird, desto größer ist auch der Halbraum. Unser Algorithmus berechnet das Volumen einer Vereinigung von Polytopen geschnitten mit dem Halbraum der Sweep-Ebene als eine Funktion abhängig von der Veschiebung. Ab einem gewissen Punkt liegt der Körper dabei komplett im Halbraum der Sweep-Ebene und das Volumen bleibt konstant. Unser Algorithmus unterscheidet sich in zwei Punkten von dem Algorithmus von Bieri und Nef. Erstens funktioniert er nur auf der Vereinigung von Polytopen, wohingegen der Algorithmus von Bieri und Nef für Nef-Polyeder funktioniert. Diese sind eine Verallgemeinerung von Polyedern, die auch die Klasse der Vereinigung von Polytopen umfasst. Für uns ist das allerdings kein Nachteil, da unsere Datensätze zu Vereinigungen von Polytopen führen. Zweitens ist unser Algorithmus in zwei Teile aufgeteilt. Im ersten Teil wird eine Datenstruktur entwickelt, aus der im zweiten Teil zusammen mit einer Richtung die Sweep-Ebenen-Volumenfunktion berechnet wird. Der Großteil der Komplexität liegt im ersten Teil des Algorithmus. Das hat den Vorteil, dass wir die Volumenfunktionen für viele verschiedene Richtungen berechnen können. So können Einblicke in die Struktur des Körpers gewonnen werden. Der Algorithmus beruht auf zwei verschiedenen Zerlegungsansätzen. Zuerst können wir mit Hilfe von Anordnungen von Hyperebenen eine Vereinigung von Polytopen in ihre Zellen zerlegen. Dabei berufen wir uns auf die Arbeit von Gerstner und Holtz, in der das Konzept der Positionsvektoren eingeführt wird. Diese nutzen wir um die Ecken und ihre benachbarten Zellen zu bestimmen. So erhalten wir eine Zerlegung unserer Vereinigung in Zellen, deren paarweise Schnitte kein Volumen haben. Das zweite Zerlegungskonzept ist die konische Zerlegung, wie sie von Lawrence eingeführt wurde. Mit Hilfe dieser können wir die Indikatorfunktion eines Polytops als die Summe der Indikatorfunktionen seiner Vorwärtskegel schreiben. Die Sweep-Ebenen Volumenfunktionen können dann leicht mit Hilfe einer altbekannten Formel für das Volumen von Simplices berechnet werden. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71829 ER - TY - JOUR A1 - Dartsch, Maria A1 - Dulski, Sebastian A1 - Engels, Frauke A1 - Gran, Meike A1 - Kende, Jiri A1 - Lohrum, Stefan A1 - Porth, Robert A1 - Ristau, Ute A1 - Rüter, Christian A1 - Sabisch, Andreas A1 - Stumm, Birgit A1 - Taylor, Viola A1 - Voß, Michael T1 - Einführung des cloudbasierten Bibliothekssystems Alma in Berlin – ein Erfahrungsbericht JF - ABI Technik - Zeitschrift für Automation, Bau und Technik im Archiv-, Bibliotheks- und Informationswesen N2 - Die enge Zusammenarbeit der vier Berliner Universitätsbibliotheken1 reicht weit zurück. Bereits vor der Jahrtausendwende haben die Berliner Universitätsbibliotheken (UBs) gemeinsam das Bibliothekssystem Aleph 500 ausgewählt und implementiert, danach folgten weitere Systeme – das Linking System SFX, die Digitale Bibliothek MetaLib und das Bibliotheksportal Primo. Es war daher folgerichtig und selbstverständlich, dass auch die Auswahl und Implementierung eines neuen Bibliothekssystems in enger Abstimmung und Zusammenarbeit erfolgte. Die Erfahrungen bei Vertragsverhandlungen und Implementierung von Alma sind Gegenstand des folgenden Berichtes. N2 - As regards implementing new library technology, the Berlin University libraries have been working closely together for more than 20 years. It was the case for the implementation of the legacy system Aleph 500, the linking system SFX, the digital library MetaLib and the library portal Primo, and therefore it was a matter of course to continue the close cooperation during the implementation of the new cloud-based library system, too. The experience gained during the contract negotiations and the implementation project, and lessons learned are the focus of this report. Y1 - 2018 U6 - https://doi.org/10.1515/abitech-2018-2002 VL - 38 IS - 2 SP - 128 EP - 141 ER - TY - THES A1 - Elijazyfer, Ziena T1 - Längenbeschränkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung Y1 - 2018 ER - TY - THES A1 - Schreck, Vanessa T1 - Algorithmic Analysis of the Graph Segmentation Problem Y1 - 2018 ER - TY - THES A1 - Villatoro, José T1 - A combined approach for the analysis of biomolecules using IR-MALDI ion mobility spectrometry and molecular dynamics simulations of peptide ions in the gas phase Y1 - 2018 ER - TY - THES A1 - Klimm, Martina T1 - New Strategies in Conformation Dynamics Y1 - 2018 ER - TY - THES A1 - Quer, Jannes T1 - Importance Sampling for metastable dynamical systems in molecular dynamics Y1 - 2018 ER - TY - THES A1 - Reuter, Bernhard T1 - Generalisierte Markov-Modellierung von Nichtgleichgewichtssystemen - Simulation und Modellierung der Amyloid-beta(1-40)-Konformationsdynamik unter Mikrowelleneinfluss Y1 - 2018 ER - TY - JOUR A1 - Alchikh, Maren A1 - Conrad, Tim A1 - Hoppe, Christian A1 - Ma, Xiaolin A1 - Broberg, Eeva K. A1 - Penttinen, P. A1 - Reiche, J. A1 - Biere, Barbara A1 - Schweiger, Brunhilde A1 - Rath, Barbara T1 - Are we missing respiratory viral infections in infants and children? Comparison of a hospital-based quality management system with standard of care. Clinical Microbiology and Infection JF - Clinical Microbiology and Infection Y1 - 2018 U6 - https://doi.org/10.1016/j.cmi.2018.05.023 IS - 06/18 SP - 1 EP - 1 ER - TY - JOUR A1 - Mireles, Victor A1 - Conrad, Tim T1 - Reusable building blocks in biological systems JF - Journal of the Royal Society Interface N2 - One of the most widely recognized features of biological systems is their modularity. The modules that constitute biological systems are said to be redeployed and combined across several conditions, thus acting as building blocks. In this work, we analyse to what extent are these building blocks reusable as compared with those found in randomized versions of a system. We develop a notion of decompositions of systems into phenotypic building blocks, which allows them to overlap while maximizing the number of times a building block is reused across several conditions. Different biological systems present building blocks whose reusability ranges from single use (e.g. condition specific) to constitutive, although their average reusability is not always higher than random equivalents of the system. These decompositions reveal a distinct distribution of building block sizes in real biological systems. This distribution stems, in part, from the peculiar usage pattern of the elements of biological systems, and constitutes a new angle to study the evolution of modularity. Y1 - 2018 U6 - https://doi.org/10.1098/rsif.2018.0595 VL - 15 IS - 149 SP - 1 EP - 10 ER - TY - JOUR A1 - Ma, Xiaolin A1 - Conrad, Tim A1 - Alchikh, Maren A1 - Reiche, J. A1 - Schweiger, Brunhilde A1 - Rath, Barbara T1 - Can we distinguish respiratory viral infections based on clinical features? A prospective pediatric cohort compared to systematic literature review JF - Medical Virology N2 - Studies have shown that the predictive value of “clinical diagnoses” of influenza and other respiratory viral infections is low, especially in children. In routine care, pediatricians often resort to clinical diagnoses, even in the absence of robust evidence‐based criteria. We used a dual approach to identify clinical characteristics that may help to differentiate infections with common pathogens including influenza, respiratory syncytial virus, adenovirus, metapneumovirus, rhinovirus, bocavirus‐1, coronaviruses, or parainfluenza virus: (a) systematic review and meta‐analysis of 47 clinical studies published in Medline (June 1996 to March 2017, PROSPERO registration number: CRD42017059557) comprising 49 858 individuals and (b) data‐driven analysis of an inception cohort of 6073 children with ILI (aged 0‐18 years, 56% male, December 2009 to March 2015) examined at the point of care in addition to blinded PCR testing. We determined pooled odds ratios for the literature analysis and compared these to odds ratios based on the clinical cohort dataset. This combined analysis suggested significant associations between influenza and fever or headache, as well as between respiratory syncytial virus infection and cough, dyspnea, and wheezing. Similarly, literature and cohort data agreed on significant associations between HMPV infection and cough, as well as adenovirus infection and fever. Importantly, none of the abovementioned features were unique to any particular pathogen but were also observed in association with other respiratory viruses. In summary, our “real‐world” dataset confirmed published literature trends, but no individual feature allows any particular type of viral infection to be ruled in or ruled out. For the time being, laboratory confirmation remains essential. More research is needed to develop scientifically validated decision models to inform best practice guidelines and targeted diagnostic algorithms. Y1 - 2018 U6 - https://doi.org/10.1002/rmv.1997 VL - 28 IS - 5 SP - 1 EP - 12 ER - TY - GEN ED - Borndörfer, Ralf ED - Storandt, Sabine T1 - Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems N2 - Running and optimizing transportation systems give rise to very complex and large-scale optimization problems requiring innovative solution techniques and ideas from mathematical optimization, theoretical computer science, and operations research. Since 2000, the series of Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) workshops brings together researchers and practitioners who are interested in all aspects of algorithmic methods and models for transportation optimization and provides a forum for the exchange and dissemination of new ideas and techniques. The scope of ATMOS comprises all modes of transportation. The 18th ATMOS workshop (ATMOS’18) was held in connection with ALGO’18 and hosted by Aalto University in Helsinki, Finland, on August 23–24, 2018. Topics of interest were all optimization problems for passenger and freight transport, including, but not limited to, demand forecasting, models for user behavior, design of pricing systems, infrastructure planning, multi-modal transport optimization, mobile applications for transport, congestion modelling and reduction, line planning, timetable generation, routing and platform assignment, vehicle scheduling, route planning, crew and duty scheduling, rostering, delay management, routing in road networks, traffic guidance, and electro mobility. Of particular interest were papers applying and advancing techniques like graph and network algorithms, combinatorial optimization, mathematical programming, approximation algorithms, methods for the integration of planning stages, stochastic and robust optimization, online and real-time algorithms, algorithmic game theory, heuristics for real-world instances, and simulation tools. There were twenty-nine submissions from eighteen countries. All of them were reviewed by at least three referees in ninety-one reviews, among them five external ones, and judged on their originality, technical quality, and relevance to the topics of the workshop. Based on the reviews, the program committee selected sixteen submissions to be presented at the workshop (acceptance rate: 55%), which are collected in this volume in the order in which they were presented. Together, they quite impressively demonstrate the range of applicability of algorithmic optimization to transportation problems in a wide sense. In addition, Dennis Huisman kindly agreed to complement the program with an invited talk on Railway Disruption Management: State-of-the-art in practice and new research directions. Based on the reviews, Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner won the Best Paper Award of ATMOS’18 with their paper A simple way to compute the number of vehicles that Are required to operate a periodic timetable. In addition, we awarded Tomas Lidén the Best VGI Paper Award of ATMOS’18 for his paper Reformulations for railway traffic and maintenance planning. We would like to thank the members of the Steering Committee of ATMOS for giving us the opportunity to serve as Program Chairs of ATMOS’18, all the authors who submitted papers, Dennis Huisman for accepting our invitation to present an invited talk, the members of the Program Committee and the additional reviewers for their valuable work in selecting the papers appearing in this volume, our sponsors MODAL, TomTom, and VGIscience for their support of the prizes, and the local organizers for hosting the workshop as part of ALGO’18. We acknowledge the use of the EasyChair system for the great help in managing the submission and review processes, and Schloss Dagstuhl for publishing the proceedings of ATMOS’18 in its OASIcs series. Y1 - 2018 SN - ISBN 978-3-95977-096-5 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2018.0 PB - Dagstuhl Publishing, Saarbrücken/Wadern, Germany ER - TY - JOUR A1 - Reidelbach, Marco A1 - Weber, Marcus A1 - Imhof, Petra T1 - Prediction of perturbed proton transfer networks JF - PLoS ONE N2 - The transfer of protons through proton translocating channels is a complex process, for which direct samplings of different protonation states and side chain conformations in a transition network calculation provide an efficient, bias-free description. In principle, a new transition network calculation is required for every unsampled change in the system of interest, e.g. an unsampled protonation state change, which is associated with significant computational costs. Transition networks void of or including an unsampled change are termed unperturbed or perturbed, respectively. Here, we present a prediction method, which is based on an extensive coarse-graining of the underlying transition networks to speed up the calculations. It uses the minimum spanning tree and a corresponding sensitivity analysis of an unperturbed transition network as initial guess and refinement parameter for the determination of an unknown, perturbed transition network. Thereby, the minimum spanning tree defines a sub-network connecting all nodes without cycles and minimal edge weight sum, while the sensitivity analysis analyzes the stability of the minimum spanning tree towards individual edge weight reductions. Using the prediction method, we are able to reduce the calculation costs in a model system by up to 80%, while important network properties are maintained in most predictions. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1371/journal.pone.0207718 VL - 13 IS - 12 SP - e0207718 EP - e0207718 ER - TY - THES A1 - Nöckel, Celine T1 - Bidirectional A* Search on Time-Dependent Airway Networks N2 - This thesis deals with a new algorithm for finding Shortest Paths on Airway Networks. It is about a Bidirectional A* Search, a Greedy algorithm exploring a network from two sides instead of one. We will use it to solve the so-called 'Horizontal Flight Trajectory Problem', where one searches for an aircraft trajectory between two airports of minimal costs on an Airway Network. The given network will be modeled as a directed graph and in order to reflect reality we concentrate on the dynamic version. Here a timedependent cost function for all arcs is integrated, that shall represent the winds blowing. This way we model the Horizontal Flight Trajectory Problem mathematically as a Time-Dependent Shortest Path Problem. The basic algorithm idea derives from the algorithm presented in 'Bidirectional A* Search on Time-Dependent Road Networks' [1], where a similar setting is elaborated for road networks. The algorithm procedure bears on a modified generalization of Dijkstra's algorithm, made bidirectional and improved in several aspects. As for the backwards search the arrival times are not known in advance, the reversed graph it occurs on has to be weighted by a lower bound. Contrary to the static case the forwards search still has to go on, when they 'meet' in one node. In the static case, the shortest path would have been found at this point. For road networks the TDSPP is well-studied, for airway networks cannot be found as much in literature. In order to test efficiency, we implement Dijkstra's algorithm, unidirectional A* Search and Bidirectional A* Search. We draw up how potential functions for the static case could look like and that with a suitable potential A* Search with works approx. 7 times faster than Dijkstra in the dynamic case. Our computations lead also to the result, that the unidirectional A* Search works even better on the network than our new bidirectional approach does. On average it labels fewer nodes and also yields 1,7 times faster to the solutions. For assessing the efficiency of the different algorithms we compare the running times and to exclude processor characteristics we consider also the set labels relative to the labels on the resulting optimal path. In addition, we present examples of routes visually and explain shortly why there appear local differences regarding performance of A* Search and Bidirectional A* Search. Y1 - 2018 ER - TY - THES A1 - Mett, Fabian T1 - Über die optimale Platzierung von Ladestationen für Elektrobusse N2 - In dieser Arbeit wird die Platzierung von Ladestationen für Elektrobusse untersucht. Dabei soll für eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zunächst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden könnte. Dieses Problem stellt sich als NP-schwer heraus. Für einige einfachere Fällewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur Lösung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station würde ein individueller Wert geladen, so ist das Problem schon für nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazität hinzugefügt und die zuvor entwickelten Algorithmen werden entsprechend angepasst. Für die abschließende Problemdefinition werden verschiedene Batteriegrößen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich größeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt größerer und mehr Ladestationen genutzt werden. Y1 - 2018 ER - TY - THES A1 - Krug, Matthias T1 - Analysis of the Shortest Path Problem with Piecewise Constant Crossing Costs Y1 - 2018 ER - TY - THES A1 - Husemann, Christoph T1 - Multimodales Routing mit Leihfahrradsystemen am Beispiel Berlins N2 - The aim of multimodal routing is to extract the best integrated journey of multiple transportation networks. The integration of bike rental networks is challenging particularly with respect to recognizing a valid path dependent on real-time availability of bike boarding and alighting places. In this work a common model for station-based bike rental networks extended with boarding possibilities for free floating bikes is presented. Moreover a new model for alighting inside a free floating area is introduced. In addition, a prototype of multimodal routing with a bike rental network in Berlin is developed by extending the OpenTripPlanner software. Due to recent public dispute about bike rental networks in Berlin, an examination about speed-up potential of an integrated bike rental network in the public transit of Berlin is provided. Y1 - 2018 ER - TY - THES A1 - Vornberger, Leo T1 - Approximation von Windkomponenten in der Luftfahrt durch lineare Interpolation N2 - Das Wind-Interpolation-Problem (WIP) ist ein bisher selten diskutiertes Problem der Flugplanungsoptimierung, bei dem es darum geht, Wind-Komponenten auf einer Luftstraße zu approximieren. Anhand von Winddaten, die vektoriell an den Gitterpunkten eines den Globus umspannenden Gitters vorliegen, soll bestimmt werden, wie viel Wind entlang der Luftstraße und quer zu ihr weht. Thema dieser Arbeit ist ein Spezialfall des WIP, nämlich das statische WIP auf einer Planfläche (SWIPP). Dazu wird zuerst ein Algorithmus besprochen, der das SWIPP zwar löst, aber einem Ansatz zugrunde liegt, der bei genauerem Hinsehen nicht sinnvoll erscheint: hier wird Wind zwischen vier Punkten interpoliert, wozu es keine triviale Methode gibt. Ähnlich zu diesem Algorithmus, der heute als State-of-the-Art gilt, wird als Ergebnis dieser Arbeit ein neuer Algorithmus vorgestellt, der das SWIPP akkurater und schneller löst. Hier wird deutlich seltener auf die Interpolation zwischen vier Punkten zurückgegriffen - stattdessen wird fast immer linear zwischen zwei Punkten interpoliert. Die Algorithmen zum Lösen des SWIPP werden auf ihre Genauigkeit, asymptotische Laufzeit und Geschwindigkeit untersucht und verglichen. Als Testareal dienen zum einen echte Wetterdaten sowie das Luftstraßennetz, das die Erde umspannt, und zum anderen ein eigens generiertes Windfeld und fiktive Luftstraßen. Es wird gezeigt, dass der hier vorgestellte Algorithmus die State-of-the-Art-Variante in allen genannten Aspekten übertrifft. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71570 ER - TY - THES A1 - Akil, Fatima T1 - Lineare Gleichungssysteme modulo T N2 - Mit dem Voranschreiten der Technologie erhalten die öffentlichen Verkehrsmittel eine größere Bedeutung. Die Beförderung mehrerer Personen eröffnet der Gesellschaft viele Möglichkeiten, unter Anderem den Vorteil der Zeitersparnis. Die Dauer des Verkehrswegs mit öffentlichen Verkehrsmitteln ist häufig geringer, als die mit individuellen Verkehrsmitteln. Jedes öffentliche Transportmittel ist mit einem Fahrplan versehen. Dieser bietet Passagieren, die öffentliche Verkehrsmittel öfter nutzen, eine Strukturierung und Planung ihrer Zeit. Dabei lassen sich Taktfahrpläne aufgrund ihres periodischen Verhaltens leicht einprägen. Dieses periodische Verhalten ist durch mathematische Modellierungen darstellbar. Das persönliche Nutzverhalten vieler Bürger im Personenverkehr ist auf die öffentlichen Verkehrsmittel beschränkt. Diese beinhalten im Gegensatz zum individuellen Verkehrsmittel eine Wartezeit. Dabei stellt sich die Frage, ob man anhand mathematischer Modelle diese Wartezeit minimieren kann. Eine bekannte mathematische Modellierung dieses Problems ist das Periodic Event Scheduling Problem (PESP). Die optimale Planung eines periodischen Taktfahrplanes steht im Vordergrund. Während ich dieses Problem betrachtet habe, wurde ich auf das Rechnen mit linearen Gleichungssystemen modulo T aufmerksam. Bei periodischen Taktfahrplänen wird ein einheitliches zeitliches Muster, welches sich nach T Minuten wiederholt, betrachtet. Das dabei zu betrachtende Lösungsproblem eröffnet ein Teilgebiet der Mathematik, welches bislang nicht im Vordergrund stand: Das Lösen linearer Gleichungen modulo T, wobei T für die Zeit in Minuten steht und somit 60 ist. Da 60 keine Primzahl ist, kann – wie im Laufe der Arbeit präsentiert – das lineare Gleichungssystem nicht mehr über einen Körper gelöst werden. Lineare Gleichungssysteme werden nun über Nicht-Körpern betrachtet. Die Literatur weist sowohl im deutschsprachigem als auch im englischsprachigen Raum wenig Umfang bezüglich linearer Gleichungssysteme über Nicht-Körper auf. Der Bestand an Fachliteratur bezüglich den Themen lineare diophantische Gleichungssysteme, Hermite- Normalform und Smith-Normalform ist zurzeit gering, dennoch erreichbar, beispielsweise in [1], welches in dieser Bachelorarbeit genutzt wurde. Insbesondere wurde ich bei der Suche nach geeigneter Literatur zu linearen Gleichungssystemen über Restklassenringe, die keinen Körper bilden, nicht fündig. Dabei recherchierte ich sowohl in den Universitätsbibliotheken als auch in webbasierenden Suchmaschinen. Aufgrund dem geringen Bestand an Fachliteratur in diesem Kontext, war ich gezwungen, an vielen Stellen eigene logische Verknüpfungen zu konzipieren und zu beweisen. Dies brachte viele Schwierigkeiten mit sich, die mit bestmöglichem Verständnis bearbeitet wurden. Abseits der Zugänglichkeit der Literatur, finde ich es sehr überraschend, dass sich viele Professoren der Mathematik mit diesem Themenbereich nicht beschäftigten. Insbesondere gingen von den Dozenten, die ich um Literaturempfehlung bat, kein Werk aus. Damit wurde das Thema "Lineare Gleichungssysteme Modulo T" einerseits eine große Herausforderung, andererseits eine große Motivation, da ich mit dieser Bachelorarbeit vielen Interessenten der Mathematik als Sekundärliteratur dienen kann. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71560 ER - TY - THES A1 - Wyczik, Christopher T1 - Optimierung von Deployment- und Umgebungs-Integrität durch ein dezentrales Konfigurationsrepository auf Basis einer Blockchain N2 - Viele Firmen nutzen für ihre eigenen Softwareentwicklungen verschiedene Server mit unterschiedlichen Konfigurationen. Manche Server werden dazu eingestzt das Verhalten einer Software in einer bestimmten Umgebung zu testen und andere dienen zur Bereitstellung der Software für den Endnutzer. Hierbei ist es wichtig, dass die Konfiguration der Server regelmäßig überprüft wird. Eine solche Sicherstellung der Deployment- und Umgebungs-Integrität wird meistens durch eine Mitarbeiter der Firma oder durch einen externen Dienstleister erbracht. D.h. die Firma muss sich auf die Zuverlässigkeit eines Mitarbeiters oder einer externen Dienstleistung verlassen, bie zunehmender Komplexität ist sie sogar abhängig. Das Ziel dieser Masterarbeit ist es, zu untersuchen, ob die Sicherstellung der Deployment- und Umgebungs-Integrität durch automatisierte kryptografische Beweise, anstelle externer Dienstleistungen oder anderer Mitarbeiter, gewährleistet werden kann. Als Anwendungsfall dient die Toll Collect GmbH. Im ersten Teil dieser Arbeit wird das Matheamtische Modell einer Blockchain erläutert. die Blockchain wurde erstmals in einem Dokument, welches unter dem Pseudonym Satoshi Nakamoto veröffentlicht wurde, beschrieben. Die erste große Anwendungen der Blockchain ist das dezentrale Zahlungssystem Bitcoin. Im zweiten Teil dieser Arbeit wird die Softwareimplementierung vorgestellt, welche im Rahmen dieser Arbeit entstanden ist. Mithilfe dieses Programms kann die Deployment- und Umgebungs-Integrität durch eine heirführ entwickelte Blockchainlösung dezentralisiert werden. Es wird außerdem der Übergang vom Mathematischen Modell zur Implementierung gezeigt. Y1 - 2018 ER - TY - THES A1 - Oleynikova, Ekaterina T1 - Mathematical optimization of joint order batching and picker routing problems N2 - In this thesis we study order picking optimization problems for a two-blocks rectangle warehouse layout. We present combinatorial formulations and linear programming models based on the Steiner graph representation for order batching, picker routing, and joint order batching and picker routing problems. A special case of the latter is considered. This case assumes that each order contains exactly one item and each item can be picked from different possible locations in a warehouse. The underlying optimization problem is called joint multi-location order batching and picker routing problem (JMLOBPRP). Since having only one-item orders turns the JMLOBPRP into a special case of a capacitated vehicle routing problem, we suggest to implement algorithmic approaches for those to solve the JMLOBPRP. In particular, we define the JMLOBPRP as a generalization of the resource constrained assignment problem, for which a regional search method exists. The intention of the thesis is to investigate how a relaxation of the JMLOBPRP, a so-called group assignment problem (GrAP), can be solved following the ideas of regional search. We present a mathematical model of the GrAP and prove that it is NP-hard. Furthermore, we propose a novel heuristic algorithm for the GrAP. We call this method a network search algorithm, as it is based on a Lagrangian relaxation of the GrAP, which is solved by the network simplex method. On each its iteration network search examines a solution region suggested by the network simplex algorithm and improves the incumbent solution. Numerical experiments are conducted to assess a performance of the network search method. We create more realistic problem instances. The proposed algorithm is compared to the integer optimal solution of the GrAP and optimal fractional solution of its linear relaxation. Both computed using the commercial linear solver Gurobi. Our experiments show that the developed network search algorithm leads to the hight-quality solution within a short computing time. The results obtained testing large problem instances which cannot be solved by Gurobi within a reasonable computing time, show that the network search method provides a solution approach which can be used in practice. Y1 - 2018 ER - TY - THES A1 - Wirsching, Marie T1 - Der Einfluss von Langzahlarithmetik auf das Gewichtsraumpolyeder in mehrkriterieller Optimierung N2 - Die Arbeit befasst sich mit einem gewichtsraumbasierten Algorithmus, der ganzzahlige und lineare Optimierungsprobleme mit mehreren Zielfunktionen löst und die Menge der unterstützt nicht dominierten Punkte ermittelt. Die dabei erzeugten Gewichtsraumpolyeder sind das entscheidende Mittel, um die gesuchte Lösungsmenge zu bestimmen. Aus softwaretechnischer Sicht sind numerische Ungenauigkeiten potentielle Fehlerquellen, die sich negativ auf das Endergebnis auswirken. Aus diesem Grund untersuchen wir anhand von Zuweisungs- und Rucksackinstanzen mit 3 Zielfunktionen, inwieweit der Gebrauch von Langzahlarithmetik die Gewichtsraumpolyeder und die damit verbundene Menge der unterstützt nicht dominierten Punkte beeinflusst. Y1 - 2018 ER - TY - THES A1 - Euler, Ricardo T1 - The Bienstock Zuckerberg Algorithm for the Rolling Stock Rotation Problem N2 - The design of rolling stock rotations is an important task in large-scale railway planning. This so-called rolling stock rotation problem (RSRP) is usually tackled using an integer programming approach. Markus Reuther did so in his dissertation [15] for the ICE railway network of DB ("Deutsche Bahn"). Due to the size of the network and the complexity of further technical requirements, the resulting integer problems tend to become very large and computationally involved. In this thesis, we tackle the linear programming relaxation of the RSRP integer program. We will do so by applying a modified version of an algorithm recently proposed by Dan Bienstock and Mark Zuckerberg [2] for the precedence constrained production scheduling problem that arises in open pit mine scheduling. This problem contains a large number of "easy" constraints and a relatively small number of "hard" constraints. We will see that a similar problem structure can also be found in the RSRP. The Bienstock-Zuckerberg algorithm relies on applying Lagrangian relaxation to the hard constraints as well as on partitioning the variable set. We propose three different partition schemes which try to exploit the specific problem structure of the RSRP. Furthermore, we will discuss the influence of primal degeneracy on the algorithm's performance, as well as possible merits of perturbating the right-hand side of the constraint matrix. We provide computational results to assess the performance of those approaches. Y1 - 2018 ER - TY - CHAP A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Weider, Steffen T1 - The Rolling Stock Rotation Planning Problem under Revenue Considerations T2 - Proceedings of the Rail Transport Demand Management Conference N2 - In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America. Y1 - 2018 ER - TY - CHAP A1 - Klindt, Marco T1 - Implications of perceived preservation levels T2 - Proceedings of iPres – 15th International Conference on Digital Preservation / Boston, MA, USA / September 24 – 27, 2018 N2 - This paper describes and explores the concept of perceived preservation levels and their implications. Perceived preservation levels are a way to communicate preservation policies, options and actions to the various stakeholders in digital preservation a digital preservation system is capable and able of. While explicitly assigned or stated preservation levels are promises to adhere to a certain set of policies and decisions, it may be hard to impossible for a best effort preservation service to fulfill these expectations. Perceived preservation levels combine different outcomes from preservation actions with preservation options and available resources to convey a holistic view of the archive’s worflow and decision states. A preservation system providing information about current states of digital objects puts the data producers in a position to reassure themselves of the trustworthiness of the archive without the need of formal certification. This openness has implications not only for the trust relationship between producer and archive but provides the opportunity to constantly reassess the archive’s decisions and priorities from the outside. Y1 - 2018 U6 - https://doi.org/10.17605/OSF.IO/M6QA5 VL - 15 ER - TY - CHAP A1 - Sagnol, Guillaume A1 - Schmidt genannt Waldschmidt, Daniel A1 - Tesch, Alexander T1 - The Price of Fixed Assignments in Stochastic Extensible Bin Packing T2 - WAOA 2018: Approximation and Online Algorithms N2 - We consider the stochastic extensible bin packing problem (SEBP) in which n items of stochastic size are packed into m bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of 2. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of (1+e−1)≈1.368 under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-030-04693-4_20 VL - 11312 SP - 327 EP - 347 ER - TY - GEN A1 - Berthold, Timo A1 - Stuckey, Peter A1 - Witzig, Jakob T1 - Local Rapid Learning for Integer Programs N2 - Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems. T3 - ZIB-Report - 18-56 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71190 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming N2 - Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part. T3 - ZIB-Report - 18-57 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71170 SN - 1438-0064 ER - TY - CHAP A1 - Hendel, Gregor A1 - Miltenberger, Matthias A1 - Witzig, Jakob T1 - Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms T2 - OR 2018: International Conference on Operations Research N2 - State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances. Y1 - 2018 ER - TY - GEN A1 - Hendel, Gregor T1 - Adaptive Large Neighborhood Search for Mixed Integer Programming N2 - Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP. T3 - ZIB-Report - 18-60 KW - mixed integer programming KW - primal heuristics KW - large neighborhood search KW - multi armed bandit problem Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71167 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Hatzel, Meike A1 - Wiederrecht, Sebastian T1 - The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs N2 - The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lovász on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable. T3 - ZIB-Report - 18-61 KW - uniform hypergraphs KW - perfect matchings KW - tight cuts Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71149 SN - 1438-0064 ER - TY - GEN A1 - Serrano, Felipe T1 - Intersection cuts for factorable MINLP N2 - Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables. T3 - ZIB-Report - 18-59 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71105 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores N2 - SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB. T3 - ZIB-Report - 18-58 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71118 SN - 1438-0064 ER - TY - JOUR A1 - Klus, Stefan A1 - Bittracher, Andreas A1 - Schuster, Ingmar A1 - Schütte, Christof T1 - A kernel-based approach to molecular conformation analysis JF - Journal of Chemical Physics N2 - We present a novel machine learning approach to understanding conformation dynamics of biomolecules. The approach combines kernel-based techniques that are popular in the machine learning community with transfer operator theory for analyzing dynamical systems in order to identify conformation dynamics based on molecular dynamics simulation data. We show that many of the prominent methods like Markov State Models, EDMD, and TICA can be regarded as special cases of this approach and that new efficient algorithms can be constructed based on this derivation. The results of these new powerful methods will be illustrated with several examples, in particular the alanine dipeptide and the protein NTL9. Y1 - 2018 U6 - https://doi.org/10.1063/1.5063533 VL - 149 IS - 24 ER - TY - JOUR A1 - Dell’Amico, M. A1 - Hadjidimitriou, Natalia Selini A1 - Koch, Thorsten A1 - Petkovic, Milena T1 - Forecasting Natural Gas Flows in Large Networks JF - Machine Learning, Optimization, and Big Data. MOD 2017. N2 - Natural gas is the cleanest fossil fuel since it emits the lowest amount of other remains after being burned. Over the years, natural gas usage has increased significantly. Accurate forecasting is crucial for maintaining gas supplies, transportation and network stability. This paper presents two methodologies to identify the optimal configuration o parameters of a Neural Network (NN) to forecast the next 24 h of gas flow for each node of a large gas network. In particular the first one applies a Design Of Experiments (DOE) to obtain a quick initial solution. An orthogonal design, consisting of 18 experiments selected among a total of 4.374 combinations of seven parameters (training algorithm, transfer function, regularization, learning rate, lags, and epochs), is used. The best result is selected as initial solution of an extended experiment for which the Simulated Annealing is run to find the optimal design among 89.100 possible combinations of parameters. The second technique is based on the application of Genetic Algorithm for the selection of the optimal parameters of a recurrent neural network for time series forecast. GA was applied with binary representation of potential solutions, where subsets of bits in the bit string represent different values for several parameters of the recurrent neural network. We tested these methods on three municipal nodes, using one year and half of hourly gas flow to train the network and 60 days for testing. Our results clearly show that the presented methodologies bring promising results in terms of optimal configuration of parameters and forecast error. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1007/978-3-319-72926-8_14 VL - Lecture Notes in Computer Science IS - vol 10710 SP - 158 EP - 171 ER - TY - JOUR A1 - Lie, Han Cheng A1 - Sullivan, T. J. T1 - Erratum: Equivalence of weak and strong modes of measures on topological vector spaces (2018 Inverse Problems 34 115013) JF - Inverse Problems Y1 - 2018 U6 - https://doi.org/10.1088/1361-6420/aae55b VL - 34 IS - 12 SP - 129601 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Reduction-based exact solution of prize-collecting Steiner tree problems T3 - ZIB-Report - 18-55 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70958 SN - 1438-0064 ER - TY - GEN A1 - Nägel, Arne A1 - Deuflhard, Peter A1 - Wittum, Gabriel T1 - Efficient Stiff Integration of Density Driven Flow Problems N2 - The paper investigates the efficient use of a linearly implicit stiff integrator for the numerical solution of density driven flow problems. Upon choosing a one-step method of extrapolation type (code LIMEX), the use of full Jacobians and reduced approximations are discussed. Numerical experiments include nonlinear density flow problems such as diffusion from a salt dome (2D), a (modified) Elder problem (3D), the saltpool benchmark (3D) and a real life salt dome problem (2D). The arising linear equations are solved using either a multigrid preconditioner from the software package UG4 or the sparse matrix solver SuperLU. T3 - ZIB-Report - 18-54 KW - stiff integration for PDEs KW - linearly implicit Euler discretization Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70891 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Egerer, Ascan A1 - Karbstein, Marika A1 - Messerschmidt, Ralf A1 - Perez, Marc A1 - Pfisterer, Steven A1 - Strauß, Petra T1 - Kombilösung: Optimierung des Liniennetzes in Karlsruhe N2 - Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung. T3 - ZIB-Report - 18-45 KW - ÖPNV KW - Linienplanung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69677 SN - 1438-0064 ER - TY - CHAP A1 - Jäger, Klaus A1 - Manley, Phillip A1 - Eisenhauer, David A1 - Tockhorn, Philipp A1 - Sutter, Johannes A1 - Hammerschmidt, Martin A1 - Burger, Sven A1 - Albrecht, Steve A1 - Becker, Christiane T1 - Light management with sinusoidal nanotextures T2 - Light, Energy and the Environment 2018 Y1 - 2018 U6 - https://doi.org/10.1364/OSE.2018.OT5C.5 SP - OT5C.5 ER - TY - JOUR A1 - Hoffmann, Rene A1 - Lemanis, Robert A1 - Wulff, Lena A1 - Zachow, Stefan A1 - Lukeneder, Alexander A1 - Klug, Christian A1 - Keupp, Helmut T1 - Traumatic events in the life of the deep-sea cephalopod mollusc, the coleoid Spirula spirula JF - ScienceDirect: Deep Sea Research Part I - Oceanographic Research N2 - Here, we report on different types of shell pathologies of the enigmatic deep-sea (mesopelagic) cephalopod Spirula spirula. For the first time, we apply non-invasive imaging methods to: document trauma-induced changes in shell shapes, reconstruct the different causes and effects of these pathologies, unravel the etiology, and attempt to quantify the efficiency of the buoyancy apparatus. We have analysed 2D and 3D shell parameters from eleven shells collected as beach findings from the Canary Islands (Gran Canaria and Fuerteventura), West-Australia, and the Maldives. All shells were scanned with a nanotom-m computer tomograph. Seven shells were likely injured by predator attacks: fishes, cephalopods or crustaceans, one specimen was infested by an endoparasite (potentially Digenea) and one shell shows signs of inflammation and one shell shows large fluctuations of chamber volumes without any signs of pathology. These fluctuations are potential indicators of a stressed environment. Pathological shells represent the most deviant morphologies of a single species and can therefore be regarded as morphological end-members. The changes in the shell volume / chamber volume ratio were assessed in order to evaluate the functional tolerance of the buoyancy apparatus showing that these had little effect. Y1 - 2018 U6 - https://doi.org/10.1016/j.dsr.2018.10.007 VL - 142 IS - 12 SP - 127 EP - 144 ER - TY - THES A1 - Steininger, Lennart T1 - Atomarer Datenzugriff auf verteilten persistenten Arbeitsspeicher N2 - Nicht flüchtiger Arbeitsspeicher bzw. Non-volatile Random Access Memory oder auch Persistent Memory befindet sich im frühen Markteintritt. Diese Art von Speicher nimmt eine Stellung zwischen bisherigem flüchtigen Arbeitsspeicher (Memory) und bisherigem Permanentspeicher (Storage) ein. Im Zusammenspiel mit verteilten Algorithmen und Systemen sowie dem Zugriff auf entfernte Speicherbereiche durch die Netzwerkinterfaces per Remote Direct Memory Access sind die Konzepte zum Umgang mit Durability und allen einhergehenden Herausforderungen bisher nicht ausgereift. Diese Arbeit untersucht, wie sich in Rechnernetzen mit persistentem Speicher und möglichst passivem Zugriff auf entfernten Speicher performante verteilte Systeme implementieren lassen. Es werden Anforderungen und Voraussetzungen eines solchen Systems bestimmt und daraufhin Lösungsmöglichkeiten aufgezeigt, wie sich diese Anforderungen mit Nutzung nicht flüchtigen Arbeitsspeichers umsetzen lassen. Die notwendigen Eigenschaften der Hard- und Software sowie der eingesetzten Netzwerkprotokolle werden beschrieben. Y1 - 2018 ER - TY - CHAP A1 - Schmidtke, Robert A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - From Application to Disk: Tracing I/O Through the Big Data Stack T2 - High Performance Computing ISC High Performance 2018 International Workshops, Frankfurt/Main, Germany, June 24 - 28, 2018, Revised Selected Papers, Workshop on Performance and Scalability of Storage Systems (WOPSSS) N2 - Typical applications in data science consume, process and produce large amounts of data, making disk I/O one of the dominating — and thus worthwhile optimizing — factors of their overall performance. Distributed processing frameworks, such as Hadoop, Flink and Spark, hide a lot of complexity from the programmer when they parallelize these applications across a compute cluster. This exacerbates reasoning about I/O of both the application and the framework, through the distributed file system, such as HDFS, down to the local file systems. We present SFS (Statistics File System), a modular framework to trace each I/O request issued by the application and any JVM-based big data framework involved, mapping these requests to actual disk I/O. This allows detection of inefficient I/O patterns, both by the applications and the underlying frameworks, and builds the basis for improving I/O scheduling in the big data software stack. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-030-02465-9_6 SP - 89 EP - 102 ER - TY - CHAP A1 - Renken, Malte A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Sahin, Guvenc A1 - Schlechte, Thomas T1 - Demand-Driven Line Planning with Selfish Routing T2 - Operations Research Proceedings 2017 N2 - Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_91 SP - 687 EP - 692 PB - Springer International Publishing ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Liebchen, Christian A1 - Lindner, Niels T1 - A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable T2 - 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) N2 - We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [9], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same. Y1 - 2018 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2018.16 VL - 65 SP - 16:1 EP - 16:15 ER - TY - GEN A1 - Gholami, Masoud A1 - Schintke, Florian A1 - Schütt, Thorsten A1 - Reinefeld, Alexander T1 - Modeling Checkpoint Schedules for Concurrent HPC Applications T2 - CoSaS 2018 International Symposium on Computational Science at Scale Y1 - 2018 ER - TY - JOUR A1 - Donati, Luca A1 - Heida, Martin A1 - Keller, Bettina G. A1 - Weber, Marcus T1 - Estimation of the infinitesimal generator by square-root approximation JF - J. Phys.: Condens. Matter N2 - In recent years, for the analysis of molecular processes, the estimation of time-scales and transition rates has become fundamental. Estimating the transition rates between molecular conformations is—from a mathematical point of view—an invariant subspace projection problem. We present a method to project the infinitesimal generator acting on function space to a low-dimensional rate matrix. This projection can be performed in two steps. First, we discretize the conformational space in a Voronoi tessellation, then the transition rates between adjacent cells is approximated by the geometric average of the Boltzmann weights of the Voronoi cells. This method demonstrates that there is a direct relation between the potential energy surface of molecular structures and the transition rates of conformational changes. We will show also that this approximation is correct and converges to the generator of the Smoluchowski equation in the limit of infinitely small Voronoi cells. We present results for a two dimensional diffusion process and alanine dipeptide as a high-dimensional system. Y1 - 2018 U6 - https://doi.org/10.1088/1361-648X/aadfc8 VL - 30 IS - 42 SP - 425201 EP - 425201 ER - TY - JOUR A1 - Manley, Phillip A1 - Abdi, Fatwa F. A1 - Berglund, Sean P. A1 - Islam, A. T. M. Nazmul A1 - Burger, Sven A1 - van de Krol, Roel A1 - Schmid, Martina T1 - Absorption Enhancement for Ultra-Thin Solar Fuel Devices with Plasmonic Gratings JF - ACS Appl. Energy Mater. Y1 - 2018 U6 - https://doi.org/10.1021/acsaem.8b01070 VL - 1 SP - 5810 ER - TY - CHAP A1 - Knötel, David A1 - Becker, Carola A1 - Scholtz, Gerhard A1 - Baum, Daniel T1 - Global and Local Mesh Morphing for Complex Biological Objects from microCT Data T2 - Eurographics Workshop on Visual Computing for Biology and Medicine (VCBM) N2 - We show how biologically coherent mesh models of animals can be created from μCT data to generate artificial yet naturally looking intermediate objects. The whole pipeline of processing algorithms is presented, starting from generating topologically equivalent surface meshes, followed by solving the correspondence problem, and, finally, creating a surface morphing. In this pipeline, we address all the challenges that are due to dealing with complex biological, non-isometric objects. For biological objects it is often particularly important to obtain deformations that look as realistic as possible. In addition, spatially non-uniform shape morphings that only change one part of the surface and keep the rest as stable as possible are of interest for evolutionary studies, since functional modules often change independently from one another. We use Poisson interpolation for this purpose and show that it is well suited to generate both global and local shape deformations. Y1 - 2018 U6 - https://doi.org/10.2312/vcbm.20181243 SP - 179 EP - 183 CY - Granada, Spain ER - TY - GEN A1 - Knötel, David A1 - Becker, Carola A1 - Scholtz, Gerhard A1 - Baum, Daniel T1 - Global and Local Mesh Morphing for Complex Biological Objects from microCT Data N2 - We show how biologically coherent mesh models of animals can be created from μCT data to generate artificial yet naturally looking intermediate objects. The whole pipeline of processing algorithms is presented, starting from generating topologically equivalent surface meshes, followed by solving the correspondence problem, and, finally, creating a surface morphing. In this pipeline, we address all the challenges that are due to dealing with complex biological, non-isometric objects. For biological objects it is often particularly important to obtain deformations that look as realistic as possible. In addition, spatially non-uniform shape morphings that only change one part of the surface and keep the rest as stable as possible are of interest for evolutionary studies, since functional modules often change independently from one another. We use Poisson interpolation for this purpose and show that it is well suited to generate both global and local shape deformations. T3 - ZIB-Report - 18-53 KW - Mesh interpolation KW - Geometry processing KW - microCT Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70618 SN - 1438-0064 ER - TY - GEN A1 - Ito, Satoshi A1 - Shinano, Yuji T1 - Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria N2 - The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds. T3 - ZIB-Report - 18-51 KW - Sports league KW - Round-robin tournament KW - Tiebreaking criteria KW - Clinch number KW - Elimination number KW - Combinatorial optimization KW - Integer programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70591 SN - 1438-0064 ER - TY - JOUR A1 - Lange, Alexander A1 - Schwieger, Robert A1 - Plöntzke, Julia A1 - Schäfer, Stefan A1 - Röblitz, Susanna T1 - Follicular competition in cows: the selection of dominant follicles as a synergistic effect JF - Journal of Mathematical Biology N2 - The reproductive cycle of mono-ovulatory species such as cows or humans is known to show two or more waves of follicular growth and decline between two successive ovulations. Within each wave, there is one dominant follicle escorted by subordinate follicles of varying number. Under the surge of the luteinizing hormone a growing dominant follicle ovulates. Rarely the number of ovulating follicles exceeds one. In the biological literature, the change of hormonal concentrations and individually varying numbers of follicular receptors are made responsible for the selection of exactly one dominant follicle, yet a clear cause has not been identified. In this paper, we suggest a synergistic explanation based on competition, formulated by a parsimoniously defined system of ordinary differential equations (ODEs) that quantifies the time evolution of multiple follicles and their competitive interaction during one wave. Not discriminating between follicles, growth and decline are given by fixed rates. Competition is introduced via a growth-suppressing term, equally supported by all follicles. We prove that the number of dominant follicles is determined exclusively by the ratio of follicular growth and competition. This number turns out to be independent of the number of subordinate follicles. The asymptotic behavior of the corresponding dynamical system is investigated rigorously, where we demonstrate that the ω-limit set only contains fixed points. When also including follicular decline, our ODEs perfectly resemble ultrasound data of bovine follicles. Implications for the involved but not explicitly modeled hormones are discussed. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1007/s00285-018-1284-0 ER - TY - JOUR A1 - Schwieger, Robert A1 - Siebert, Heike A1 - Röblitz, Susanna T1 - Correspondence of Trap Spaces in Different Models of Bioregulatory Networks JF - SIAM Journal on Applied Dynamical Systems N2 - Mathematical models for bioregulatory networks can be based on different formalisms, depending on the quality of available data and the research question to be answered. Discrete boolean models can be constructed based on qualitative data, which are frequently available. On the other hand, continuous models in terms of ordinary differential equations (ODEs) can incorporate time-series data and give more detailed insight into the dynamics of the underlying system. A few years ago, a method based on multivariate polynomial interpolation and Hill functions has been developed for an automatic conversion of boolean models to systems of ordinary differential equations. This method is frequently used by modellers in systems biology today, but there are only a few results available about the conservation of mathematical structures and properties across the formalisms. Here, we consider subsets of the phase space where some components stay fixed, called trap spaces, and demonstrate how boolean trap spaces can be linked to invariant sets in the continuous state space. This knowledge is of practical relevance since finding trap spaces in the boolean setting, which is relatively easy, allows for the construction of reduced ODE models. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1137/17M1155302 VL - 17 IS - 2 SP - 1742 EP - 1765 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Karbstein, Marika A1 - Mett, Fabian T1 - Ein mathematisches Modell zur Beschreibung von Preissystemen im öV N2 - Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zunächst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs. T3 - ZIB-Report - 18-47 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70564 SN - 1438-0064 ER - TY - JOUR A1 - Sunkara, Vikram T1 - Algebraic Expressions of Conditional Expectations in Gene Regulatory Networks JF - Journal of Mathematical Biology N2 - Gene Regulatory Networks are powerful models for describing the mechanisms and dynamics inside a cell. These networks are generally large in dimension and seldom yield analytical formulations. It was shown that studying the conditional expectations between dimensions (vertices or species) of a network could lead to drastic dimension reduction. These conditional expectations were classically given by solving equations of motions derived from the Chemical Master Equation. In this paper we deviate from this convention and take an Algebraic approach instead. That is, we explore the consequences of conditional expectations being described by a polynomial function. There are two main results in this work. Firstly: if the conditional expectation can be described by a polynomial function, then coefficients of this polynomial function can be reconstructed using the classical moments. And secondly: there are dimensions in Gene Regulatory Networks which inherently have conditional expectations with algebraic forms. We demonstrate through examples, that the theory derived in this work can be used to develop new and effective numerical schemes for forward simulation and parameter inference. The algebraic line of investigation of conditional expectations has considerable scope to be applied to many different aspects of Gene Regulatory Networks; this paper serves as a preliminary commentary in this direction. T3 - ZIB-Report - 18-52 KW - Markov Chains KW - Chemical Master Equations KW - Dimension Reduction Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70526 SN - 1438-0064 IS - 79 SP - 1779 EP - 1829 PB - Journal of Mathematical Biology ER - TY - CHAP A1 - Dennstedt, Anne A1 - Gaslain, Fabrice A1 - Bartsch, Marion A1 - Guipont, Vincent A1 - Maurel, Vincent T1 - Crack Morphology in a Columnar Thermal Barrier Coating System N2 - Ceramic layers are used as thermal barrier coatings (TBCs) on metallic substrates. During thermal transients, the thermal expansion mismatch between coating and substrate drives failure of the TBC mainly by interfacial cracking. Laser Shock Adhesion Test (LASAT) provides stresses at the ceramic/metal interface enabling controlled interfacial cracking. For achieving a clear understanding of the influence of local morphology on interfacial toughness, this study aims at characterizing the 3D morphology of a crack at the interface between metal and an EB-PVD TBC having a columnar structure. Cracks were produced by LASAT and documented further in SE and BSE image stacks collected simultaneously during subsequent slice and view operations using a focus ion beam (FIB) and a scanning electron microscope (FIB slice & view). The segmented 3D data gives clear understanding of the columnar structure of the ceramic and of the interaction between the crack and the TBC microstructure. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69385 ER - TY - CHAP A1 - Manley, Phillip A1 - Jäger, Klaus A1 - Tockhorn, Philipp A1 - Burger, Sven A1 - Albrecht, Steve A1 - Becker, Christiane T1 - Optimization of nanostructured high efficiency perovskite/c-Si tandem solar cells via numerical simulation T2 - Proc. SPIE Y1 - 2018 U6 - https://doi.org/10.1117/12.2321240 VL - 10731 SP - 107310B ER -