@misc{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {SCIP-Jack—a solver for STP and variants with parallelization extensions: An update}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66416}, year = {2018}, abstract = {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.}, language = {en} } @misc{LieSullivanTeckentrup2018, author = {Lie, Han Cheng and Sullivan, T. J. and Teckentrup, Aretha}, title = {Random forward models and log-likelihoods in Bayesian inverse problems}, volume = {6}, journal = {SIAM/ASA Journal on Uncertainty Quantification}, number = {4}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/1712.05717}, doi = {10.1137/18M1166523}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66324}, pages = {1600 -- 1629}, year = {2018}, abstract = {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.}, language = {en} } @article{GriewankStreubelLehmannetal.2018, author = {Griewank, Andreas and Streubel, Tom and Lehmann, Lutz and Radons, Manuel and Hasenfelder, Richard}, title = {Piecewise linear secant approximation via algorithmic piecewise differentiation}, volume = {33}, journal = {Optimization Methods and Software}, number = {4-6}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1387256}, pages = {1108 -- 1126}, year = {2018}, abstract = {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.}, language = {en} } @article{GriewankHasenfelderRadonsetal.2018, author = {Griewank, Andreas and Hasenfelder, Richard and Radons, Manuel and Lehmann, Lutz and Streubel, Tom}, title = {Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation}, volume = {33}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1378653}, pages = {1089 -- 1107}, year = {2018}, abstract = {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.}, language = {en} } @article{DuarteSagnolWong2018, author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Wong, Weng Kee}, title = {An algorithm based on Semidefinite Programming for finding minimax optimal designs}, volume = {119}, journal = {Computational Statistics \& Data Analysis}, doi = {10.1016/j.csda.2017.09.008}, pages = {99 -- 117}, year = {2018}, language = {en} } @article{JaegerKoeppelHammerschmidtetal.2018, author = {J{\"a}ger, Klaus and K{\"o}ppel, Grit and Hammerschmidt, Martin and Burger, Sven and Becker, Christiane}, title = {On accurate simulations of thin-film solar cells with a thick glass superstrate}, volume = {26}, journal = {Opt. Express}, doi = {10.1364/OE.26.000A99}, pages = {A99}, year = {2018}, language = {en} } @article{SchnauberSchallBounouaretal.2018, author = {Schnauber, Peter and Schall, Johannes and Bounouar, Samir and H{\"o}hne, Theresa and Park, Suk-In and Ryu, Geun-Hwan and Heindel, Tobias and Burger, Sven and Song, Jin-Dong and Rodt, Sven and Reitzenstein, Stephan}, title = {Deterministic integration of quantum dots into on-chip multi-mode interference beamsplitters using in-situ electron beam lithography}, volume = {18}, journal = {Nano Lett.}, arxiv = {http://arxiv.org/abs/1712.03837}, doi = {10.1021/acs.nanolett.7b05218}, pages = {2336}, year = {2018}, language = {en} } @article{QuerDonatiKelleretal.2018, author = {Quer, Jannes and Donati, Luca and Keller, Bettina and Weber, Marcus}, title = {An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates}, volume = {40}, journal = {SIAM Journal on Scientific Computing}, number = {2}, doi = {10.1137/17m1124772}, pages = {A653 -- A670}, year = {2018}, abstract = {In this article we propose an adaptive importance sampling scheme for dynamical quantities of high dimensional complex systems which are metastable. The main idea of this article is to combine a method coming from Molecular Dynamics Simulation, Metadynamics, with a theorem from stochastic analysis, Girsanov's theorem. The proposed algorithm has two advantages compared to a standard estimator of dynamic quantities: firstly, it is possible to produce estimators with a lower variance and, secondly, we can speed up the sampling. One of the main problems for building importance sampling schemes for metastable systems is to find the metastable region in order to manipulate the potential accordingly. Our method circumvents this problem by using an assimilated version of the Metadynamics algorithm and thus creates a non-equilibrium dynamics which is used to sample the equilibrium quantities.}, language = {en} } @article{AkbariShandizBoulosSavarssonetal.2018, author = {Akbari Shandiz, Mohsen and Boulos, Paul and S{\ae}varsson, Stefan and Ramm, Heiko and Fu, Chun Kit and Miller, Stephen and Zachow, Stefan and Anglin, Carolyn}, title = {Changes in Knee Shape and Geometry Resulting from Total Knee Arthroplasty}, volume = {232}, journal = {Journal of Engineering in Medicine}, number = {1}, doi = {10.1177/0954411917743274}, pages = {67 -- 79}, year = {2018}, abstract = {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.}, language = {en} } @article{deLassonFrandsenGutscheetal.2018, author = {de Lasson, Jakob Rosenkrantz and Frandsen, Lars Hagedorn and Gutsche, Philipp and Burger, Sven and Kim, Oleksiy S. and Breinbjerg, Olav and Ivanskaya, Aliaksandra and Wang, Fengwen and Sigmund, Ole and H{\"a}yrynen, Teppo and Lavrinenko, Andrei and Mork, Jesper and Gregersen, Niels}, title = {Benchmarking five numerical simulation techniques for computing resonance wavelengths and quality factors in photonic crystal membrane line defect cavities}, volume = {26}, journal = {Opt. Express}, arxiv = {http://arxiv.org/abs/1710.02215}, doi = {10.1364/OE.26.011366}, pages = {11366}, year = {2018}, language = {en} } @article{FischerGoetschelWeiser2018, author = {Fischer, Lisa and G{\"o}tschel, Sebastian and Weiser, Martin}, title = {Lossy data compression reduces communication time in hybrid time-parallel integrators}, volume = {19}, journal = {Comput. Vis. Sci.}, number = {1}, doi = {10.1007/s00791-018-0293-2}, pages = {19 -- 30}, year = {2018}, abstract = {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.}, language = {en} } @article{vonTycowiczAmbellanMukhopadhyayetal.2018, author = {von Tycowicz, Christoph and Ambellan, Felix and Mukhopadhyay, Anirban and Zachow, Stefan}, title = {An Efficient Riemannian Statistical Shape Model using Differential Coordinates}, volume = {43}, journal = {Medical Image Analysis}, number = {1}, doi = {10.1016/j.media.2017.09.004}, pages = {1 -- 9}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{MiltenbergerRalphsSteffy2018, author = {Miltenberger, Matthias and Ralphs, Ted and Steffy, Daniel}, title = {Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6}, pages = {151 -- 157}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{MuellerKuhlmannVigerske2018, author = {M{\"u}ller, Benjamin and Kuhlmann, Renke and Vigerske, Stefan}, title = {On the performance of NLP solvers within global MINLP solvers}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_84}, pages = {633 -- 639}, year = {2018}, abstract = {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.}, language = {en} } @article{VigerskeGleixner2018, author = {Vigerske, Stefan and Gleixner, Ambros}, title = {SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework}, volume = {33}, journal = {Optimization Methods \& Software}, number = {3}, doi = {10.1080/10556788.2017.1335312}, pages = {563 -- 593}, year = {2018}, abstract = {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.}, language = {en} } @article{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP}, volume = {36}, journal = {Journal of Computational Mathematics}, number = {3}, doi = {10.4208/jcm.1709-m2017-0002}, pages = {459 -- 468}, year = {2018}, abstract = {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.}, language = {en} } @article{KlusNueskeKoltaietal.2018, author = {Klus, Stefan and N{\"u}ske, Feliks and Koltai, Peter and Wu, Hao and Kevrekidis, Ioannis and Sch{\"u}tte, Christof and No{\´e}, Frank}, title = {Data-driven model reduction and transfer operator approximation}, volume = {28}, journal = {Journal of Nonlinear Science}, number = {3}, doi = {10.1007/s00332-017-9437-7}, pages = {985 -- 1010}, year = {2018}, language = {en} } @article{vonKleistSchuetteZhang2018, author = {von Kleist, Max and Sch{\"u}tte, Christof and Zhang, Wei}, title = {Statistical analysis of the first passage path ensemble of jump processes}, volume = {170}, journal = {Journal of Statistical Physics}, doi = {10.1007/s10955-017-1949-x}, pages = {809 -- 843}, year = {2018}, abstract = {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.}, language = {en} } @article{KlusGelssPeitzetal.2018, author = {Klus, Stefan and Gelß, Patrick and Peitz, Sebastian and Sch{\"u}tte, Christof}, title = {Tensor-based dynamic mode decomposition}, volume = {31}, journal = {Nonlinearity}, number = {7}, publisher = {IOP Publishing Ltd \& London Mathematical Society}, doi = {10.1088/1361-6544/aabc8f}, year = {2018}, language = {en} } @article{LieSullivan2018, author = {Lie, Han Cheng and Sullivan, T. J.}, title = {Quasi-invariance of countable products of Cauchy measures under non-unitary dilations}, volume = {23}, journal = {Electronic Communications in Probability}, number = {8}, arxiv = {http://arxiv.org/abs/1611.10289}, doi = {10.1214/18-ECP113}, pages = {1 -- 6}, year = {2018}, language = {en} } @article{WeiserGhosh2018, author = {Weiser, Martin and Ghosh, Sunayana}, title = {Theoretically optimal inexact SDC methods}, journal = {Communications in Applied Mathematics and Computational Science}, number = {13-1}, doi = {10.2140/camcos.2018.13.53}, pages = {53 -- 86}, year = {2018}, abstract = {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.}, language = {en} } @article{WitzigBeckenbachEifleretal.2018, author = {Witzig, Jakob and Beckenbach, Isabel and Eifler, Leon and Fackeldey, Konstantin and Gleixner, Ambros and Grever, Andreas and Weber, Marcus}, title = {Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes}, volume = {16}, journal = {Multiscale Modeling and Simulation}, number = {1}, issn = {1438-0064}, doi = {10.1137/16M1091162}, pages = {248 -- 265}, year = {2018}, abstract = {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.}, language = {en} }