TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - SCIP-Jack—a solver for STP and variants with parallelization extensions: An update N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state. T3 - ZIB-Report - 18-05 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66416 SN - 1438-0064 ER - TY - GEN A1 - Lie, Han Cheng A1 - Sullivan, T. J. A1 - Teckentrup, Aretha T1 - Random forward models and log-likelihoods in Bayesian inverse problems T2 - SIAM/ASA Journal on Uncertainty Quantification N2 - We consider the use of randomised forward models and log-likelihoods within the Bayesian approach to inverse problems. Such random approximations to the exact forward model or log-likelihood arise naturally when a computationally expensive model is approximated using a cheaper stochastic surrogate, as in Gaussian process emulation (kriging), or in the field of probabilistic numerical methods. We show that the Hellinger distance between the exact and approximate Bayesian posteriors is bounded by moments of the difference between the true and approximate log-likelihoods. Example applications of these stability results are given for randomised misfit models in large data applications and the probabilistic solution of ordinary differential equations. T3 - ZIB-Report - 18-03 KW - Bayesian inverse problem KW - random likelihood KW - surrogate model KW - posterior consistency KW - probabilistic numerics KW - uncertainty quantification KW - randomised misfit Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66324 SN - 1438-0064 VL - 6 IS - 4 SP - 1600 EP - 1629 ER - TY - JOUR A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Radons, Manuel A1 - Hasenfelder, Richard T1 - Piecewise linear secant approximation via algorithmic piecewise differentiation JF - Optimization Methods and Software N2 - It is shown how piecewise differentiable functions F : IR^n -> IR^m that are defined by evaluation programmes can be approximated locally by a piecewise linear model based on a pair of sample points \check x and \hat x. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - \check x||*||x - \hat x||). As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equalling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. Y1 - 2017 U6 - https://doi.org/10.1080/10556788.2017.1387256 VL - 33 IS - 4-6 SP - 1108 EP - 1126 PB - Taylor & Francis ER - TY - JOUR A1 - Griewank, Andreas A1 - Hasenfelder, Richard A1 - Radons, Manuel A1 - Lehmann, Lutz A1 - Streubel, Tom T1 - Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation JF - Optimization Methods and Software N2 - In this article we analyse a generalized trapezoidal rule for initial value problems with piecewise smooth right-hand side F : IR^n -> IR^n based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of F. The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third-order interpolation polynomial for the numerical trajectory. In the smooth case, the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1378653 VL - 33 SP - 1089 EP - 1107 PB - Taylor & Francis ER - TY - JOUR A1 - Duarte, Belmiro P.M. A1 - Sagnol, Guillaume A1 - Wong, Weng Kee T1 - An algorithm based on Semidefinite Programming for finding minimax optimal designs JF - Computational Statistics & Data Analysis Y1 - 2018 U6 - https://doi.org/10.1016/j.csda.2017.09.008 VL - 119 SP - 99 EP - 117 ER - TY - JOUR A1 - Jäger, Klaus A1 - Köppel, Grit A1 - Hammerschmidt, Martin A1 - Burger, Sven A1 - Becker, Christiane T1 - On accurate simulations of thin-film solar cells with a thick glass superstrate JF - Opt. Express Y1 - 2018 U6 - https://doi.org/10.1364/OE.26.000A99 VL - 26 SP - A99 ER - TY - JOUR A1 - Schnauber, Peter A1 - Schall, Johannes A1 - Bounouar, Samir A1 - Höhne, Theresa A1 - Park, Suk-In A1 - Ryu, Geun-Hwan A1 - Heindel, Tobias A1 - Burger, Sven A1 - Song, Jin-Dong A1 - Rodt, Sven A1 - Reitzenstein, Stephan T1 - Deterministic integration of quantum dots into on-chip multi-mode interference beamsplitters using in-situ electron beam lithography JF - Nano Lett. Y1 - 2018 U6 - https://doi.org/10.1021/acs.nanolett.7b05218 VL - 18 SP - 2336 ER - TY - JOUR A1 - Quer, Jannes A1 - Donati, Luca A1 - Keller, Bettina A1 - Weber, Marcus T1 - An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates JF - SIAM Journal on Scientific Computing N2 - In this article we propose an adaptive importance sampling scheme for dynamical quantities of high dimensional complex systems which are metastable. The main idea of this article is to combine a method coming from Molecular Dynamics Simulation, Metadynamics, with a theorem from stochastic analysis, Girsanov's theorem. The proposed algorithm has two advantages compared to a standard estimator of dynamic quantities: firstly, it is possible to produce estimators with a lower variance and, secondly, we can speed up the sampling. One of the main problems for building importance sampling schemes for metastable systems is to find the metastable region in order to manipulate the potential accordingly. Our method circumvents this problem by using an assimilated version of the Metadynamics algorithm and thus creates a non-equilibrium dynamics which is used to sample the equilibrium quantities. Y1 - 2018 U6 - https://doi.org/10.1137/17m1124772 VL - 40 IS - 2 SP - A653 EP - A670 ER - TY - JOUR A1 - Akbari Shandiz, Mohsen A1 - Boulos, Paul A1 - Sævarsson, Stefan A1 - Ramm, Heiko A1 - Fu, Chun Kit A1 - Miller, Stephen A1 - Zachow, Stefan A1 - Anglin, Carolyn T1 - Changes in Knee Shape and Geometry Resulting from Total Knee Arthroplasty JF - Journal of Engineering in Medicine N2 - Changes in knee shape and geometry resulting from total knee arthroplasty can affect patients in numerous important ways: pain, function, stability, range of motion, and kinematics. Quantitative data concerning these changes have not been previously available, to our knowledge, yet are essential to understand individual experiences of total knee arthroplasty and thereby improve outcomes for all patients. The limiting factor has been the challenge of accurately measuring these changes. Our study objective was to develop a conceptual framework and analysis method to investigate changes in knee shape and geometry, and prospectively apply it to a sample total knee arthroplasty population. Using clinically available computed tomography and radiography imaging systems, the three-dimensional knee shape and geometry of nine patients (eight varus and one valgus) were compared before and after total knee arthroplasty. All patients had largely good outcomes after their total knee arthroplasty. Knee shape changed both visually and numerically. On average, the distal condyles were slightly higher medially and lower laterally (range: +4.5 mm to −4.4 mm), the posterior condyles extended farther out medially but not laterally (range: +1.8 to −6.4 mm), patellofemoral distance increased throughout flexion by 1.8–3.5 mm, and patellar thickness alone increased by 2.9 mm (range: 0.7–5.2 mm). External femoral rotation differed preop and postop. Joint line distance, taking cartilage into account, changed by +0.7 to −1.5 mm on average throughout flexion. Important differences in shape and geometry were seen between pre-total knee arthroplasty and post-total knee arthroplasty knees. While this is qualitatively known, this is the first study to report it quantitatively, an important precursor to identifying the reasons for the poor outcome of some patients. Using the developed protocol and visualization techniques to compare patients with good versus poor clinical outcomes could lead to changes in implant design, implant selection, component positioning, and surgical technique. Recommendations based on this sample population are provided. Intraoperative and postoperative feedback could ultimately improve patient satisfaction. Y1 - 2018 UR - http://journals.sagepub.com/eprint/ZVgNrNESA9EjIcaFWSjb/full U6 - https://doi.org/10.1177/0954411917743274 VL - 232 IS - 1 SP - 67 EP - 79 ER - TY - JOUR A1 - de Lasson, Jakob Rosenkrantz A1 - Frandsen, Lars Hagedorn A1 - Gutsche, Philipp A1 - Burger, Sven A1 - Kim, Oleksiy S. A1 - Breinbjerg, Olav A1 - Ivanskaya, Aliaksandra A1 - Wang, Fengwen A1 - Sigmund, Ole A1 - Häyrynen, Teppo A1 - Lavrinenko, Andrei A1 - Mork, Jesper A1 - Gregersen, Niels T1 - Benchmarking five numerical simulation techniques for computing resonance wavelengths and quality factors in photonic crystal membrane line defect cavities JF - Opt. Express Y1 - 2018 U6 - https://doi.org/10.1364/OE.26.011366 VL - 26 SP - 11366 ER - TY - JOUR A1 - Fischer, Lisa A1 - Götschel, Sebastian A1 - Weiser, Martin T1 - Lossy data compression reduces communication time in hybrid time-parallel integrators JF - Comput. Vis. Sci. N2 - Parallel in time methods for solving initial value problems are a means to increase the parallelism of numerical simulations. Hybrid parareal schemes interleaving the parallel in time iteration with an iterative solution of the individual time steps are among the most efficient methods for general nonlinear problems. Despite the hiding of communication time behind computation, communication has in certain situations a significant impact on the total runtime. Here we present strict, yet no sharp, error bounds for hybrid parareal methods with inexact communication due to lossy data compression, and derive theoretical estimates of the impact of compression on parallel efficiency of the algorithms. These and some computational experiments suggest that compression is a viable method to make hybrid parareal schemes robust with respect to low bandwidth setups. Y1 - 2018 U6 - https://doi.org/10.1007/s00791-018-0293-2 VL - 19 IS - 1 SP - 19 EP - 30 ER - TY - JOUR A1 - von Tycowicz, Christoph A1 - Ambellan, Felix A1 - Mukhopadhyay, Anirban A1 - Zachow, Stefan T1 - An Efficient Riemannian Statistical Shape Model using Differential Coordinates JF - Medical Image Analysis N2 - We propose a novel Riemannian framework for statistical analysis of shapes that is able to account for the nonlinearity in shape variation. By adopting a physical perspective, we introduce a differential representation that puts the local geometric variability into focus. We model these differential coordinates as elements of a Lie group thereby endowing our shape space with a non-Euclidean structure. A key advantage of our framework is that statistics in a manifold shape space becomes numerically tractable improving performance by several orders of magnitude over state-of-the-art. We show that our Riemannian model is well suited for the identification of intra-population variability as well as inter-population differences. In particular, we demonstrate the superiority of the proposed model in experiments on specificity and generalization ability. We further derive a statistical shape descriptor that outperforms the standard Euclidean approach in terms of shape-based classification of morphological disorders. Y1 - 2018 U6 - https://doi.org/10.1016/j.media.2017.09.004 VL - 43 IS - 1 SP - 1 EP - 9 ER - TY - CHAP A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6 SP - 151 EP - 157 PB - Springer International Publishing ER - TY - CHAP A1 - Müller, Benjamin A1 - Kuhlmann, Renke A1 - Vigerske, Stefan T1 - On the performance of NLP solvers within global MINLP solvers T2 - Operations Research Proceedings 2017 N2 - Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_84 SP - 633 EP - 639 PB - Springer International Publishing ER - TY - JOUR A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework JF - Optimization Methods & Software N2 - This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1335312 VL - 33 IS - 3 SP - 563 EP - 593 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP JF - Journal of Computational Mathematics N2 - Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds. Y1 - 2018 U6 - https://doi.org/10.4208/jcm.1709-m2017-0002 VL - 36 IS - 3 SP - 459 EP - 468 ER - TY - JOUR A1 - Klus, Stefan A1 - Nüske, Feliks A1 - Koltai, Peter A1 - Wu, Hao A1 - Kevrekidis, Ioannis A1 - Schütte, Christof A1 - Noé, Frank T1 - Data-driven model reduction and transfer operator approximation JF - Journal of Nonlinear Science Y1 - 2018 UR - https://link.springer.com/article/10.1007/s00332-017-9437-7 U6 - https://doi.org/10.1007/s00332-017-9437-7 VL - 28 IS - 3 SP - 985 EP - 1010 ER - TY - JOUR A1 - von Kleist, Max A1 - Schütte, Christof A1 - Zhang, Wei T1 - Statistical analysis of the first passage path ensemble of jump processes JF - Journal of Statistical Physics N2 - The transition mechanism of jump processes between two different subsets in state space reveals important dynamical information of the processes and therefore has attracted considerable attention in the past years. In this paper, we study the first passage path ensemble of both discrete-time and continuous-time jump processes on a finite state space. The main approach is to divide each first passage path into nonreactive and reactive segments and to study them separately. The analysis can be applied to jump processes which are non-ergodic, as well as continuous-time jump processes where the waiting time distributions are non-exponential. In the particular case that the jump processes are both Markovian and ergodic, our analysis elucidates the relations between the study of the first passage paths and the study of the transition paths in transition path theory. We provide algorithms to numerically compute statistics of the first passage path ensemble. The computational complexity of these algorithms scales with the complexity of solving a linear system, for which efficient methods are available. Several examples demonstrate the wide applicability of the derived results across research areas. Y1 - 2018 U6 - https://doi.org/10.1007/s10955-017-1949-x VL - 170 SP - 809 EP - 843 ER - TY - JOUR A1 - Klus, Stefan A1 - Gelß, Patrick A1 - Peitz, Sebastian A1 - Schütte, Christof T1 - Tensor-based dynamic mode decomposition JF - Nonlinearity Y1 - 2018 U6 - https://doi.org/10.1088/1361-6544/aabc8f VL - 31 IS - 7 PB - IOP Publishing Ltd & London Mathematical Society ER - TY - JOUR A1 - Lie, Han Cheng A1 - Sullivan, T. J. T1 - Quasi-invariance of countable products of Cauchy measures under non-unitary dilations JF - Electronic Communications in Probability Y1 - 2018 U6 - https://doi.org/10.1214/18-ECP113 VL - 23 IS - 8 SP - 1 EP - 6 ER - TY - JOUR A1 - Weiser, Martin A1 - Ghosh, Sunayana T1 - Theoretically optimal inexact SDC methods JF - Communications in Applied Mathematics and Computational Science N2 - In several inital value problems with particularly expensive right hand side evaluation or implicit step computation, there is a trade-off between accuracy and computational effort. We consider inexact spectral deferred correction (SDC) methods for solving such initial value problems. SDC methods are interpreted as fixed point iterations and, due to their corrective iterative nature, allow to exploit the accuracy-work-tradeoff for a reduction of the total computational effort. On one hand we derive error models bounding the total error in terms of the evaluation errors. On the other hand, we define work models describing the computational effort in terms of the evaluation accuracy. Combining both, a theoretically optimal local tolerance selection is worked out by minimizing the total work subject to achieving the requested tolerance. The properties of optimal local tolerances and the predicted efficiency gain compared to simpler heuristics, and a reasonable practical performance, are illustrated on simple numerical examples. Y1 - 2018 U6 - https://doi.org/10.2140/camcos.2018.13.53 IS - 13-1 SP - 53 EP - 86 ER - TY - JOUR A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes JF - Multiscale Modeling and Simulation N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. KW - Markov State Models KW - NESS KW - Non-reversible Markov Processes KW - Mixed-Integer Programming Y1 - 2018 U6 - https://doi.org/10.1137/16M1091162 SN - 1438-0064 VL - 16 IS - 1 SP - 248 EP - 265 ER -