@misc{BergPloentzkeLeonhardMareketal., author = {Berg, Mascha and Pl{\"o}ntzke, Julia and Leonhard-Marek, Sabine and M{\"u}ller, Kerstin-Elisabeth and R{\"o}blitz, Susanna}, title = {A dynamic model to simulate potassium balance in dairy cows.}, issn = {1438-0064}, doi = {10.3168/jds.2016-12443}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64756}, abstract = {High performing dairy cows require a particular composition of nutritional ingredients, adapted to their individual requirements and depending on their production status. The optimal dimensioning of minerals in the diet, one of them being potassium, is indispensable for the prevention of imbalances. The potassium balance in cows is the result of potassium intake, distribution in the organism, and excretion, it is closely related with the glucose and electrolyte metabolism. In this paper, we present a dynamical model for the potassium balance in lactating and non-lactating dairy cows based on ordinary differential equations. Parameter values are obtained from clinical trial data and from the literature. To verify the consistency of the model, we present simulation outcomes for three different scenarios: potassium balance in (i) non-lactating cows with varying feed intake, (ii) non-lactating cows with varying potassium fraction in the diet, and (iii) lactating cows with varying milk production levels. The results give insights into the short and long term potassium metabolism, providing an important step towards the understanding of the potassium network, the design of prophylactic feed additives, and possible treatment strategies.}, language = {en} } @misc{HillerWalther, author = {Hiller, Benjamin and Walther, Tom}, title = {Improving branching for disjunctive polyhedral models using approximate convex decompositions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67462}, abstract = {Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior.}, language = {en} } @misc{HillerSaitenmacherWalther, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68179}, abstract = {We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode.}, language = {en} } @misc{BeckerHiller, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77684}, abstract = {In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.}, language = {en} } @misc{AgudoJacomeHegePaetschetal., author = {Agudo J{\´a}come, Leonardo and Hege, Hans-Christian and Paetsch, Olaf and P{\"o}thkow, Kai}, title = {Three-Dimensional Reconstruction and Quantification of Dislocation Substructures from Transmission Electron Microscopy Stereo-Pairs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70339}, abstract = {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.}, language = {en} } @misc{BuchmannKaplanPowelletal., author = {Buchmann, Jens and Kaplan, Bernhard and Powell, Samuel and Prohaska, Steffen and Laufer, Jan}, title = {3D quantitative photoacoustic tomography using an adjoint radiance Monte Carlo model and gradient descent}, issn = {1438-0064}, doi = {10.1117/1.JBO.24.6.066001}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72995}, abstract = {Quantitative photoacoustic tomography aims to recover maps of the local concentrations of tissue chromophores from multispectral images. While model-based inversion schemes are promising approaches, major challenges to their practical implementation include the unknown fluence distribution and the scale of the inverse problem. This paper describes an inversion scheme based on a radiance Monte Carlo model and an adjoint-assisted gradient optimization that incorporates fluence-dependent step sizes and adaptive moment estimation. The inversion is shown to recover absolute chromophore concentrations, blood oxygen saturation and the Gr{\"u}neisen parameter from in silico 3D phantom images for different radiance approximations. The scattering coefficient was assumed to be homogeneous and known a priori.}, language = {en} } @misc{BuchmannKaplanPowelletal., author = {Buchmann, Jens and Kaplan, Bernhard and Powell, Samuel and Prohaska, Steffen and Laufer, Jan}, title = {Quantitative PA tomography of high resolution 3-D images: experimental validation in tissue phantoms}, issn = {1438-0064}, doi = {10.1016/j.pacs.2019.100157}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75416}, abstract = {Quantitative photoacoustic tomography aims recover the spatial distribution of absolute chromophore concentrations and their ratios from deep tissue, high-resolution images. In this study, a model-based inversion scheme based on a Monte-Carlo light transport model is experimentally validated on 3-D multispectral images of a tissue phantom acquired using an all-optical scanner with a planar detection geometry. A calibrated absorber allowed scaling of the measured data during the inversion, while an acoustic correction method was employed to compensate the effects of limited view detection. Chromophore- and fluence-dependent step sizes and Adam optimization were implemented to achieve rapid convergence. High resolution 3-D maps of absolute concentrations and their ratios were recovered with high accuracy. Potential applications of this method include quantitative functional and molecular photoacoustic tomography of deep tissue in preclinical and clinical studies.}, language = {en} } @misc{LindnerLiebchen, author = {Lindner, Niels and Liebchen, Christian}, title = {Determining all integer vertices of the PESP polytope by flipping arcs}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2020.5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78793}, abstract = {We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.}, language = {en} } @misc{LindnerLiebchen, author = {Lindner, Niels and Liebchen, Christian}, title = {New Perspectives on PESP: T-Partitions and Separators}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2019.2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73853}, abstract = {In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.}, language = {en} } @misc{BorndoerferDenissenHelleretal., author = {Bornd{\"o}rfer, Ralf and Denißen, Jonas and Heller, Simon and Klug, Torsten and K{\"u}pper, Michael and Lindner, Niels and Reuther, Markus and Schlechte, Thomas and S{\"o}hlke, Andreas and Steadman, William}, title = {Microscopic Timetable Optimization for a Moving Block System}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82547}, abstract = {We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.}, language = {en} } @misc{LindnerLiebchenMasing, author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike}, title = {Forward Cycle Bases and Periodic Timetabling}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82756}, abstract = {Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.}, language = {en} } @misc{LindnerMaristanydelasCasasSchiewe, author = {Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine}, title = {Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82716}, abstract = {We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.}, language = {en} } @misc{BorndoerferKarbsteinLiebchenetal., author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2018.16}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69688}, abstract = {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.}, language = {en} } @misc{LoebelLindnerBorndoerfer, author = {L{\"o}bel, Fabian and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing}, issn = {1438-0064}, doi = {https://doi.org/https://doi.org/10.1007/978-3-030-48439-2_92}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73868}, abstract = {The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.}, language = {en} } @misc{LindnervanLieshout, author = {Lindner, Niels and van Lieshout, Rolf}, title = {Benders Decomposition for the Periodic Event Scheduling Problem}, issn = {1438-0064}, doi = {10.1007/978-3-031-08623-6_43}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83338}, abstract = {The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib.}, language = {en} } @misc{KlindtAmrheinMuelleretal., author = {Klindt, Marco and Amrhein, Kilian and M{\"u}ller, Anja and Peters-Kottig, Wolfgang}, title = {Dealing with all the data - Participating in workflows to transform digital data about cultural heritage objects within a digital long-term preservation infrastructure}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-43020}, abstract = {Cultural heritage institutions are on the verge of making their artefacts available in digital form. During this transition they are faced with conceptual and technical challenges that have only little overlap with their traditional domains but provide them with a lot of opportunities. We aim at empowering them to deal with some of these challenges by designing workflows attached to the data flow within a digital long-term preservation system. The preservation framework processes data by utilising micro-services. These are tailored to accommodate data transformations that can help institutions making their data available if they choose to participate in the interconnected digital world}, language = {en} } @misc{RammMorilloVictoriaTodtetal., author = {Ramm, Heiko and Morillo Victoria, Oscar Salvador and Todt, Ingo and Schirmacher, Hartmut and Ernst, Arneborg and Zachow, Stefan and Lamecker, Hans}, title = {Visual Support for Positioning Hearing Implants}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42495}, abstract = {We present a software planning tool that provides intuitive visual feedback for finding suitable positions of hearing implants in the human temporal bone. After an automatic reconstruction of the temporal bone anatomy the tool pre-positions the implant and allows the user to adjust its position interactively with simple 2D dragging and rotation operations on the bone's surface. During this procedure, visual elements like warning labels on the implant or color encoded bone density information on the bone geometry provide guidance for the determination of a suitable fit.}, language = {en} } @misc{PfetschFuegenschuhGeissleretal., author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, issn = {1438-0064}, doi = {10.1080/10556788.2014.888426}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16531}, abstract = {In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.}, language = {en} } @misc{WaltherHillerSaitenmacher, author = {Walther, Tom and Hiller, Benjamin and Saitenmacher, Ren{\´e}}, title = {Polyhedral 3D Models for compressors in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65864}, abstract = {Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.}, language = {en} } @misc{CostaMantonOstrovskyetal., author = {Costa, Marta and Manton, James D. and Ostrovsky, Aaron D. and Prohaska, Steffen and Jefferis, Gregory S.X.E.}, title = {NBLAST: Rapid, sensitive comparison of neuronal structure and construction of neuron family databases}, issn = {1438-0064}, doi = {10.1016/j.neuron.2016.06.012}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59672}, abstract = {Neural circuit mapping is generating datasets of 10,000s of labeled neurons. New computational tools are needed to search and organize these data. We present NBLAST, a sensitive and rapid algorithm, for measuring pairwise neuronal similarity. NBLAST considers both position and local geometry, decomposing neurons into short segments; matched segments are scored using a probabilistic scoring matrix defined by statistics of matches and non-matches. We validated NBLAST on a published dataset of 16,129 single Drosophila neurons. NBLAST can distinguish neuronal types down to the finest level (single identified neurons) without a priori information. Cluster analysis of extensively studied neuronal classes identified new types and unreported topographical features. Fully automated clustering organized the validation dataset into 1052 clusters, many of which map onto previously described neuronal types. NBLAST supports additional query types including searching neurons against transgene expression patterns. Finally we show that NBLAST is effective with data from other invertebrates and zebrafish.}, language = {en} } @misc{KuhnEngelkeFlatkenetal., author = {Kuhn, Alexander and Engelke, Wito and Flatken, Markus and Hege, Hans-Christian and Hotz, Ingrid}, title = {Topology-based Analysis for Multimodal Atmospheric Data of Volcano Eruptions}, issn = {1438-0064}, doi = {10.1007/978-3-319-44684-4_2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57043}, abstract = {Many scientific applications deal with data from a multitude of different sources, e.g., measurements, imaging and simulations. Each source provides an additional perspective on the phenomenon of interest, but also comes with specific limitations, e.g. regarding accuracy, spatial and temporal availability. Effectively combining and analyzing such multimodal and partially incomplete data of limited accuracy in an integrated way is challenging. In this work, we outline an approach for an integrated analysis and visualization of the atmospheric impact of volcano eruptions. The data sets comprise observation and imaging data from satellites as well as results from numerical particle simulations. To analyze the clouds from the volcano eruption in the spatiotemporal domain we apply topological methods. Extremal structures reveal structures in the data that support clustering and comparison. We further discuss the robustness of those methods with respect to different properties of the data and different parameter setups. Finally we outline open challenges for the effective integrated visualization using topological methods.}, language = {en} } @misc{HammerschmidtHerrmannBurgeretal., author = {Hammerschmidt, Martin and Herrmann, Sven and Burger, Sven and Pomplun, Jan and Schmidt, Frank}, title = {Reduced basis method for the optimization of nano-photonic devices}, issn = {1438-0064}, doi = {10.1007/s11082-016-0530-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57556}, abstract = {Optical 3D simulations in many-query and real-time contexts require new solution strategies. We study an adaptive, error controlled reduced basis method for solving parametrized time-harmonic optical scattering problems. Application fields are, among others, design and optimization problems of nano-optical devices as well as inverse problems for parameter reconstructions occuring e. g. in optical metrology. The reduced basis method presented here relies on a finite element modeling of the scattering problem with parametrization of materials, geometries and sources.}, language = {en} } @misc{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61931}, abstract = {Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.}, language = {en} } @misc{MartinGeisslerHaynetal., author = {Martin, Alexander and Geißler, Bj{\"o}rn and Hayn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15121}, abstract = {Die mittel- und l{\"a}ngerfristige Planung f{\"u}r den Gastransport hat sich durch {\"A}nderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazit{\"a}t und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und L{\"o}sungsans{\"a}tze skizziert.}, language = {de} } @misc{KaplanLauferProhaskaetal., author = {Kaplan, Bernhard and Laufer, Jan and Prohaska, Steffen and Buchmann, Jens}, title = {Monte-Carlo-based inversion scheme for 3D quantitative photoacoustic tomography}, issn = {1438-0064}, doi = {10.1117/12.2251945}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62318}, abstract = {The goal of quantitative photoacoustic tomography (qPAT) is to recover maps of the chromophore distributions from multiwavelength images of the initial pressure. Model-based inversions that incorporate the physical processes underlying the photoacoustic (PA) signal generation represent a promising approach. Monte-Carlo models of the light transport are computationally expensive, but provide accurate fluence distributions predictions, especially in the ballistic and quasi-ballistic regimes. Here, we focus on the inverse problem of 3D qPAT of blood oxygenation and investigate the application of the Monte-Carlo method in a model-based inversion scheme. A forward model of the light transport based on the MCX simulator and acoustic propagation modeled by the k-Wave toolbox was used to generate a PA image data set acquired in a tissue phantom over a planar detection geometry. The combination of the optical and acoustic models is shown to account for limited-view artifacts. In addition, the errors in the fluence due to, for example, partial volume artifacts and absorbers immediately adjacent to the region of interest are investigated. To accomplish large-scale inversions in 3D, the number of degrees of freedom is reduced by applying image segmentation to the initial pressure distribution to extract a limited number of regions with homogeneous optical parameters. The absorber concentration in the tissue phantom was estimated using a coordinate descent parameter search based on the comparison between measured and modeled PA spectra. The estimated relative concentrations using this approach lie within 5 \% compared to the known concentrations. Finally, we discuss the feasibility of this approach to recover the blood oxygenation from experimental data.}, language = {en} } @misc{QuerDonatiKelleretal., author = {Quer, Jannes and Donati, Luca and Keller, Bettina and Weber, Marcus}, title = {An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62075}, abstract = {In this article we propose an adaptive importance sampling scheme for dynamical quantities of high dimensional complex systems which are metastable. The main idea of this article is to combine a method coming from Molecular Dynamics Simulation, Metadynamics, with a theorem from stochastic analysis, Girsanov's theorem. The proposed algorithm has two advantages compared to a standard estimator of dynamic quantities: firstly, it is possible to produce estimators with a lower variance and, secondly, we can speed up the sampling. One of the main problems for building importance sampling schemes for metastable systems is to find the metastable region in order to manipulate the potential accordingly. Our method circumvents this problem by using an assimilated version of the Metadynamics algorithm and thus creates a non-equilibrium dynamics which is used to sample the equilibrium quantities.}, language = {en} } @misc{HammerschmidtWeiserSantiagoetal., author = {Hammerschmidt, Martin and Weiser, Martin and Santiago, Xavier Garcia and Zschiedrich, Lin and Bodermann, Bernd and Burger, Sven}, title = {Quantifying parameter uncertainties in optical scatterometry using Bayesian inversion}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64704}, abstract = {We present a Newton-like method to solve inverse problems and to quantify parameter uncertainties. We apply the method to parameter reconstruction in optical scatterometry, where we take into account a priori information and measurement uncertainties using a Bayesian approach. Further, we discuss the influence of numerical accuracy on the reconstruction result.}, language = {en} } @misc{BaumLindowHegeetal., author = {Baum, Daniel and Lindow, Norbert and Hege, Hans-Christian and Lepper, Verena and Siopi, Tzulia and Kutz, Frank and Mahlow, Kristin and Mahnke, Heinz-Eberhard}, title = {Revealing hidden text in rolled and folded papyri}, issn = {1438-0064}, doi = {10.1007/s00339-017-0808-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61826}, abstract = {Ancient Egyptian papyri are often folded, rolled up or kept as small packages, sometimes even sealed. Physically unrolling or unfolding these packages might severely damage them. We demonstrate a way to get access to the hidden script without physical unfolding by employing computed tomography and mathematical algorithms for virtual unrolling and unfolding. Our algorithmic approaches are combined with manual interaction. This provides the necessary flexibility to enable the unfolding of even complicated and partly damaged papyrus packages. In addition, it allows us to cope with challenges posed by the structure of ancient papyrus, which is rather irregular, compared to other writing substrates like metallic foils or parchment. Unfolding of packages is done in two stages. In the first stage, we virtually invert the physical folding process step by step until the partially unfolded package is topologically equivalent to a scroll or a papyrus sheet folded only along one fold line. To minimize distortions at this stage, we apply the method of moving least squares. In the second stage, the papyrus is simply flattened, which requires the definition of a medial surface. We have applied our software framework to several papyri. In this work, we present the results of applying our approaches to mockup papyri that were either rolled or folded along perpendicular fold lines. In the case of the folded papyrus, our approach represents the first attempt to address the unfolding of such complicated folds.}, language = {en} } @misc{FuegenschuhHaynMichaels, author = {F{\"u}genschuh, Armin and Hayn, Christine and Michaels, Dennis}, title = {Mixed-Integer Linear Methods for Layout-Optimization of Screening Systems in Recovered Paper Production}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16862}, abstract = {The industrial treatment of waste paper in order to regain valuable fibers from which recovered paper can be produced, involves several steps of preparation. One important step is the separation of stickies that are normally attached to the paper. If not properly separated, remaining stickies reduce the quality of the recovered paper or even disrupt the production process. For the mechanical separation process of fibers from stickies a separator screen is used. This machine has one input feed and two output streams, called the accept and the reject. In the accept the fibers are concentrated, whereas the reject has a higher concentration of stickies. The machine can be controlled by setting its reject rate. But even when the reject rate is set properly, after just a single screening step, the accept still has too many stickies, or the reject too many fibers. To get a proper separation, several separators have to be assembled into a network. From a mathematical point of view this problem can be seen as a multi-commodity network flow design problem with a nonlinear, controllable distribution function at each node. We present a nonlinear mixed-integer programming model for the simultaneous selection of a subset of separators, the network's topology, and the optimal setting of each separator. Numerical results are obtained via different types of linearization of the nonlinearities and the use of mixed-integer linear solvers, and compared with state-of-the-art global optimization software.}, language = {en} } @misc{HillerWalther, author = {Hiller, Benjamin and Walther, Tom}, title = {Modelling compressor stations in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67443}, abstract = {Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.}, language = {en} } @misc{EggerDercksenUdvaryetal., author = {Egger, Robert and Dercksen, Vincent J. and Udvary, Daniel and Hege, Hans-Christian and Oberlaender, Marcel}, title = {Generation of dense statistical connectomes from sparse morphological data}, issn = {1438-0064}, doi = {10.3389/fnana.2014.00129}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53075}, abstract = {Sensory-evoked signal flow, at cellular and network levels, is primarily determined by the synaptic wiring of the underlying neuronal circuitry. Measurements of synaptic innervation, connection probabilities and sub-cellular organization of synaptic inputs are thus among the most active fields of research in contemporary neuroscience. Methods to measure these quantities range from electrophysiological recordings over reconstructions of dendrite-axon overlap at light-microscopic levels to dense circuit reconstructions of small volumes at electron-microscopic resolution. However, quantitative and complete measurements at subcellular resolution and mesoscopic scales to obtain all local and long-range synaptic in/outputs for any neuron within an entire brain region are beyond present methodological limits. Here, we present a novel concept, implemented within an interactive software environment called NeuroNet, which allows (i) integration of sparsely sampled (sub)cellular morphological data into an accurate anatomical reference frame of the brain region(s) of interest, (ii) up-scaling to generate an average dense model of the neuronal circuitry within the respective brain region(s) and (iii) statistical measurements of synaptic innervation between all neurons within the model. We illustrate our approach by generating a dense average model of the entire rat vibrissal cortex, providing the required anatomical data, and illustrate how to measure synaptic innervation statistically. Comparing our results with data from paired recordings in vitro and in vivo, as well as with reconstructions of synaptic contact sites at light- and electron-microscopic levels, we find that our in silico measurements are in line with previous results.}, language = {en} } @misc{Bushe, type = {Master Thesis}, author = {Bushe, Julian}, title = {Rolling Stock Rotation Optimization with Maintenance Paths}, abstract = {Die Planung vom Zuguml{\"a}ufen ist eine der wichtigsten Aufgaben f{\"u}r Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle f{\"u}r die Sicherheit und Zuverl{\"a}ssigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und l{\"o}st — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn f{\"u}r den Schienenpersonenfernverkehr. Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem besch{\"a}ftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung pr{\"a}sentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zun{\"a}chst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gel{\"o}st werden und diese L{\"o}sung dann verwendet wird, um auf effiziente Art und Weise eine L{\"o}sung f{\"u}r das urspr{\"u}ngliche Problem zu finden. Zur Wartungsplanung nutzt Reuther einen Fluss im Hypergraphen, der den Ressourcenverbrauch der Fahrzeuge modelliert. In der linearen Relaxierung des Modells f{\"u}hrt dies dazu, dass die Zahl der notwendigen Wartungen systematisch untersch{\"a}tzt wird. Dadurch bleibt in vielen F{\"a}llen eine große L{\"u}cke zwischen dem Zielfunktionswert einer optimalen L{\"o}sung des ganzzahligen Problems und der untere Schranke, die uns die lineare Relaxierung liefert. Wir nehmen uns in dieser Arbeit dieses Problems an. Wir entwickeln ein auf Pfaden basierendes ganzzahliges Modell f{\"u}r das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder sch{\"a}rfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu l{\"o}sen, entwickeln wir einen Algorithmus, der Spaltengenerierung mit dem Coarse-to-Fine-Ansatz von Reuther verbindet. Weiterhin entwickeln wir eine Spaltenauswahlregel zur Beschleunigung des Algorithmus. Das Modell und alle in der Arbeit vorgestellten Algorithmen wur- den im Rahmen der Arbeit implementiert und mit Anwendungsszenarien der DB Fernverkehr AG getestet. Unsere Tests zeigen, dass unser Modell f{\"u}r fast alle Szena- rien deutlich sch{\"a}rfere untere Schranken liefert als das Modell von Reuther. In den getesteten Instanzen konnten wir durch die Verbesserung der unteren Schranke bis zu 99\% der Optimalit{\"a}tsl{\"u}cke schließen. In einem Drittel der F{\"a}lle konnten wir durch unseren Ansatz auch f{\"u}r das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen}, language = {en} } @misc{Henning, type = {Master Thesis}, author = {Henning, Erin}, title = {Tropical Geometry Approach to Shortest Paths with Parameterized Arc Weights - A Case Study in Public Transportation Networks}, abstract = {In graphical representations of public transportation networks, there is often some degree of uncertainty in the arc values, due to delays or transfer times. This uncertainty can be expressed as a parameterized weight on the transfer arcs. Classical shortest path algorithms often have difficulty handling parameterized arc weights and a tropical geometry approach has been shown as a possible solution. The connection between the classical shortest path problem and tropical geometry is well establish: Tropically multiplying the n × n adjacency matrix of a graph with itself n - 1 times results in the so-called Kleene star, and is a matrix-form solution to the all-pairs shortest path problem. Michael Joswig and Benjamin Schr{\"o}ter showed in their paper The Tropical Geometry of Shortest Paths that the same method can be used to find the solution to the all-pairs shortest path problem even in the case of variable arc weights and they proposed an algorithm to solve the single-target shortest path problem in such a case. The solution takes the form of a polyhedral subdivision of the parameter space. As the number of variable arc weights grows, the time needed to execute an implementation of this algorithm grows exponentially. As the size of a public transportation network grows, the number of variable arc weights grows exponentially as well. However, it has been observed that in public transportation networks, there are usually only a few possible shortest routes. Geometrically, this means that there should be few polyhedra in the polyhedral subdivision. This algorithm is used on an example of a real-world public transportation network and an analysis of the polyhedral subdivision is made. Then a geometrical approach is used to analyze the impact of limiting the number of transfers, and thereby limiting the number of parameterized arcs used, as an estimation of the solution to the all-pairs shortest path problem}, language = {en} } @misc{Masing, type = {Master Thesis}, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, abstract = {One of the fundamental steps in the optimization of public transport is line planning. It involves determining lines and assigning frequencies of service such that costs are minimized while also maximizing passenger comfort and satisfying travel demands. We formulate the problem as a mixed integer linear program that considers all circuit-like lines in a graph and allows free passenger routing. Traveler and operator costs are included in a linear scalarization in the objective. We apply said programming problem to the Parametric City, which is a graph model introduced by Fielbaum, Jara-D{\´i}az and Gschwender that exibly represents different cities. In his dissertation, Fielbaum solved the line planning problem for various parameter choices in the Parametric City. In a first step, we therefore review his results and make comparative computations. Unlike Fielbaum we arrive at the conclusion that the optimal line plan for this model indeed depends on the demand. Consequently, we analyze the line planning problem in-depth: We find equivalent, but easier to compute formulations and provide a lower bound by LP-relaxation, which we show to be equivalent to a multi-commodity flow problem. Further, we examine what impact symmetry has on the solutions. Supported both by computational results as well as by theoretical analysis, we reach the conclusion that symmetric line plans are optimal or near-optimal in the Parametric City. Restricting the model to symmetric line plans allows for a \kappa-factor approximation algorithm for the line planning problem in the Parametric City.}, language = {en} } @masterthesis{Lange, type = {Bachelor Thesis}, author = {Lange, Johanna}, title = {A Decomposition and Dualization Approach to the Periodic Event Scheduling Problem}, abstract = {Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, f{\"u}r gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschr{\"a}nkungen, die zu erf{\"u}llen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrpl{\"a}nen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabl{\"a}ufen. Mathematisch k{\"o}nnen diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur L{\"o}sung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zun{\"a}chst die notwendigen graphentheoretischen Grundlagen und das PESP eingef{\"u}hrt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Daf{\"u}r ist eine weitere Nebenbedingung n{\"o}tig. Im f{\"u}nften Kapitel behandeln wir die L{\"o}sung des teildualisierten PESP. Eine M{\"o}glichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschr{\"a}nken. Eine weitere M{\"o}glichkeit ist ein Algorithmus, der{\"a}hnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet.}, language = {en} } @misc{Kuehner, type = {Master Thesis}, author = {K{\"u}hner, Arno}, title = {Shortest Paths with Boolean Constraints}, abstract = {For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.}, language = {en} } @misc{Bortoletto, type = {Master Thesis}, author = {Bortoletto, Enrico}, title = {The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm}, abstract = {We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.}, language = {en} } @masterthesis{Kraus, type = {Bachelor Thesis}, author = {Kraus, Luitgard}, title = {A Label Setting Multiobjective Shortest Path FPTAS}, abstract = {Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.}, language = {en} } @misc{Rahmati, type = {Master Thesis}, author = {Rahmati, Niloofar}, title = {Resource Constrained APSP-Algorithm with Possible Reloading Stops}, language = {en} } @masterthesis{Wende, type = {Bachelor Thesis}, author = {Wende, Florian}, title = {Dynamic Load Balancing on Massively Parallel Computer Architectures}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42166}, school = {Zuse Institute Berlin (ZIB)}, pages = {100}, abstract = {This thesis reports on using dynamic load balancing methods on massively parallel computers in the context of multithreaded computations. In particular we investigate the applicability of a randomized work stealing algorithm to ray tracing and breadth-first search as representatives of real-world applications with dynamic work creation. For our considerations we made use of current massively parallel hardware accelerators: Nvidia Tesla M2090, and Intel Xeon Phi. For both of the two we demonstrate the suitability of the work stealing scheme for the said real-world applications. Also the necessity of dynamic load balancing for irregular computations on such hardware is illustrated.}, language = {en} } @misc{WendeSteinke, author = {Wende, Florian and Steinke, Thomas}, title = {Swendsen-Wang Multi-Cluster Algorithm for the 2D/3D Ising Model on Xeon Phi and GPU}, issn = {1438-0064}, doi = {10.1145/2503210.2503254}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42187}, abstract = {Simulations of the critical Ising model by means of local update algorithms suffer from critical slowing down. One way to partially compensate for the influence of this phenomenon on the runtime of simulations is using increasingly faster and parallel computer hardware. Another approach is using algorithms that do not suffer from critical slowing down, such as cluster algorithms. This paper reports on the Swendsen-Wang multi-cluster algorithm on Intel Xeon Phi coprocessor 5110P, Nvidia Tesla M2090 GPU, and x86 multi-core CPU. We present shared memory versions of the said algorithm for the simulation of the two- and three-dimensional Ising model. We use a combination of local cluster search and global label reduction by means of atomic hardware primitives. Further, we describe an MPI version of the algorithm on Xeon Phi and CPU, respectively. Significant performance improvements over known im plementations of the Swendsen-Wang algorithm are demonstrated.}, language = {en} } @misc{Wende, type = {Master Thesis}, author = {Wende, Florian}, title = {Simulation of Spin Models on Nvidia Graphics Cards using CUDA}, school = {Humboldt-Universit{\"a}t zu Berlin}, pages = {149}, abstract = {This thesis reports on simulating spin models on Nvidia graphics cards using the CUDA programming model; a particular approach for making GPGPU (General Purpose Computation on Graphics Processing Units) available for a wide range of software developers not necessarily acquainted with (massively) parallel programming. By comparing program execution times for simulations of the Ising model and the Ising spin glass by means of the Metropolis algorithm on Nvidia Tesla C1060 graphics cards and an Intel Core i7-920 quad-core x86 CPU (we used OpenMP to make our simulations run on all 4 execution units of the CPU), we noticed that the Tesla C1060 performed about a factor 5-10 faster than the Core i7-920, depending on the particular model and the accuracy of the calculations (32-bit or 64-bit). We also investigated the reliability of GPGPU computations, especially with respect to the occurrence of soft-errors as suggested in [23]. We noticed faulty program outputs during long-time simulations of the Ising model on ''large'' lattices. We were able to link these problems to overheating of the corresponding graphics cards. Doing Monte Carlo simulations on parallel computer architectures, as was the case in this thesis, suggests to also generate random numbers in a parallel manner. We present implementations of the random number generators Ranlux and Mersenne Twister. In addition, we give an alternative and very efficient approach for producing parallel random numbers on Nvidia graphics cards. We successfully tested all random number generators used in this thesis for their quality by comparing Monte Carlo estimates against exact calculations.}, language = {en} } @misc{Krause, type = {Master Thesis}, author = {Krause, Jan}, title = {Investigation of Options to Handle 3D MRI Data via Convolutional Neural Networks Application in Knee Osteoarthritits Classification}, pages = {127}, language = {en} } @misc{MaherMiltenbergerPedrosoetal., author = {Maher, Stephen J. and Miltenberger, Matthias and Pedroso, Jo{\~a}o Pedro and Rehfeldt, Daniel and Schwarz, Robert and Serrano, Felipe}, title = {PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite}, issn = {1438-0064}, doi = {10.1007/978-3-319-42432-3_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61348}, abstract = {SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.}, language = {en} } @misc{LindnerLiebchen, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable Merging for the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81587}, abstract = {We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.}, language = {en} } @misc{WitzigGamrathHiller, author = {Witzig, Jakob and Gamrath, Gerald and Hiller, Benjamin}, title = {Reoptimization Techniques in MIP Solvers}, issn = {1438-0064}, doi = {10.1007/978-3-319-20086-6_14}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54375}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @misc{Witzig, type = {Master Thesis}, author = {Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54067}, pages = {176}, abstract = {Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems. In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence. At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this thesis, 2013. Since most of the state-of-the-art MIP solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process.}, language = {en} } @misc{HillerKlugWitzig, author = {Hiller, Benjamin and Klug, Torsten and Witzig, Jakob}, title = {Reoptimization in branch-and-bound algorithms with an application to elevator control}, issn = {1438-0064}, doi = {10.1007/978-3-642-38527-8_33}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17876}, abstract = {We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm. We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.}, language = {en} } @misc{LindnerLiebchen, author = {Lindner, Niels and Liebchen, Christian}, title = {Incremental Heuristics for Periodic Timetabling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92309}, abstract = {We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.}, language = {en} } @misc{BortolettoLindner, author = {Bortoletto, Enrico and Lindner, Niels}, title = {Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92315}, abstract = {The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.}, language = {en} } @misc{OezelKulkarniHasanetal., author = {{\"O}zel, M. Neset and Kulkarni, Abhishek and Hasan, Amr and Brummer, Josephine and Moldenhauer, Marian and Daumann, Ilsa-Maria and Wolfenberg, Heike and Dercksen, Vincent J. and Kiral, F. Ridvan and Weiser, Martin and Prohaska, Steffen and von Kleist, Max and Hiesinger, Peter Robin}, title = {Serial synapse formation through filopodial competition for synaptic seeding factors}, issn = {1438-0064}, doi = {10.1016/j.devcel.2019.06.014}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74397}, abstract = {Following axon pathfinding, growth cones transition from stochastic filopodial exploration to the formation of a limited number of synapses. How the interplay of filopodia and synapse assembly ensures robust connectivity in the brain has remained a challenging problem. Here, we developed a new 4D analysis method for filopodial dynamics and a data-driven computational model of synapse formation for R7 photoreceptor axons in developing Drosophila brains. Our live data support a 'serial synapse formation' model, where at any time point only a single 'synaptogenic' filopodium suppresses the synaptic competence of other filopodia through competition for synaptic seeding factors. Loss of the synaptic seeding factors Syd-1 and Liprin-α leads to a loss of this suppression, filopodial destabilization and reduced synapse formation, which is sufficient to cause the destabilization of entire axon terminals. Our model provides a filopodial 'winner-takes-all' mechanism that ensures the formation of an appropriate number of synapses.}, language = {en} } @misc{LindnerMasing, author = {Lindner, Niels and Masing, Berenike}, title = {On the Split Closure of the Periodic Timetabling Polytope}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91156}, abstract = {The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P \$=\$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances.}, language = {en} } @misc{Shestakov, type = {Master Thesis}, author = {Shestakov, Alexey}, title = {A Deep Learning Method for Automated Detection of Meniscal Tears in Meniscal Sub-Regions in 3D MRI Data}, pages = {96}, abstract = {This work presents a fully automated pipeline, centered around a deep neural network, as well as a method to train that network in an efficient manner, that enables accurate detection of lesions in meniscal anatomical subregions. The network architecture is based on a transformer encoder/decoder. It is trained on DESS and tuned on IW TSE 3D MRI scans sourced from the Osteoarthritis Initiative. Furthermore, it is trained in a multilabel, and multitask fashion, using an auxiliary detection head. The former enables implicit localisation of meniscal defects, that to the best of my knowledge, has not yet been reported elsewhere. The latter enables efficient learning on the entire 3D MRI volume. Thus, the proposed method does not require any expert knowledge at inference. Aggregated inference results from two datasets resulted in an overall AUCROC result of 0.90, 0.91 and 0.93 for meniscal lesion detection anywhere in the knee, in medial and in lateral menisci respectively. These results compare very well to the related work, even though only a fraction of the data has been utilized. Clinical applicability and benefit is yet to be determined.}, language = {en} } @misc{SchieweGoerigkLindner, author = {Schiewe, Philine and Goerigk, Marc and Lindner, Niels}, title = {Introducing TimPassLib - A library for integrated periodic timetabling and passenger routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89741}, abstract = {Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing.}, language = {en} } @misc{MasingLindnerEbert, author = {Masing, Berenike and Lindner, Niels and Ebert, Patricia}, title = {Forward and Line-Based Cycle Bases for Periodic Timetabling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89731}, abstract = {The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.}, language = {en} } @phdthesis{Miltenberger, author = {Miltenberger, Matthias}, title = {Linear Programming in MILP Solving - A Computational Perspective}, publisher = {Verlag Dr. Hut GmbH}, isbn = {9783843953238}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91873}, pages = {237}, abstract = {Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly. This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub.}, language = {en} } @phdthesis{Hanik2023, author = {Hanik, Martin}, title = {Geometric Data Analysis: Advancements of the Statistical Methodology and Applications}, publisher = {Refubium}, doi = {10.17169/refubium-39809}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:188-refubium-40087-8}, pages = {192}, year = {2023}, abstract = {Data analysis has become fundamental to our society and comes in multiple facets and approaches. Nevertheless, in research and applications, the focus was primarily on data from Euclidean vector spaces. Consequently, the majority of methods that are applied today are not suited for more general data types. Driven by needs from fields like image processing, (medical) shape analysis, and network analysis, more and more attention has recently been given to data from non-Euclidean spaces---particularly (curved) manifolds. It has led to the field of geometric data analysis whose methods explicitly take the structure (for example, the topology and geometry) of the underlying space into account. This thesis contributes to the methodology of geometric data analysis by generalizing several fundamental notions from multivariate statistics to manifolds. We thereby focus on two different viewpoints. First, we use Riemannian structures to derive a novel regression scheme for general manifolds that relies on splines of generalized B{\´e}zier curves. It can accurately model non-geodesic relationships, for example, time-dependent trends with saturation effects or cyclic trends. Since B{\´e}zier curves can be evaluated with the constructive de Casteljau algorithm, working with data from manifolds of high dimensions (for example, a hundred thousand or more) is feasible. Relying on the regression, we further develop a hierarchical statistical model for an adequate analysis of longitudinal data in manifolds, and a method to control for confounding variables. We secondly focus on data that is not only manifold- but even Lie group-valued, which is frequently the case in applications. We can only achieve this by endowing the group with an affine connection structure that is generally not Riemannian. Utilizing it, we derive generalizations of several well-known dissimilarity measures between data distributions that can be used for various tasks, including hypothesis testing. Invariance under data translations is proven, and a connection to continuous distributions is given for one measure. A further central contribution of this thesis is that it shows use cases for all notions in real-world applications, particularly in problems from shape analysis in medical imaging and archaeology. We can replicate or further quantify several known findings for shape changes of the femur and the right hippocampus under osteoarthritis and Alzheimer's, respectively. Furthermore, in an archaeological application, we obtain new insights into the construction principles of ancient sundials. Last but not least, we use the geometric structure underlying human brain connectomes to predict cognitive scores. Utilizing a sample selection procedure, we obtain state-of-the-art results.}, language = {en} } @phdthesis{Chewle, author = {Chewle, Surahit}, title = {Probing effects of organic solvents on paracetamol crystallization using in silico and orthogonal in situ methods}, abstract = {Polymorphism is the property exhibited by many inorganic and organic molecules to crystallize in more than one crystal structure. There is a strong need for understanding the influencing factors on polymorphism, as it is responsible for differences in many physicochemical properties such as stability and solubility. Nearly 80 \% of marketed drugs exhibit polymorphism. In this work, we took the model system of paracetamol to investigate the influence of solvent choice on its polymorphism. Different methods were developed and employed to understand the influence of small organic solvents on the crystallization of paracetamol. Non-equilibrium molecular dynamics simulations with periodic simulated annealing were used as a tool to probe the nature of precursors of the metastable intermediates occurring in the crystallization process. Using this method, it was found that the structures of the building blocks of crystals of paracetamol is governed by solvent-solute interactions. In situ Raman spectroscopy was used with a custom-made acoustic levitator to follow crystallization. This set-up is a reliable method for investigating solvent influence, attenuating heterogeneous nucleation and stabilizing other environmental factors. It was established that as a solvent, ethanol is much stronger than methanol in its effect of driving paracetamol solutions to their crystal form. The time-resolved Raman spectroscopy crystallization data was processed using a newly developed objective function based non-negative matrix factorization method (NMF). An orthogonal time-lapse photography was used in conjunction with NMF to get unique and accurate factors that pertain to the spectra and concentrations of different moieties of paracetamol crystallization existing as latent components in the untreated data.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of Cycle Inequalities in Periodic Timetabling}, issn = {1438-0064}, doi = {https://doi.org/10.1016/j.disopt.2019.100552}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69746}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @misc{TateiwaShinanoYasudaetal., author = {Tateiwa, Nariaki and Shinano, Yuji and Yasuda, Masaya and Kaji, Shizuo and Yamamura, Keiichiro and Fujisawa, Katsuki}, title = {Massively parallel sharing lattice basis reduction}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85209}, abstract = {For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments.}, language = {en} } @misc{LindnerMasing, author = {Lindner, Niels and Masing, Berenike}, title = {SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-94644}, abstract = {Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turnarounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.}, language = {en} }