@misc{LindowBruenigDercksenetal.2019, author = {Lindow, Norbert and Br{\"u}nig, Florian and Dercksen, Vincent J. and Fabig, Gunar and Kiewisz, Robert and Redemann, Stefanie and M{\"u}ller-Reichert, Thomas and Prohaska, Steffen}, title = {Semi-automatic Stitching of Serial Section Image Stacks with Filamentous Structures}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73739}, year = {2019}, abstract = {In this paper, we present a software-assisted workflow for the alignment and matching of filamentous structures across a stack of 3D serial image sections. This is achieved by a combination of automatic methods, visual validation, and interactive correction. After an initial alignment, the user can continuously improve the result by interactively correcting landmarks or matches of filaments. This is supported by a quality assessment that visualizes regions that have been already inspected and, thus, allows a trade-off between quality and manual labor. The software tool was developed in collaboration with biologists who investigate microtubule-based spindles during cell division. To quantitatively understand the structural organization of such spindles, a 3D reconstruction of the numerous microtubules is essential. Each spindle is cut into a series of semi-thick physical sections, of which electron tomograms are acquired. The sections then need to be stitched, i.e. non-rigidly aligned; and the microtubules need to be traced in each section and connected across section boundaries. Experiments led to the conclusion that automatic methods for stitching alone provide only an incomplete solution to practical analysis needs. Automatic methods may fail due to large physical distortions, a low signal-to-noise ratio of the images, or other unexpected experimental difficulties. In such situations, semi-automatic validation and correction is required to rescue as much information as possible to derive biologically meaningful results despite of some errors related to data collection. Since the correct stitching is visually not obvious due to the number of microtubules (up to 30k) and their dense spatial arrangement, these are difficult tasks. Furthermore, a naive inspection of each microtubule is too time consuming. In addition, interactive visualization is hampered by the size of the image data (up to 100 GB). Based on the requirements of our collaborators, we present a practical solution for the semi-automatic stitching of serial section image stacks with filamentous structures.}, language = {en} } @misc{MuellerMuñozGasseetal.2019, author = {M{\"u}ller, Benjamin and Muñoz, Gonzalo and Gasse, Maxime and Gleixner, Ambros and Lodi, Andrea and Serrano, Felipe}, title = {On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75179}, year = {2019}, abstract = {The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.}, language = {en} } @misc{OmariPloentzkeRoeblitz2019, author = {Omari, Mohamed and Pl{\"o}ntzke, Julia and R{\"o}blitz, Susanna}, title = {A pharmacokinetic-pharmacodynamic model for single dose administration of Dexamethasone in dairy cows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75043}, year = {2019}, abstract = {We present a mechanistic pharmacokinetic-pharmacodynamic model to simulate the effect of dexamethasone on the glucose metabolism in dairy cows. The coupling of the pharmacokinetic model to the pharmacodynamic model is based on mechanisms underlying homeostasis regulation by dexamethasone. In particular, the coupling takes into account the predominant role of dexamethasone in stimulating glucagon secretion, glycogenolysis and lipolysis and in impairing the sensitivity of cells to insulin. Simulating the effect of a single dose of dexamethasone on the physiological behaviour of the system shows that the adopted mechanisms are able to induce a temporary hyperglycemia and hyperinsulinemia, which captures the observed data in non-lactating cows. In lactating cows, the model simulations show that a single dose of dexamethasone reduces the lipolytic effect, owing to the reduction of glucose uptake by the mammary gland.}, language = {en} } @misc{WitzigBertholdHeinz2019, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Computational Aspects of Infeasibility Analysis in Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74962}, year = {2019}, abstract = {The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.}, language = {en} } @misc{ChenKochXu2019, author = {Chen, Ying and Koch, Thorsten and Xu, Xiaofei}, title = {Regularized partially functional autoregressive model with application to high-resolution natural gas forecasting in Germany}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74880}, year = {2019}, abstract = {We propose a partially functional autoregressive model with exogenous variables (pFAR) to describe the dynamic evolution of the serially correlated functional data. It provides a unit� ed framework to model both the temporal dependence on multiple lagged functional covariates and the causal relation with ultrahigh-dimensional exogenous scalar covariates. Estimation is conducted under a two-layer sparsity assumption, where only a few groups and elements are supposed to be active, yet without knowing their number and location in advance. We establish asymptotic properties of the estimator and investigate its unite sample performance along with simulation studies. We demonstrate the application of pFAR with the high-resolution natural gas flows in Germany, where the pFAR model provides insightful interpretation as well as good out-of-sample forecast accuracy.}, language = {en} } @misc{ChristgauSchnor2019, author = {Christgau, Steffen and Schnor, Bettina}, title = {MPI Passive Target Synchronization on a Non-Cache-Coherent Shared-Memory Processor}, issn = {1438-0064}, doi = {10.12752/7477}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74774}, year = {2019}, abstract = {MPI passive target synchronization offers exclusive and shared locks. These are the building blocks for the implementation of applications with Readers \& Writers semantic, like for example distributed hash tables. This paper discusses the implementation of MPI passive target synchronization on a non-cache-coherent multicore, the Intel Single-Chip Cloud Computer. The considered algorithms differ in their communication style (message based versus shared memory), their data structures (centralized versus distributed) and their semantics (with/without Writer preference). It is shown that shared memory approaches scale very well and deliver good performance, even in absence of cache coherence.}, language = {en} } @misc{MaherRalphsShinano2019, author = {Maher, Stephen J. and Ralphs, Ted and Shinano, Yuji}, title = {Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74702}, year = {2019}, abstract = {Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that resource consumption is at the heart of what we generally refer to as the "effectiveness" of an implementation. The proposed framework carefully distinguishes between an implementation's baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment.}, language = {en} } @misc{SahinAhmadiBorndoerferetal.2019, author = {Sahin, Guvenc and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Multi-Period Line Planning with Resource Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74662}, year = {2019}, abstract = {Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.}, language = {en} } @misc{GotzesHoppmann2019, author = {Gotzes, Uwe and Hoppmann, Kai}, title = {Bounds for the final ranks during a round robin tournament}, journal = {Operational Research - An International Journal (ORIJ)}, doi = {https://doi.org/10.1007/s12351-020-00546-w}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74638}, year = {2019}, abstract = {This article answers two kinds of questions regarding the Bundesliga which is Germany's primary football (soccer) competition having the highest average stadium attendance worldwide. First "At any point of the season, what final rank will a certain team definitely reach?" and second "At any point of the season, what final rank can a certain team at most reach?". Although we focus especially on the Bundesliga, the models that we use to answer the two questions can easily be adopted to league systems that are similar to that of the Bundesliga.}, language = {en} } @misc{NavaYazdaniHegevonTycowicz2019, author = {Nava-Yazdani, Esfandiar and Hege, Hans-Christian and von Tycowicz, Christoph}, title = {A Geodesic Mixed Effects Model in Kendall's Shape Space}, journal = {Proc. 7th MICCAI workshop on Mathematical Foundations of Computational Anatomy (MFCA)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74621}, year = {2019}, abstract = {In many applications, geodesic hierarchical models are adequate for the study of temporal observations. We employ such a model derived for manifold-valued data to Kendall's shape space. In particular, instead of the Sasaki metric, we adapt a functional-based metric, which increases the computational efficiency and does not require the implementation of the curvature tensor. We propose the corresponding variational time discretization of geodesics and apply the approach for the estimation of group trends and statistical testing of 3D shapes derived from an open access longitudinal imaging study on osteoarthritis.}, language = {en} } @misc{GoetschelSchielaWeiser2019, author = {G{\"o}tschel, Sebastian and Schiela, Anton and Weiser, Martin}, title = {Kaskade 7 -- a Flexible Finite Element Toolbox}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74616}, year = {2019}, abstract = {Kaskade 7 is a finite element toolbox for the solution of stationary or transient systems of partial differential equations, aimed at supporting application-oriented research in numerical analysis and scientific computing. The library is written in C++ and is based on the Dune interface. The code is independent of spatial dimension and works with different grid managers. An important feature is the mix-and-match approach to discretizing systems of PDEs with different ansatz and test spaces for all variables. We describe the mathematical concepts behind the library as well as its structure, illustrating its use at several examples on the way.}, language = {en} } @misc{AmbellanZachowvonTycowicz2019, author = {Ambellan, Felix and Zachow, Stefan and von Tycowicz, Christoph}, title = {An as-invariant-as-possible GL+(3)-based Statistical Shape Model}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74566}, year = {2019}, abstract = {We describe a novel nonlinear statistical shape model basedon differential coordinates viewed as elements of GL+(3). We adopt an as-invariant-as possible framework comprising a bi-invariant Lie group mean and a tangent principal component analysis based on a unique GL+(3)-left-invariant, O(3)-right-invariant metric. Contrary to earlier work that equips the coordinates with a specifically constructed group structure, our method employs the inherent geometric structure of the group-valued data and therefore features an improved statistical power in identifying shape differences. We demonstrate this in experiments on two anatomical datasets including comparison to the standard Euclidean as well as recent state-of-the-art nonlinear approaches to statistical shape modeling.}, language = {en} } @misc{AmbellanZachowvonTycowicz2019, author = {Ambellan, Felix and Zachow, Stefan and von Tycowicz, Christoph}, title = {A Surface-Theoretic Approach for Statistical Shape Modeling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74497}, year = {2019}, abstract = {We present a novel approach for nonlinear statistical shape modeling that is invariant under Euclidean motion and thus alignment-free. By analyzing metric distortion and curvature of shapes as elements of Lie groups in a consistent Riemannian setting, we construct a framework that reliably handles large deformations. Due to the explicit character of Lie group operations, our non-Euclidean method is very efficient allowing for fast and numerically robust processing. This facilitates Riemannian analysis of large shape populations accessible through longitudinal and multi-site imaging studies providing increased statistical power. We evaluate the performance of our model w.r.t. shape-based classification of pathological malformations of the human knee and show that it outperforms the standard Euclidean as well as a recent nonlinear approach especially in presence of sparse training data. To provide insight into the model's ability of capturing natural biological shape variability, we carry out an analysis of specificity and generalization ability.}, language = {en} } @misc{Baum2019, author = {Baum, Daniel}, title = {An Evaluation of Color Maps for Visual Data Exploration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74259}, year = {2019}, language = {en} } @misc{MahnkeArltBaumetal.2019, author = {Mahnke, Heinz-Eberhard and Arlt, Tobias and Baum, Daniel and Hege, Hans-Christian and Herter, Felix and Lindow, Norbert and Manke, Ingo and Siopi, Tzulia and Menei, Eve and Etienne, Marc and Lepper, Verena}, title = {Virtual unfolding of folded papyri}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74338}, year = {2019}, abstract = {The historical importance of ancient manuscripts is unique since they provide information about the heritage of ancient cultures. Often texts are hidden in rolled or folded documents. Due to recent impro- vements in sensitivity and resolution, spectacular disclosures of rolled hidden texts were possible by X-ray tomography. However, revealing text on folded manuscripts is even more challenging. Manual unfolding is often too risky in view of the fragile condition of fragments, as it can lead to the total loss of the document. X-ray tomography allows for virtual unfolding and enables non-destructive access to hid- den texts. We have recently demonstrated the procedure and tested unfolding algorithms on a mockup sample. Here, we present results on unfolding ancient papyrus packages from the papyrus collection of the Mus{\´e}e du Louvre, among them objects folded along approximately orthogonal folding lines. In one of the packages, the first identification of a word was achieved, the Coptic word for "Lord".}, language = {en} } @misc{OezelKulkarniHasanetal.2019, 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}, year = {2019}, 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{BehrensBertelmannBoltzeetal.2019, author = {Behrens, Kathrin and Bertelmann, Roland and Boltze, Julia and Ceynowa, Klaus and Christof, J{\"u}rgen and Dierkes, Thomas and Goltz-Fellgiebel, Julia Alexandra and Groß, Matthias and Hammerl, Michaela and Haoua, Marsa and Heermann, Petra and Hoffmann, Cornelia and H{\"o}hnow, Tobias and Koch, Thorsten and Kuberek, Monika and Pampel, Heinz and Putnings, Markus and Rusch, Beate and Sch{\"a}ffler, Hildegard and Schwidder, Jens and S{\"o}llner, Konstanze and Staub, Hedda and Wannick, Eike}, title = {DeepGreen - Open Access Transformation: Eine Handreichung f{\"u}r institutionelle Repositorien}, issn = {1438-0064}, doi = {10.12752/7443}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74438}, year = {2019}, abstract = {Mit dem DFG-gef{\"o}rderten Projekt DeepGreen soll eine automatisierte, rechtssichere L{\"o}sung entwickelt werden, um Artikeldaten von wissenschaftlichen Verlagen abzuholen und anschließend, nach Ablauf etwaiger lizenzrechtlicher Embargofristen, an berechtigte Repositorien zu verteilen und somit in den Open Access zu {\"u}berf{\"u}hren. Dabei liegt der Fokus auf den DFG-gef{\"o}rderten und {\"u}berregional verhandelten Allianz-Lizenzen, mit spezieller Open-Access-Komponente. Die vorliegende Handreichung richtet sich speziell an die Betreiber institutioneller Repositorien und stellt Empfehlungen und einen Workflow bereit, um eine erfolgreiche Ver{\"o}ffentlichung, der durch die DeepGreen-Datendrehscheibe zugeordneten Artikel, zu erm{\"o}glichen. Die Handreichung basiert auf den bisherigen Erfahrungen der DeepGreen-Projektbeteiligten.}, language = {de} } @misc{BreugemBorndoerferSchlechteetal.2019, author = {Breugem, Thomas and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Schulz, Christof}, title = {A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74297}, year = {2019}, abstract = {In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20\% in just a few minutes.}, language = {en} } @misc{RehfeldtHobbieSchoenheitetal.2019, author = {Rehfeldt, Daniel and Hobbie, Hannes and Sch{\"o}nheit, David and Gleixner, Ambros and Koch, Thorsten and M{\"o}st, Dominik}, title = {A massively parallel interior-point solver for linear energy system models with block structure}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74321}, year = {2019}, abstract = {Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market clearing. It has been widely applied in the literature on energy system analyses during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.}, language = {en} } @misc{GleixnerKempkeKochetal.2019, author = {Gleixner, Ambros and Kempke, Nils-Christian and Koch, Thorsten and Rehfeldt, Daniel and Uslu, Svenja}, title = {First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method}, issn = {1438-0064}, doi = {10.1007/978-3-030-48439-2_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74084}, year = {2019}, abstract = {In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.}, language = {en} } @misc{Serrano2019, author = {Serrano, Felipe}, title = {Visible points, the separation problem, and applications to MINLP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74016}, year = {2019}, abstract = {In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{visible points} of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide.}, language = {en} } @misc{GrimmBorndoerferSchlechte2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73976}, year = {2019}, abstract = {Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.}, language = {en} } @misc{LoebelLindnerBorndoerfer2019, 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}, year = {2019}, 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{LindnerLiebchen2019, 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}, year = {2019}, 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{BaumWeaverZlotnikovetal.2019, author = {Baum, Daniel and Weaver, James C. and Zlotnikov, Igor and Kn{\"o}tel, David and Tomholt, Lara and Dean, Mason N.}, title = {High-Throughput Segmentation of Tiled Biological Structures using Random-Walk Distance Transforms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73841}, year = {2019}, abstract = {Various 3D imaging techniques are routinely used to examine biological materials, the results of which are usually a stack of grayscale images. In order to quantify structural aspects of the biological materials, however, they must first be extracted from the dataset in a process called segmentation. If the individual structures to be extracted are in contact or very close to each other, distance-based segmentation methods utilizing the Euclidean distance transform are commonly employed. Major disadvantages of the Euclidean distance transform, however, are its susceptibility to noise (very common in biological data), which often leads to incorrect segmentations (i.e. poor separation of objects of interest), and its limitation of being only effective for roundish objects. In the present work, we propose an alternative distance transform method, the random-walk distance transform, and demonstrate its effectiveness in high-throughput segmentation of three microCT datasets of biological tilings (i.e. structures composed of a large number of similar repeating units). In contrast to the Euclidean distance transform, this random-walk approach represents the global, rather than the local, geometric character of the objects to be segmented and, thus, is less susceptible to noise. In addition, it is directly applicable to structures with anisotropic shape characteristics. Using three case studies—stingray tessellated cartilage, starfish dermal endoskeleton, and the prismatic layer of bivalve mollusc shell—we provide a typical workflow for the segmentation of tiled structures, describe core image processing concepts that are underused in biological research, and show that for each study system, large amounts of biologically-relevant data can be rapidly segmented, visualized and analyzed.}, language = {en} } @misc{GoetschelWeiser2019, author = {G{\"o}tschel, Sebastian and Weiser, Martin}, title = {Lossy Compression for Large Scale PDE Problems}, issn = {1438-0064}, doi = {10.1101/506378}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73817}, year = {2019}, abstract = {Solvers for partial differential equations (PDE) are one of the cornerstones of computational science. For large problems, they involve huge amounts of data that needs to be stored and transmitted on all levels of the memory hierarchy. Often, bandwidth is the limiting factor due to relatively small arithmetic intensity, and increasingly so due to the growing disparity between computing power and bandwidth. Consequently, data compression techniques have been investigated and tailored towards the specific requirements of PDE solvers during the last decades. This paper surveys data compression challenges and corresponding solution approaches for PDE problems, covering all levels of the memory hierarchy from mass storage up to main memory. Exemplarily, we illustrate concepts at particular methods, and give references to alternatives.}, language = {en} } @misc{PetkovicChenGamrathetal.2019, author = {Petkovic, Milena and Chen, Ying and Gamrath, Inken and Gotzes, Uwe and Hadjidimitriou, Natalia Selini and Zittel, Janina and Xu, Xiaofei and Koch, Thorsten}, title = {A Hybrid Approach for High Precision Prediction of Gas Flows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73525}, year = {2019}, abstract = {About 20\% of the German energy demand is supplied by natural gas. Ad- ditionally, for about twice the amount Germany serves as a transit country. Thereby, the German network represents a central hub in the European natural gas transport network. The transport infrastructure is operated by so-called transmissions system operators or TSOs. The number one priority of the TSOs is to ensure security of supply. However, the TSOs have no knowledge of the intentions and planned actions of the shippers (traders). Open Grid Europe (OGE), one of Germany's largest TSO, operates a high- pressure transport network of about 12.000 km length. Since flexibility and security of supply is of utmost importance to the German Energy Transition ("Energiewende") especially with the introduction of peak-load gas power stations, being able to predict in- and out-flow of the network is of great importance. In this paper we introduce a new hybrid forecast method applied to gas flows at the boundary nodes of a transport network. The new method employs optimized feature minimization and selection. We use a combination of an FAR, LSTM DNN and mathematical programming to achieve robust high quality forecasts on real world data for different types of network nodes. Keywords: Gas Forecast, Time series, Hybrid Method, FAR, LSTM, Mathematical Optimisation}, language = {en} } @misc{GamrathPetkovic2019, author = {Gamrath, Inken and Petkovic, Milena}, title = {Prediction of Intermitted Flows in Large Gas Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73717}, year = {2019}, language = {en} } @misc{BorndoerferElijazyferSchwartz2019, author = {Bornd{\"o}rfer, Ralf and Elijazyfer, Ziena and Schwartz, Stephan}, title = {Approximating Balanced Graph Partitions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73675}, year = {2019}, abstract = {We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a \$\Delta\$-approximation where \$\Delta\$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.}, language = {en} } @misc{HoppmannHenningsLenzetal.2019, author = {Hoppmann, Kai and Hennings, Felix and Lenz, Ralf and Gotzes, Uwe and Heinecke, Nina and Spreckelsen, Klaus and Koch, Thorsten}, title = {Optimal Operation of Transient Gas Transport Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73639}, year = {2019}, language = {en} } @misc{HenningsAndersonHoppmannetal.2019, author = {Hennings, Felix and Anderson, Lovis and Hoppmann, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73645}, year = {2019}, abstract = {Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach.}, language = {en} } @misc{OmariLangePloentzkeetal.2019, author = {Omari, Mohamed and Lange, Alexander and Pl{\"o}ntzke, Julia and R{\"o}blitz, Susanna}, title = {A Mathematical Model for the Influence of Glucose-Insulin Dynamics on the Estrous Cycle in Dairy Cows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73475}, year = {2019}, abstract = {Nutrition plays a crucial role in regulating reproductive hormones and follicular development in cattle. This is visible particularly during the time of negative energy balance at the onset of milk production after calving. Here, elongated periods of anovulation have been observed, resulting from alterations in luteiniz- ing hormone concentrations, likely caused by lower glucose and insulin concen- trations in the blood. The mechanisms that result in a reduced fertility are not completely understood, although a close relationship to the glucose-insulin metabolism is widely supported. Following this idea, a mathematical model of the hormonal network combining reproductive hormones and hormones that are coupled to the glucose compartments within the body of the cow was developed. The model is built on ordinary differential equations and relies on previously introduced models on the bovine estrous cycle and the glucose-insulin dynam- ics. Necessary modifications and coupling mechanisms are thoroughly discussed. Depending on the composition and the amount of food, in particular the glu- cose content in the dry matter, the model quantifies reproductive hormones and follicular development over time. Simulation results for different nutritional regimes in lactating and non-lactating dairy cows are examined and compared with experimental studies. Regarding its applicability, this work is an early attempt towards developing in silico feeding strategies and may eventually help refining and reducing animal experiments.}, language = {en} } @misc{HelfmannDjurdjevacConradDjurdjevacetal.2019, author = {Helfmann, Luzie and Djurdjevac Conrad, Natasa and Djurdjevac, Ana and Winkelmann, Stefanie and Sch{\"u}tte, Christof}, title = {From interacting agents to density-based modeling with stochastic PDEs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73456}, year = {2019}, abstract = {Many real-world processes can naturally be modeled as systems of interacting agents. However, the long-term simulation of such agent-based models is often intractable when the system becomes too large. In this paper, starting from a stochastic spatio-temporal agent-based model (ABM), we present a reduced model in terms of stochastic PDEs that describes the evolution of agent number densities for large populations. We discuss the algorithmic details of both approaches; regarding the SPDE model, we apply Finite Element discretization in space which not only ensures efficient simulation but also serves as a regularization of the SPDE. Illustrative examples for the spreading of an innovation among agents are given and used for comparing ABM and SPDE models.}, language = {en} } @misc{Hoppmann2019, author = {Hoppmann, Kai}, title = {On the Complexity of the Maximum Minimum Cost Flow Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73359}, year = {2019}, abstract = {Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity and an associated length, together with nonempty supply-intervals for the sources and nonempty demand-intervals for the sinks. The goal of the Maximum Minimum Cost Flow Problem (MMCF) is to find fixed supply and demand values within these intervals, such that the optimal objective value of the induced Minimum Cost Flow Problem (MCF) is maximized. In this paper, we show that MMCF is APX-hard and remains NP-hard in the uncapacitated case.}, language = {en} } @misc{SerranoSchwarzGleixner2019, author = {Serrano, Felipe and Schwarz, Robert and Gleixner, Ambros}, title = {On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley's Cutting Plane Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73253}, year = {2019}, abstract = {Recently, Kronqvist et al. (2016) rediscovered the supporting hyperplane algorithm of Veinott (1967) and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by general, not necessarily convex, differentiable functions that satisfy a mild condition.}, language = {en} } @misc{BertholdGamrathSalvagnin2019, author = {Berthold, Timo and Gamrath, Gerald and Salvagnin, Domenico}, title = {Exploiting Dual Degeneracy in Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73028}, year = {2019}, abstract = {Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 \% on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 \% on average.}, language = {en} } @misc{BuchmannKaplanPowelletal.2019, 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}, year = {2019}, 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{ShinanoRehfeldtGalley2019, author = {Shinano, Yuji and Rehfeldt, Daniel and Galley, Tristan}, title = {An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-libraries}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72804}, year = {2019}, abstract = {Branch-and-bound (B\&B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B\&B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks.The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries---by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.}, language = {en} } @misc{MuellerSerranoGleixner2019, author = {M{\"u}ller, Benjamin and Serrano, Felipe and Gleixner, Ambros}, title = {Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72759}, year = {2019}, abstract = {One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.}, language = {en} } @misc{AmbellanTackEhlkeetal.2019, author = {Ambellan, Felix and Tack, Alexander and Ehlke, Moritz and Zachow, Stefan}, title = {Automated Segmentation of Knee Bone and Cartilage combining Statistical Shape Knowledge and Convolutional Neural Networks: Data from the Osteoarthritis Initiative}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72704}, year = {2019}, abstract = {We present a method for the automated segmentation of knee bones and cartilage from magnetic resonance imaging (MRI) that combines a priori knowledge of anatomical shape with Convolutional Neural Networks (CNNs).The proposed approach incorporates 3D Statistical Shape Models (SSMs) as well as 2D and 3D CNNs to achieve a robust and accurate segmentation of even highly pathological knee structures.The shape models and neural networks employed are trained using data from the Osteoarthritis Initiative (OAI) and the MICCAI grand challenge "Segmentation of Knee Images 2010" (SKI10), respectively. We evaluate our method on 40 validation and 50 submission datasets from the SKI10 challenge.For the first time, an accuracy equivalent to the inter-observer variability of human readers is achieved in this challenge.Moreover, the quality of the proposed method is thoroughly assessed using various measures for data from the OAI, i.e. 507 manual segmentations of bone and cartilage, and 88 additional manual segmentations of cartilage. Our method yields sub-voxel accuracy for both OAI datasets. We make the 507 manual segmentations as well as our experimental setup publicly available to further aid research in the field of medical image segmentation.In conclusion, combining localized classification via CNNs with statistical anatomical knowledge via SSMs results in a state-of-the-art segmentation method for knee bones and cartilage from MRI data.}, language = {en} } @misc{AmbellanLameckervonTycowiczetal.2019, author = {Ambellan, Felix and Lamecker, Hans and von Tycowicz, Christoph and Zachow, Stefan}, title = {Statistical Shape Models - Understanding and Mastering Variation in Anatomy}, issn = {1438-0064}, doi = {10.1007/978-3-030-19385-0_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72699}, year = {2019}, abstract = {In our chapter we are describing how to reconstruct three-dimensional anatomy from medical image data and how to build Statistical 3D Shape Models out of many such reconstructions yielding a new kind of anatomy that not only allows quantitative analysis of anatomical variation but also a visual exploration and educational visualization. Future digital anatomy atlases will not only show a static (average) anatomy but also its normal or pathological variation in three or even four dimensions, hence, illustrating growth and/or disease progression. Statistical Shape Models (SSMs) are geometric models that describe a collection of semantically similar objects in a very compact way. SSMs represent an average shape of many three-dimensional objects as well as their variation in shape. The creation of SSMs requires a correspondence mapping, which can be achieved e.g. by parameterization with a respective sampling. If a corresponding parameterization over all shapes can be established, variation between individual shape characteristics can be mathematically investigated. We will explain what Statistical Shape Models are and how they are constructed. Extensions of Statistical Shape Models will be motivated for articulated coupled structures. In addition to shape also the appearance of objects will be integrated into the concept. Appearance is a visual feature independent of shape that depends on observers or imaging techniques. Typical appearances are for instance the color and intensity of a visual surface of an object under particular lighting conditions, or measurements of material properties with computed tomography (CT) or magnetic resonance imaging (MRI). A combination of (articulated) statistical shape models with statistical models of appearance lead to articulated Statistical Shape and Appearance Models (a-SSAMs).After giving various examples of SSMs for human organs, skeletal structures, faces, and bodies, we will shortly describe clinical applications where such models have been successfully employed. Statistical Shape Models are the foundation for the analysis of anatomical cohort data, where characteristic shapes are correlated to demographic or epidemiologic data. SSMs consisting of several thousands of objects offer, in combination with statistical methods ormachine learning techniques, the possibility to identify characteristic clusters, thus being the foundation for advanced diagnostic disease scoring.}, language = {en} } @misc{AndersonHendelLeBodicetal.2019, author = {Anderson, Daniel and Hendel, Gregor and Le Bodic, Pierre and Viernickel, Jan Merlin}, title = {Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72653}, year = {2019}, abstract = {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.}, language = {en} } @misc{SakuraiOnoCarretal.2019, author = {Sakurai, Daisuke and Ono, Kenji and Carr, Hamish and Nonaka, Jorji and Kawanabe, Tomohiro}, title = {Flexible Fiber Surfaces: A Reeb-Free Approach}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72599}, year = {2019}, abstract = {The fiber surface generalizes the popular isosurface to multi-fields, so that pre-images can be visualized as surfaces. As with the isosurface, however, the fiber surface suffers from visual occlusion. We propose to avoid such occlusion by restricting the components to only the relevant ones with a new component-wise flexing algorithm. The approach, flexible fiber surface, generalizes the manipulation idea found in the flexible isosurface for the fiber surface. The flexible isosurface in the original form, however, relies on the contour tree. For the fiber surface, this corresponds to the Reeb space, which is challenging for both the computation and user interaction. We thus take a Reeb-free approach, in which one does not compute the Reeb space. Under this constraint, we generalize a few selected interactions in the flexible isosurface and discuss the implication of the restriction.}, language = {en} } @misc{SakuraiHegeKuhnetal.2017, author = {Sakurai, Daisuke and Hege, Hans-Christian and Kuhn, Alexander and Rust, Henning and Kern, Bastian and Breitkopf, Tom-Lukas}, title = {An Application-Oriented Framework for Feature Tracking in Atmospheric Sciences}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72617}, year = {2017}, abstract = {In atmospheric sciences, sizes of data sets grow continuously due to increasing resolutions. A central task is the comparison of spatiotemporal fields, to assess different simulations and to compare simulations with observations. A significant information reduction is possible by focusing on geometric-topological features of the fields or on derived meteorological objects. Due to the huge size of the data sets, spatial features have to be extracted in time slices and traced over time. Fields with chaotic component, i.e. without 1:1 spatiotemporal correspondences, can be compared by looking upon statistics of feature properties. Feature extraction, however, requires a clear mathematical definition of the features - which many meteorological objects still lack. Traditionally, object extractions are often heuristic, defined only by implemented algorithms, and thus are not comparable. This work surveys our framework designed for efficient development of feature tracking methods and for testing new feature definitions. The framework supports well-established visualization practices and is being used by atmospheric researchers to diagnose and compare data.}, language = {en} } @misc{WitzigGleixner2019, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2020.0973}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72204}, year = {2019}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @misc{BorndoerferLindnerRoth2019, author = {Bornd{\"o}rfer, Ralf and Lindner, Niels and Roth, Sarah}, title = {A Concurrent Approach to the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71907}, year = {2019}, abstract = {We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.}, language = {en} } @misc{GoetschelMinion2019, author = {G{\"o}tschel, Sebastian and Minion, Michael L.}, title = {An Efficient Parallel-in-Time Method for Optimization with Parabolic PDEs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71490}, year = {2019}, abstract = {To solve optimization problems with parabolic PDE constraints, often methods working on the reduced objective functional are used. They are computationally expensive due to the necessity of solving both the state equation and a backward-in-time adjoint equation to evaluate the reduced gradient in each iteration of the optimization method. In this study, we investigate the use of the parallel-in-time method PFASST in the setting of PDE constrained optimization. In order to develop an efficient fully time-parallel algorithm we discuss different options for applying PFASST to adjoint gradient computation, including the possibility of doing PFASST iterations on both the state and adjoint equations simultaneously. We also explore the additional gains in efficiency from reusing information from previous optimization iterations when solving each equation. Numerical results for both a linear and a non-linear reaction-diffusion optimal control problem demonstrate the parallel speedup and efficiency of different approaches.}, language = {en} } @misc{TackZachow2019, author = {Tack, Alexander and Zachow, Stefan}, title = {Accurate Automated Volumetry of Cartilage of the Knee using Convolutional Neural Networks: Data from the Osteoarthritis Initiative}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71439}, year = {2019}, abstract = {Volumetry of the cartilage of the knee, as needed for the assessment of knee osteoarthritis (KOA), is typically performed in a tedious and subjective process. We present an automated segmentation-based method for the quantification of cartilage volume by employing 3D Convolutional Neural Networks (CNNs). CNNs were trained in a supervised manner using magnetic resonance imaging data as well as cartilage volumetry readings given by clinical experts for 1378 subjects. It was shown that 3D CNNs can be employed for cartilage volumetry with an accuracy similar to expert volumetry readings. In future, accurate automated cartilage volumetry might support both, diagnosis of KOA as well as assessment of KOA progression via longitudinal analysis.}, language = {en} } @misc{GrimmBorndoerferSchulzetal.2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71339}, year = {2019}, abstract = {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.}, language = {en} } @misc{SchneckWeiserWende2019, author = {Schneck, Jakob and Weiser, Martin and Wende, Florian}, title = {Impact of mixed precision and storage layout on additive Schwarz smoothers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71305}, year = {2019}, abstract = {The growing discrepancy between CPU computing power and memory bandwidth drives more and more numerical algorithms into a bandwidth- bound regime. One example is the overlapping Schwarz smoother, a highly effective building block for iterative multigrid solution of elliptic equations with higher order finite elements. Two options of reducing the required memory bandwidth are sparsity exploiting storage layouts and representing matrix entries with reduced precision in floating point or fixed point format. We investigate the impact of several options on storage demand and contraction rate, both analytically in the context of subspace correction methods and numerically at an example of solid mechanics. Both perspectives agree on the favourite scheme: fixed point representation of Cholesky factors in nested dissection storage.}, language = {en} } @misc{SahuDillMukhopadyayetal.2017, author = {Sahu, Manish and Dill, Sabrina and Mukhopadyay, Anirban and Zachow, Stefan}, title = {Surgical Tool Presence Detection for Cataract Procedures}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69110}, year = {2017}, abstract = {This article outlines the submission to the CATARACTS challenge for automatic tool presence detection [1]. Our approach for this multi-label classification problem comprises labelset-based sampling, a CNN architecture and temporal smothing as described in [3], which we call ZIB-Res-TS.}, language = {en} } @misc{BertholdStuckeyWitzig2018, author = {Berthold, Timo and Stuckey, Peter and Witzig, Jakob}, title = {Local Rapid Learning for Integer Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71190}, year = {2018}, abstract = {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.}, language = {en} } @misc{WitzigBertholdHeinz2018, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71170}, year = {2018}, abstract = {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.}, language = {en} } @misc{Hendel2018, author = {Hendel, Gregor}, title = {Adaptive Large Neighborhood Search for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71167}, year = {2018}, abstract = {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.}, language = {en} } @misc{BeckenbachHatzelWiederrecht2018, author = {Beckenbach, Isabel and Hatzel, Meike and Wiederrecht, Sebastian}, title = {The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71149}, year = {2018}, abstract = {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{\´a}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{\´a}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.}, language = {en} } @misc{ShinanoRehfeldtKoch2018, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71118}, year = {2018}, abstract = {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.}, language = {en} } @misc{Serrano2018, author = {Serrano, Felipe}, title = {Intersection cuts for factorable MINLP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71105}, year = {2018}, abstract = {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.}, language = {en} } @misc{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Reduction-based exact solution of prize-collecting Steiner tree problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70958}, year = {2018}, language = {en} } @misc{NaegelDeuflhardWittum2018, author = {N{\"a}gel, Arne and Deuflhard, Peter and Wittum, Gabriel}, title = {Efficient Stiff Integration of Density Driven Flow Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70891}, year = {2018}, abstract = {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.}, language = {en} } @misc{BorndoerferEgererKarbsteinetal.2018, author = {Bornd{\"o}rfer, Ralf and Egerer, Ascan and Karbstein, Marika and Messerschmidt, Ralf and Perez, Marc and Pfisterer, Steven and Strauß, Petra}, title = {Kombil{\"o}sung: Optimierung des Liniennetzes in Karlsruhe}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69677}, year = {2018}, abstract = {Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombil{\"o}sung.}, language = {de} } @misc{KnoetelBeckerScholtzetal.2018, author = {Kn{\"o}tel, David and Becker, Carola and Scholtz, Gerhard and Baum, Daniel}, title = {Global and Local Mesh Morphing for Complex Biological Objects from microCT Data}, issn = {1438-0064}, doi = {10.2312/vcbm.20181243}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70618}, year = {2018}, abstract = {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.}, language = {en} } @misc{ItoShinano2018, author = {Ito, Satoshi and Shinano, Yuji}, title = {Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70591}, year = {2018}, abstract = {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.}, language = {en} } @misc{BorndoerferEulerKarbsteinetal.2018, author = {Bornd{\"o}rfer, Ralf and Euler, Ricardo and Karbstein, Marika and Mett, Fabian}, title = {Ein mathematisches Modell zur Beschreibung von Preissystemen im {\"o}V}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70564}, year = {2018}, abstract = {Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des {\"o}V mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen m{\"o}glich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon w{\"a}hrend einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zun{\"a}chst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverb{\"u}nde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erl{\"a}utert. Anschließend folgen {\"U}berlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbund{\"u}bergriffs.}, language = {de} } @article{Sunkara2018, author = {Sunkara, Vikram}, title = {Algebraic Expressions of Conditional Expectations in Gene Regulatory Networks}, journal = {Journal of Mathematical Biology}, number = {79}, publisher = {Journal of Mathematical Biology}, issn = {1438-0064}, doi = {10.1007/s00285-019-01410-y}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70526}, pages = {1779 -- 1829}, year = {2018}, abstract = {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.}, language = {en} } @misc{StreubelTischendorfGriewank2018, author = {Streubel, Tom and Tischendorf, Caren and Griewank, Andreas}, title = {Piecewise Polynomial Taylor Expansions - The Generalization of Fa{\`a} di Bruno's Formula}, issn = {1438-0064}, doi = {10.1007/978-3-030-55240-4_3}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68859}, year = {2018}, abstract = {We present an extension of Taylor's theorem towards nonsmooth evalua- tion procedures incorporating absolute value operaions. Evaluations procedures are computer programs of mathematical functions in closed form expression and al- low a different treatment of smooth operations and calls to the absolute value value function. The well known classical Theorem of Taylor defines polynomial approx- imation of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential or differential algebraic equations, for the construction of solvers for the continuous nonlinear op- timization of finite dimensional objective functions and for root solving of nonlinear systems of equations. The herein provided proof is construtive and allow efficiently designed algorithms for the execution and computation of generalized piecewise polynomial expansions. As a demonstration we will derive a k-step method on the basis of polynomial interpolation and the proposed generalized expansions.}, language = {en} } @misc{RadonsLehmannStreubeletal.2018, author = {Radons, Manuel and Lehmann, Lutz and Streubel, Tom and Griewank, Andreas}, title = {An Open Newton Method for Piecewise Smooth Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70418}, year = {2018}, abstract = {Recent research has shown that piecewise smooth (PS) functions can be approximated by piecewise linear functions with second order error in the distance to a given reference point. A semismooth Newton type algorithm based on successive application of these piecewise linearizations was subsequently developed for the solution of PS equation systems. For local bijectivity of the linearization at a root, a radius of quadratic convergence was explicitly calculated in terms of local Lipschitz constants of the underlying PS function. In the present work we relax the criterium of local bijectivity of the linearization to local openness. For this purpose a weak implicit function theorem is proved via local mapping degree theory. It is shown that there exist PS functions f:IR^2 --> IR^2 satisfying the weaker criterium where every neighborhood of the root of f contains a point x such that all elements of the Clarke Jacobian at x are singular. In such neighborhoods the steps of classical semismooth Newton are not defined, which establishes the new method as an independent algorithm. To further clarify the relation between a PS function and its piecewise linearization, several statements about structure correspondences between the two are proved. Moreover, the influence of the specific representation of the local piecewise linear models on the robustness of our method is studied. An example application from cardiovascular mathematics is given.}, language = {en} } @misc{AgudoJacomeHegePaetschetal.2018, 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}, year = {2018}, 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{EiflerGleixnerPulaj2018, author = {Eifler, Leon and Gleixner, Ambros and Pulaj, Jonad}, title = {Chv{\´a}tal's Conjecture Holds for Ground Sets of Seven Elements}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70240}, year = {2018}, abstract = {We establish a general computational framework for Chv{\´a}tal's conjecture based on exact rational integer programming. As a result we prove Chv{\´a}tal's conjecture holds for all downsets whose union of sets contains seven elements or less. The computational proof relies on an exact branch-and-bound certificate that allows for elementary verification and is independent of the integer programming solver used.}, language = {en} } @misc{FackeldeySikorskiWeber2018, author = {Fackeldey, Konstantin and Sikorski, Alexander and Weber, Marcus}, title = {Spectral Clustering for Non-reversible Markov Chains}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70218}, year = {2018}, abstract = {Spectral clustering methods are based on solving eigenvalue problems for the identification of clusters, e.g. the identification of metastable subsets of a Markov chain. Usually, real-valued eigenvectors are mandatory for this type of algorithms. The Perron Cluster Analysis (PCCA+) is a well-known spectral clustering method of Markov chains. It is applicable for reversible Markov chains, because reversibility implies a real-valued spectrum. We also extend this spectral clustering method to non-reversible Markov chains and give some illustrative examples. The main idea is to replace the eigenvalue problem by a real-valued Schur decomposition. By this extension non-reversible Markov chains can be analyzed. Furthermore, the chains do not need to have a positive stationary distribution. In addition to metastabilities, dominant cycles and sinks can also be identified. This novel method is called GenPCCA (i.e. Generalized PCCA), since it includes the case of non reversible processes. We also apply the method to real world eye tracking data.}, language = {en} } @misc{RedemannLantzschLindowetal.2018, author = {Redemann, Stefanie and Lantzsch, Ina and Lindow, Norbert and Prohaska, Steffen and Srayko, Martin and M{\"u}ller-Reichert, Thomas}, title = {A switch in microtubule orientation during C. elegans meiosis}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69855}, year = {2018}, abstract = {In oocytes of many organisms, meiotic spindles form in the absence of centrosomes [1-5]. Such female meiotic spindles have a pointed appearance in metaphase with microtubules focused at acentrosomal spindle poles. At anaphase, the microtubules of acentrosomal spindles then transition to an inter- chromosomal array, while the spindle poles disappear. This transition is currently not understood. Previous studies have focused on this inter- chromosomal microtubule array and proposed a pushing model to drive chromosome segregation [6, 7]. This model includes an end-on orientation of microtubules with chromosomes. Alternatively, chromosomes were thought to associate along bundles of microtubules [8, 9]. Starting with metaphase, this second model proposed a pure lateral chromosome-to-microtubule association up to the final meiotic stages of anaphase. Here we applied large-scale electron tomography [10] of staged C. elegans oocytes in meiosis to analyze the orientation of microtubules in respect to chromosomes. We show that microtubules at metaphase I are primarily oriented laterally to the chromosomes and that microtubules switch to an end-on orientation during progression through anaphase. We further show that this switch in microtubule orientation involves a kinesin-13 microtubule depolymerase, KLP-7, which removes laterally associated microtubules around chromosomes. From this we conclude that both lateral and end-on modes of microtubule-to-chromosome orientations are successively used in C. elegans oocytes to segregate meiotic chromosomes.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal.2018, 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}, year = {2018}, 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{LenzBecker2018, author = {Lenz, Ralf and Becker, Kai-Helge}, title = {Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches}, issn = {1438-0064}, doi = {10.1007/s00291-021-00648-7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69726}, year = {2018}, abstract = {In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping"). The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally. On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models. Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times.}, language = {en} } @misc{BorndoerferKarbsteinLiebchenetal.2018, 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}, year = {2018}, 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{NavaYazdaniHegevonTycowiczetal.2018, author = {Nava-Yazdani, Esfandiar and Hege, Hans-Christian and von Tycowicz, Christoph and Sullivan, T. J.}, title = {A Shape Trajectories Approach to Longitudinal Statistical Analysis}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69759}, year = {2018}, abstract = {For Kendall's shape space we determine analytically Jacobi fields and parallel transport, and compute geodesic regression. Using the derived expressions, we can fully leverage the geometry via Riemannian optimization and reduce the computational expense by several orders of magnitude. The methodology is demonstrated by performing a longitudinal statistical analysis of epidemiological shape data. As application example we have chosen 3D shapes of knee bones, reconstructed from image data of the Osteoarthritis Initiative. Comparing subject groups with incident and developing osteoarthritis versus normal controls, we find clear differences in the temporal development of femur shapes. This paves the way for early prediction of incident knee osteoarthritis, using geometry data only.}, language = {en} } @misc{LindowBaumLeborgneetal.2018, author = {Lindow, Norbert and Baum, Daniel and Leborgne, Morgan and Hege, Hans-Christian}, title = {Interactive Visualization of RNA and DNA Structures}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69704}, year = {2018}, abstract = {The analysis and visualization of nucleic acids (RNA and DNA) play an increasingly important role due to the growing number of known 3-dimensional structures of such molecules. The great complexity of these structures, in particular, those of RNA, demands interactive visualization to get deeper insights into the relationship between the 2D secondary structure motifs and their 3D tertiary structures. Over the last decades, a lot of research in molecular visualization has focused on the visual exploration of protein structures while nucleic acids have only been marginally addressed. In contrast to proteins, which are composed of amino acids, the ingredients of nucleic acids are nucleotides. They form structuring patterns that differ from those of proteins and, hence, also require different visualization and exploration techniques. In order to support interactive exploration of nucleic acids, the computation of secondary structure motifs as well as their visualization in 2D and 3D must be fast. Therefore, in this paper, we focus on the performance of both the computation and visualization of nucleic acid structure. For the first time, we present a ray casting-based visualization of RNA and DNA secondary and tertiary structures, which enables real-time visualization of even large molecular dynamics trajectories. Furthermore, we provide a detailed description of all important aspects to visualize nucleic acid secondary and tertiary structures. With this, we close an important gap in molecular visualization.}, language = {en} } @misc{BeckerHiller2018, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {ASTS Orientations on Undirected Graphs: Structural analysis and enumeration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69632}, year = {2018}, abstract = {All feasible flows in potential-driven networks induce an orientation on the undirected graph underlying the network. Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations.}, language = {en} } @misc{HillerBecker2018, author = {Hiller, Benjamin and Becker, Kai-Helge}, title = {Improving relaxations for potential-driven network flow problems via acyclic flow orientations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69622}, year = {2018}, abstract = {The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network. We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage.}, language = {en} } @misc{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69563}, year = {2018}, abstract = {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.}, language = {en} } @misc{AndersonHiller2018, author = {Anderson, Lovis and Hiller, Benjamin}, title = {A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69489}, year = {2018}, abstract = {Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially (at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set. Naively, this can be done via inclusion/exclusion and leveraging the existing code for the volume of polytopes. However, this is often inefficient. We propose a revised variant of an old algorithm by Bieri and Nef (1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane.}, language = {en} } @misc{Schweiger2018, author = {Schweiger, Jonas}, title = {Exploiting structure in non-convex quadratic optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69476}, year = {2018}, abstract = {The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model poses principal difficulties. This paper summarizes the dissertation of Jonas Schweiger for the occasion of the GOR dissertation award 2018. We focus on the work on non-convex quadratic programs and show how problem specific structure can be used to obtain tight relaxations and speed up Branch\&Bound methods. Both a classic general QP and the Pooling Problem as an important practical application serve as showcases.}, language = {en} } @misc{GleixnerBastubbeEifleretal.2018, author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, year = {2018}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @misc{Tesch2018, author = {Tesch, Alexander}, title = {Improving Energetic Propagations for Cumulative Scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69331}, year = {2018}, abstract = {We consider the Cumulative Scheduling Problem (CuSP) in which a set of \$n\$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades.}, language = {en} } @misc{Tesch2018, author = {Tesch, Alexander}, title = {A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem}, issn = {1438-0064waoa}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68485}, year = {2018}, abstract = {We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Kon{\´e} et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997).}, language = {en} } @misc{SchwartzBalestrieriBorndoerfer2018, author = {Schwartz, Stephan and Balestrieri, Leonardo and Bornd{\"o}rfer, Ralf}, title = {On Finding Subpaths With High Demand}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69280}, year = {2018}, abstract = {We study the problem of finding subpaths with high demand in a given network that is traversed by several users. The demand of a subpath is the number of users who completely cover this subpath during their trip. Especially with large instances, an efficient algorithm for computing all subpaths' demands is necessary. We introduce a path-graph to prevent multiple generations of the same subpath and give a recursive approach to compute the demands of all subpaths. Our runtime analysis shows, that the presented approach compares very well against the theoretical minimum runtime.}, language = {en} } @misc{SeblanyHombergVincensetal.2018, author = {Seblany, Feda and Homberg, Ulrike and Vincens, Eric and Winkler, Paul and Witt, Karl Josef}, title = {Merging criteria for defining pores and constrictions in numerical packing of spheres}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69158}, year = {2018}, abstract = {The void space of granular materials is generally divided into larger local volumes denoted as pores and throats connecting pores. The smallest section in a throat is usually denoted as constriction. A correct description of pores and constrictions may help to understand the processes related to the transport of fluid or fine particles through granular materials, or to build models of imbibition for unsaturated granular media. In the case of numerical granular materials involving packings of spheres, different methods can be used to compute the pore space properties. However, these methods generally induce an over-segmentation of the pore network and a merging step is usually applied to mitigate such undesirable artifacts even if a precise delineation of a pore is somewhat subjective. This study provides a comparison between different merging criteria for pores in packing of spheres and a discussion about their implication on both the pore size distribution and the constriction size distribution of the material. A correspondence between these merging techniques is eventually proposed as a guide for the user.}, language = {en} } @misc{SagnolBlancoSauvage2018, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {Approximation Hierarchies for the cone of flow matrices}, issn = {1438-0064}, doi = {10.1016/j.endm.2018.02.002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68424}, year = {2018}, abstract = {Let \$G\$ be a directed acyclic graph with \$n\$ arcs, a source \$s\$ and a sink \$t\$. We introduce the cone \$K\$ of flow matrices, which is a polyhedral cone generated by the matrices \$1_P 1_P^T \in R^{n\times n}\$, where \$1_P\in R^n\$ is the incidence vector of the \$(s,t)\$-path \$P\$. Several combinatorial problems reduce to a linear optimization problem over \$K\$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of \$K\$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.}, language = {en} } @misc{SagnolSchmidtgenanntWaldschmidtTesch2018, author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander}, title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68415}, year = {2018}, abstract = {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, bins 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+1/e \approx 1.368\$ under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, 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.}, language = {en} } @misc{HasenfelderLehmannRadonsetal.2018, author = {Hasenfelder, Richard and Lehmann, Lutz and Radons, Manuel and Streubel, Tom and Strohm, Christian and Griewank, Andreas}, title = {Computational aspects of the Generalized Trapezoidal Rule}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68615}, year = {2018}, abstract = {In this article we analyze a generalized trapezoidal rule for initial value problems with piecewise smooth right hand side F:IR^n -> IR^n. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a non-differentiability of F. In such a situation the investigated generalized trapezoidal rule achieves a higher convergence order than the classical method. While the asymptotic behavior of the generalized method was investigated in a previous work, in the present article we develop the algorithmic structure for efficient implementation strategies and estimate the actual computational cost of the latter. Moreover, energy preservation of the generalized trapezoidal rule is proved for Hamiltonian systems with piecewise linear right hand side.}, language = {en} } @misc{LindowBaumHege2018, author = {Lindow, Norbert and Baum, Daniel and Hege, Hans-Christian}, title = {Atomic Accessibility Radii for Molecular Dynamics Analysis}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68468}, year = {2018}, abstract = {In molecular structure analysis and visualization, the molecule's atoms are often modeled as hard spheres parametrized by their positions and radii. While the atom positions result from experiments or molecular simulations, for the radii typically values are taken from literature. Most often, van der Waals (vdW) radii are used, for which diverse values exist. As a consequence, different visualization and analysis tools use different atomic radii, and the analyses are less objective than often believed. Furthermore, for the geometric accessibility analysis of molecular structures, vdW radii are not well suited. The reason is that during the molecular dynamics simulation, depending on the force field and the kinetic energy in the system, non-bonded atoms can come so close to each other that their vdW spheres intersect. In this paper, we introduce a new kind of atomic radius, called atomic accessibility radius', that better characterizes the accessibility of an atom in a given molecular trajectory. The new radii reflect the movement possibilities of atoms in the simulated physical system. They are computed by solving a linear program that maximizes the radii of the atoms under the constraint that non-bonded spheres do not intersect in the considered molecular trajectory. Using this data-driven approach, the actual accessibility of atoms can be visualized more precisely.}, language = {en} } @misc{GeorgesGleixnerGojicetal.2018, author = {Georges, Alexander and Gleixner, Ambros and Gojic, Gorana and Gottwald, Robert Lion and Haley, David and Hendel, Gregor and Matejczyk, Bartlomiej}, title = {Feature-Based Algorithm Selection for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68362}, year = {2018}, abstract = {Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.}, language = {en} } @misc{HillerSaitenmacherWalther2018, 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}, year = {2018}, 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{WeberSagerGleixner2018, author = {Weber, Tobias and Sager, Sebastian and Gleixner, Ambros}, title = {Solving Quadratic Programs to High Precision using Scaled Iterative Refinement}, issn = {1438-0064}, doi = {10.1007/s12532-019-00154-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68152}, year = {2018}, abstract = {Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and M{\´e}sz{\´a}ros benchmark library.}, language = {en} } @misc{TackMukhopadhyayZachow2018, author = {Tack, Alexander and Mukhopadhyay, Anirban and Zachow, Stefan}, title = {Knee Menisci Segmentation using Convolutional Neural Networks: Data from the Osteoarthritis Initiative}, volume = {26}, number = {5}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68038}, pages = {680 -- 688}, year = {2018}, abstract = {Abstract: Objective: To present a novel method for automated segmentation of knee menisci from MRIs. To evaluate quantitative meniscal biomarkers for osteoarthritis (OA) estimated thereof. Method: A segmentation method employing convolutional neural networks in combination with statistical shape models was developed. Accuracy was evaluated on 88 manual segmentations. Meniscal volume, tibial coverage, and meniscal extrusion were computed and tested for differences between groups of OA, joint space narrowing (JSN), and WOMAC pain. Correlation between computed meniscal extrusion and MOAKS experts' readings was evaluated for 600 subjects. Suitability of biomarkers for predicting incident radiographic OA from baseline to 24 months was tested on a group of 552 patients (184 incident OA, 386 controls) by performing conditional logistic regression. Results: Segmentation accuracy measured as Dice Similarity Coefficient was 83.8\% for medial menisci (MM) and 88.9\% for lateral menisci (LM) at baseline, and 83.1\% and 88.3\% at 12-month follow-up. Medial tibial coverage was significantly lower for arthritic cases compared to non-arthritic ones. Medial meniscal extrusion was significantly higher for arthritic knees. A moderate correlation between automatically computed medial meniscal extrusion and experts' readings was found (ρ=0.44). Mean medial meniscal extrusion was significantly greater for incident OA cases compared to controls (1.16±0.93 mm vs. 0.83±0.92 mm; p<0.05). Conclusion: Especially for medial menisci an excellent segmentation accuracy was achieved. Our meniscal biomarkers were validated by comparison to experts' readings as well as analysis of differences w.r.t groups of OA, JSN, and WOMAC pain. It was confirmed that medial meniscal extrusion is a predictor for incident OA.}, language = {en} } @misc{TitschackBaumMatsuyamaetal.2018, author = {Titschack, J{\"u}rgen and Baum, Daniel and Matsuyama, Kei and Boos, Karin and F{\"a}rber, Claudia and Kahl, Wolf-Achim and Ehrig, Karsten and Meinel, Dietmar and Soriano, Carmen and Stock, Stuart R.}, title = {Ambient occlusion - a powerful algorithm to segment shell and skeletal intrapores in computed tomography data}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67982}, year = {2018}, abstract = {During the last decades, X-ray (micro-)computed tomography has gained increasing attention for the description of porous skeletal and shell structures of various organism groups. However, their quantitative analysis is often hampered by the difficulty to discriminate cavities and pores within the object from the surrounding region. Herein, we test the ambient occlusion (AO) algorithm and newly implemented optimisations for the segmentation of cavities (implemented in the software Amira). The segmentation accuracy is evaluated as a function of (i) changes in the ray length input variable, and (ii) the usage of AO (scalar) field and other AO-derived (scalar) fields. The results clearly indicate that the AO field itself outperforms all other AO-derived fields in terms of segmentation accuracy and robustness against variations in the ray length input variable. The newly implemented optimisations improved the AO field-based segmentation only slightly, while the segmentations based on the AO-derived fields improved considerably. Additionally, we evaluated the potential of the AO field and AO-derived fields for the separation and classification of cavities as well as skeletal structures by comparing them with commonly used distance-map-based segmentations. For this, we tested the zooid separation within a bryozoan colony, the stereom classification of an ophiuroid tooth, the separation of bioerosion traces within a marble block and the calice (central cavity)-pore separation within a dendrophyllid coral. The obtained results clearly indicate that the ideal input field depends on the three-dimensional morphology of the object of interest. The segmentations based on the AO-derived fields often provided cavity separations and skeleton classifications that were superior to or impossible to obtain with commonly used distance- map-based segmentations. The combined usage of various AO-derived fields by supervised or unsupervised segmentation algorithms might provide a promising target for future research to further improve the results for this kind of high-end data segmentation and classification. Furthermore, the application of the developed segmentation algorithm is not restricted to X-ray (micro-)computed tomographic data but may potentially be useful for the segmentation of 3D volume data from other sources.}, language = {en} } @misc{LuedtkeD'AmbrosioLinderothetal.2018, author = {Luedtke, James and D'Ambrosio, Claudia and Linderoth, Jeff and Schweiger, Jonas}, title = {Strong Convex Nonlinear Relaxations of the Pooling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67824}, year = {2018}, abstract = {We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by considering a single product, a single attibute, and a single pool. The convex hull of the resulting nonconvex set is not polyhedral. We derive valid linear and convex nonlinear inequalities for the convex hull, and demonstrate that different subsets of these inequalities define the convex hull of the nonconvex set in three cases determined by the parameters of the set. Computational results on literature instances and newly created larger test instances demonstrate that the inequalities can significantly strengthen the convex relaxation of the pq-formulation of the pooling problem, which is the relaxation known to have the strongest bound.}, language = {en} } @misc{LuedtkeD'AmbrosioLinderothetal.2018, author = {Luedtke, James and D'Ambrosio, Claudia and Linderoth, Jeff and Schweiger, Jonas}, title = {Strong Convex Nonlinear Relaxations of the Pooling Problem: Extreme Points}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67801}, year = {2018}, abstract = {We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. In this technical report, we characterize the extreme points of the convex hull of our non-convex set, and show that they are not finite, i.e., the convex hull is not polyhedral. This analysis was used to derive valid nonlinear convex inequalities and show that, for a specific case, they characterize the convex hull of our set. The new valid inequalities and computational results are presented in ZIB Report 18-12.}, language = {en} } @misc{GreweLeRouxPilzetal.2018, author = {Grewe, Carl Martin and Le Roux, Gabriel and Pilz, Sven-Kristofer and Zachow, Stefan}, title = {Spotting the Details: The Various Facets of Facial Expressions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67696}, year = {2018}, abstract = {3D Morphable Models (MM) are a popular tool for analysis and synthesis of facial expressions. They represent plausible variations in facial shape and appearance within a low-dimensional parameter space. Fitted to a face scan, the model's parameters compactly encode its expression patterns. This expression code can be used, for instance, as a feature in automatic facial expression recognition. For accurate classification, an MM that can adequately represent the various characteristic facets and variants of each expression is necessary. Currently available MMs are limited in the diversity of expression patterns. We present a novel high-quality Facial Expression Morphable Model built from a large-scale face database as a tool for expression analysis and synthesis. Establishment of accurate dense correspondence, up to finest skin features, enables a detailed statistical analysis of facial expressions. Various characteristic shape patterns are identified for each expression. The results of our analysis give rise to a new facial expression code. We demonstrate the advantages of such a code for the automatic recognition of expressions, and compare the accuracy of our classifier to state-of-the-art.}, language = {en} } @misc{HillerWalther2018, 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}, year = {2018}, 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{HillerWalther2018, 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}, year = {2018}, 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{HillerKochScheweetal.2018, 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-67438}, year = {2018}, abstract = {In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now transported by independent 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 the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements.}, language = {en} }