TY - GEN A1 - Tesch, Alexander T1 - Improved Compact Models for the Resource-Constrained Project Scheduling Problem N2 - In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments. T3 - ZIB-Report - 16-76 KW - Scheduling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62891 SN - 1438-0064 ER - TY - GEN A1 - Ralphs, Ted A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Koch, Thorsten T1 - Parallel Solvers for Mixed Integer Linear Programming N2 - In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures. T3 - ZIB-Report - 16-74 KW - parallel computing KW - integer programming KW - branch-and-bound KW - supercomputing Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62239 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Hasenfelder, Richard A1 - Radons, Manuel T1 - Piecewise linear secant approximation via Algorithmic Piecewise Differentiation N2 - It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x − x̌|| ||x − x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. 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 equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. T3 - ZIB-Report - 16-54 KW - Automatic differentiation KW - Computational graph KW - Lipschitz continuity KW - Generalized Hermite interpolation KW - ADOL-C Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61642 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - The Three Phases of MIP Solving N2 - Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points. T3 - ZIB-Report - 16-78 KW - optimization software KW - mixed-integer programming KW - branch-and-bound KW - adaptive search behavior KW - optimality prediction Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61607 SN - 1438-0064 ER - TY - GEN A1 - Lenz, Ralf A1 - Schwarz, Robert T1 - Optimal Looping of Pipelines in Gas Networks N2 - In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations. T3 - ZIB-Report - 16-67 KW - Mixed Integer Nonlinear Programming KW - Gas Network Applications KW - Expansion Planning Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61564 SN - 1438-0064 ER - TY - GEN A1 - Hennig, Kai A1 - Schwarz, Robert T1 - Using Bilevel Optimization to find Severe Transport Situations in Gas Transmission Networks N2 - In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib. T3 - ZIB-Report - 16-68 KW - bilevel optimization KW - gas networks KW - network flow Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61519 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Optimization of Handouts for Rolling Stock Rotations Visualization N2 - A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach. T3 - ZIB-Report - ZR-16-73 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61430 SN - 1438-0064 ER - TY - GEN A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed domain propagation N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. T3 - ZIB-Report - 16-71 KW - mixed integer programming KW - parallelization KW - domain propagation KW - portfolio solvers Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61380 SN - 1438-0064 ER - TY - GEN A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite N2 - SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. T3 - ZIB-Report - 16-64 KW - SCIP, Mathematical optimization, Python, Modeling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61348 SN - 1438-0064 ER - TY - GEN A1 - Klebanov, Ilja A1 - Sikorski, Alexander A1 - Schütte, Christof A1 - Röblitz, Susanna T1 - Empirical Bayes Methods for Prior Estimation in Systems Medicine N2 - One of the main goals of mathematical modelling in systems medicine related to medical applications is to obtain patient-specific parameterizations and model predictions. In clinical practice, however, the number of available measurements for single patients is usually limited due to time and cost restrictions. This hampers the process of making patient-specific predictions about the outcome of a treatment. On the other hand, data are often available for many patients, in particular if extensive clinical studies have been performed. Therefore, before applying Bayes’ rule separately to the data of each patient (which is typically performed using a non-informative prior), it is meaningful to use empirical Bayes methods in order to construct an informative prior from all available data. We compare the performance of four priors - a non-informative prior and priors chosen by nonparametric maximum likelihood estimation (NPMLE), by maximum penalized lilelihood estimation (MPLE) and by doubly-smoothed maximum likelihood estimation (DS-MLE) - by applying them to a low-dimensional parameter estimation problem in a toy model as well as to a high-dimensional ODE model of the human menstrual cycle, which represents a typical example from systems biology modelling. T3 - ZIB-Report - 16-57 KW - Parameter estimation KW - Bayesian inference KW - Bayesian hierarchical modelling KW - NPMLE KW - MPLE KW - DS-MLE KW - EM algorithm KW - Jeffreys prior KW - reference prior KW - hyperparameter KW - hyperprior KW - principle of maximum entropy Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61307 SN - 1438-0064 ER - TY - GEN A1 - Schenker, Sebastian A1 - Borndörfer, Ralf A1 - Skutella, Martin T1 - A novel partitioning of the set of non-dominated points N2 - We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with $k$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are located. T3 - ZIB-Report - 16-55 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61286 SN - 1438-0064 ER - TY - GEN A1 - Klebanov, Ilja A1 - Sikorski, Alexander A1 - Schütte, Christof A1 - Röblitz, Susanna T1 - Empirical Bayes Methods, Reference Priors, Cross Entropy and the EM Algorithm N2 - When estimating a probability density within the empirical Bayes framework, the non-parametric maximum likelihood estimate (NPMLE) usually tends to overfit the data. This issue is usually taken care of by regularization - a penalization term is subtracted from the marginal log-likelihood before the maximization step, so that the estimate favors smooth solutions, resulting in the so-called maximum penalized likelihood estimation (MPLE). The majority of penalizations currently in use are rather arbitrary brute-force solutions, which lack invariance under transformation of the parameters(reparametrization) and measurements. This contradicts the principle that, if the underlying model has several equivalent formulations, the methods of inductive inference should lead to consistent results. Motivated by this principle and using an information-theoretic point of view, we suggest an entropy-based penalization term that guarantees this kind of invariance. The resulting density estimate can be seen as a generalization of reference priors. Using the reference prior as a hyperprior, on the other hand, is argued to be a poor choice for regularization. We also present an insightful connection between the NPMLE, the cross entropy and the principle of minimum discrimination information suggesting another method of inference that contains the doubly-smoothed maximum likelihood estimation as a special case. T3 - ZIB-Report - 16-56 KW - parameter estimation KW - Bayesian inference KW - Bayesian hierarchical modeling KW - hyperparameter KW - hyperprior KW - EM algorithm KW - NPMLE KW - MPLE KW - DS-MLE KW - principle of maximum entropy KW - cross entropy KW - minimum discrimination information KW - reference prior KW - Jeffreys prior Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61230 SN - 1438-0064 ER - TY - GEN A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Schlechte, Thomas A1 - Schlobach, Swen T1 - The Shortest Path Problem with Crossing Costs N2 - We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice. T3 - ZIB-Report - 16-70 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61240 SN - 1438-0064 ER - TY - GEN A1 - Tycowicz, Christoph von A1 - Ambellan, Felix A1 - Mukhopadhyay, Anirban A1 - Zachow, Stefan T1 - A Riemannian Statistical Shape Model using Differential Coordinates 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-Euclidian structure. A key advantage of our framework is that statistics in a manifold shape space become 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 Euclidian approach in terms of shape-based classification of morphological disorders. T3 - ZIB-Report - 16-69 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61175 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6485 SN - 1438-0064 ER - TY - GEN A1 - Schwartz, Stephan A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Designing Inspector Rosters with Optimal Strategies N2 - We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances. T3 - ZIB-Report - 16-65 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61123 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming N2 - SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. T3 - ZIB-Report - 16-45 KW - supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61107 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations N2 - 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. T3 - ZIB-Report - 16-61 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61092 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Experiments with Conflict Analysis in Mixed Integer Programming N2 - The analysis of infeasible subproblems plays an import 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 the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept 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. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving. T3 - ZIB-Report - 16-63 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61087 SN - 1438-0064 ER - TY - GEN A1 - Cheung, Kevin K. H. A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Verifying Integer Programming Results N2 - Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates. T3 - ZIB-Report - 16-58 KW - correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61044 SN - 1438-0064 ER - TY - GEN A1 - Winkelmann, Stefanie A1 - Schütte, Christof T1 - The spatiotemporal master equation: approximation of reaction-diffusion dynamics via Markov state modeling N2 - Accurate modeling and numerical simulation of reaction kinetics is a topic of steady interest. We consider the spatiotemporal chemical master equation (ST-CME) as a model for stochastic reaction-diffusion systems that exhibit properties of metastability. The space of motion is decomposed into metastable compartments and diffusive motion is approximated by jumps between these compartments. Treating these jumps as first-order reactions, simulation of the resulting stochastic system is possible by the Gillespie method. We present the theory of Markov state models (MSM) as a theoretical foundation of this intuitive approach. By means of Markov state modeling, both the number and shape of compartments and the transition rates between them can be determined. We consider the ST-CME for two reaction-diffusion systems and compare it to more detailed models. Moreover, a rigorous formal justification of the ST-CME by Galerkin projection methods is presented. T3 - ZIB-Report - 16-60 KW - reaction-diffusion KW - stochastic chemical kinetics KW - chemical master equation Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60999 SN - 1438-0064 ER - TY - GEN A1 - Winkelmann, Stefanie T1 - Markov Control with Rare State Observation: Average Optimality N2 - This paper investigates the criterion of long-term average costs for a Markov decision process (MDP) which is not permanently observable. Each observation of the process produces a fixed amount of \textit{information costs} which enter the considered performance criterion and preclude from arbitrarily frequent state testing. Choosing the \textit{rare} observation times is part of the control procedure. In contrast to the theory of partially observable Markov decision processes, we consider an arbitrary continuous-time Markov process on a finite state space without further restrictions on the dynamics or the type of interaction. Based on the original Markov control theory, we redefine the control model and the average cost criterion for the setting of information costs. We analyze the constant of average costs for the case of ergodic dynamics and present an optimality equation which characterizes the optimal choice of control actions and observation times. For this purpose, we construct an equivalent freely observable MDP and translate the well-known results from the original theory to the new setting. T3 - ZIB-Report - 16-59 KW - Markov decision process KW - partial observability KW - average optimality KW - information costs Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60981 SN - 1438-0064 ER - TY - GEN A1 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Bartz, Gerald T1 - The Graph Segmentation Problem N2 - We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest. T3 - ZIB-Report - 16-53 KW - toll billing KW - graph segmentation KW - combinatorial optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60750 SN - 1438-0064 ER - TY - GEN A1 - Noack, Matthias A1 - Wende, Florian A1 - Zitzlsberger, Georg A1 - Klemm, Michael A1 - Steinke, Thomas T1 - KART – A Runtime Compilation Library for Improving HPC Application Performance N2 - The effectiveness of ahead-of-time compiler optimization heavily depends on the amount of available information at compile time. Input-specific information that is only available at runtime cannot be used, although it often determines loop counts, branching predicates and paths, as well as memory-access patterns. It can also be crucial for generating efficient SIMD-vectorized code. This is especially relevant for the many-core architectures paving the way to exascale computing, which are more sensitive to code-optimization. We explore the design-space for using input-specific information at compile-time and present KART, a C++ library solution that allows developers to compile, link, and execute code (e.g., C, C++ , Fortran) at application runtime. Besides mere runtime compilation of performance-critical code, KART can be used to instantiate the same code multiple times using different inputs, compilers, and options. Other techniques like auto-tuning and code-generation can be integrated into a KART-enabled application instead of being scripted around it. We evaluate runtimes and compilation costs for different synthetic kernels, and show the effectiveness for two real-world applications, HEOM and a WSM6 proxy. T3 - ZIB-Report - 16-48 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60730 SN - 1438-0064 ER - TY - GEN A1 - Weiser, Martin A1 - Ghosh, Sunayana T1 - Theoretically optimal inexact SDC methods N2 - In several inital value problems with particularly expensive right hand side computation, there is a trade-off between accuracy and computational effort in evaluating the right hand sides. We consider inexact spectral deferred correction (SDC) methods for solving such non-stiff 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 an error model bounding the total error in terms of the right hand side 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 tolerance selection is worked out by minimizing the total work subject to achieving the requested tolerance. T3 - ZIB-Report - 16-52 KW - Spectral deferred correction, initial value problems, error propagation, adaptive control of tolerances Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53140 SN - 1438-0064 ER - TY - GEN A1 - Pulaj, Jonad T1 - Cutting Planes for Families Implying Frankl's Conjecture N2 - We find previously unknown families which imply Frankl’s conjecture using an algorithmic framework. The conjecture states that for any non-empty union-closed (or Frankl) family there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine whether a given Frankl family implies the conjecture for all Frankl families which contain it. A Frankl family is Non–Frankl-Complete (Non–FC), if it does not imply the conjecture in its elements for some Frankl family that contains it. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem. This method allows us to find a counterexample to a ten-year-old conjecture by R. Morris about the structure of generators for Non–FC-families. T3 - ZIB-Report - 16-51 KW - extremal combinatorics, extremal set theory, cutting plane, exact integer programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60626 SN - 1438-0064 ER - TY - GEN A1 - Sali, Adrian T1 - Coupling of Monodomain and Eikonal Models for Cardiac Electrophysiology N2 - The primary goal of this paper is to study the coupling of monodomain and eikonal models for the numerical simulation of cardiac electrophysiology. Eikonal models are nonlinear elliptic equations describing the excitation time of the cardiac tissue. They are often used as very fast approximations for monodomain or bidomain models - parabolic reaction-diffusion systems describing the excitation wavefront in terms of ionic currents. The excitation front is a thin region with high gradients, whereas excitation times vary over larger domains. Hence, eikonal equations can be solved on much coarser grids than monodomain equations. Moreover, as eikonal models are not time-dependent, no time integration is needed. Eikonal models are derived from monodomain models making additional assumptions and using certain approximations. While generally the approximation is rather good, several specific situations are not well captured by eikonal models. We consider coupling the two models, i.e. using the monodomain model in regions where more accurate results or the shape of the wavefront are needed, and the eikonal model in the remaining parts of the domain, where the excitation time is sufficient. Restricting the monodomain simulation to a small subdomain reduces the computational effort considerably. Numerical methods for the simulation of the individual models are presented, with the finite element method as the main ingredient. Coupling conditions as well as algorithms for implementing the coupling are explained. The approximation quality and efficiency of the coupled model is illustrated on simple geometries using an Aliev-Panfilov membrane model. T3 - ZIB-Report - 16-50 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60508 SN - 1438-0064 ER - TY - GEN A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching N2 - The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012. T3 - ZIB-Report - 16-49 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60493 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack. T3 - ZIB-Report - 16-47 KW - Steiner tree problems KW - reduction techniques KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60420 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Bixby, Robert E. A1 - Gu, Zonghao A1 - Rothberg, Edward A1 - Weninger, Dieter T1 - Presolve Reductions in Mixed Integer Programming N2 - Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed-integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the ``strength'' of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed-integer programs, and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed-integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature. T3 - ZIB-Report - 16-44 KW - integer programming KW - presolving KW - Gurobi Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60370 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - Exact Energetic Reasoning in O(n^2 log^2 n) N2 - In this paper, we address the Energetic Reasoning propagation rule for the Cumulative Scheduling Problem (CuSP). An energetic reasoning propagation algorithm is called exact, if it computes the maximum possible energetic reasoning propagation for all the jobs. The currently best known exact energetic reasoning algorithm has complexity O(n^3). In this paper, we present a new exact energetic reasoning propagation algorithm with improved complexity of O(n^2 \log^2 n). T3 - ZIB-Report - 16-46 KW - Cumulative Scheduling KW - Energetic Reasoning KW - Sweep Line KW - Constraint Programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60367 SN - 1438-0064 N1 - Preprint Version ER - TY - GEN 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 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. T3 - ZIB-Report - 16-39 KW - Non-reversible Markov Processes KW - NESS KW - Mixed-Integer Programming KW - Markov State Models Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60353 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Löbel, Fabian T1 - The Modulo Network Simplex with Integrated Passenger Routing N2 - Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration. T3 - ZIB-Report - 16-43 KW - periodic timetabling, modulo network simplex, passenger routing Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60319 SN - 1438-0064 ER - TY - GEN A1 - Lie, Han Cheng A1 - Sullivan, T. J. T1 - Cameron--Martin theorems for sequences of Cauchy-distributed random variables N2 - Given a sequence of Cauchy-distributed random variables defined by a sequence of location parameters and a sequence of scale parameters, we consider another sequence of random variables that is obtained by perturbing the location or scale parameter sequences. Using a result of Kakutani on equivalence of infinite product measures, we provide sufficient conditions for the equivalence of laws of the two sequences. T3 - ZIB-Report - 16-40 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60230 SN - 1438-0064 ER - TY - GEN A1 - Krone, Michael A1 - Kozlikova, Barbora A1 - Lindow, Norbert A1 - Baaden, Marc A1 - Baum, Daniel A1 - Parulek, Julius A1 - Hege, Hans-Christian A1 - Viola, Ivan T1 - Visual Analysis of Biomolecular Cavities: State of the Art N2 - In this report we review and structure the branch of molecular visualization that is concerned with the visual analysis of cavities in macromolecular protein structures. First the necessary background, the domain terminology, and the goals of analytical reasoning are introduced. Based on a comprehensive collection of relevant research works, we present a novel classification for cavity detection approaches and structure them into four distinct classes: grid-based, Voronoi-based, surface-based, and probe-based methods. The subclasses are then formed by their combinations. We match these approaches with corresponding visualization technologies starting with direct 3D visualization, followed with non-spatial visualization techniques that for example abstract the interactions between structures into a relational graph, straighten the cavity of interest to see its profile in one view, or aggregate the time sequence into a single contour plot. We also discuss the current state of methods for the visual analysis of cavities in dynamic data such as molecular dynamics simulations. Finally, we give an overview of the most common tools that are actively developed and used in the structural biology and biochemistry research. Our report is concluded by an outlook on future challenges in the field. T3 - ZIB-Report - 16-42 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60193 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. 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. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. T3 - ZIB-Report - 16-41 KW - Steiner tree problem KW - SCIP-Jack KW - Steiner tree variants KW - maximum-weight connected subgraph KW - prize-collecting Steiner tree Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60170 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Arslan, Oytun A1 - Elijazyfer, Ziena A1 - Güler, Hakan A1 - Renken, Malte A1 - Sahin, Güvenc A1 - Schlechte, Thomas T1 - Line Planning on Path Networks with Application to the Istanbul Metrobüs N2 - Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed. T3 - ZIB-Report - 16-38 KW - line planning KW - unimodal demand Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60119 SN - 1438-0064 ER - TY - GEN A1 - Nielsen, Adam T1 - The Monte Carlo Computation Error of Transition Probabilities N2 - In many applications one is interested to compute transition probabilities of a Markov chain. This can be achieved by using Monte Carlo methods with local or global sampling points. In this article, we analyze the error by the difference in the $L^2$ norm between the true transition probabilities and the approximation achieved through a Monte Carlo method. We give a formula for the error for Markov chains with locally computed sampling points. Further, in the case of reversible Markov chains, we will deduce a formula for the error when sampling points are computed globally. We will see that in both cases the error itself can be approximated with Monte Carlo methods. As a consequence of the result, we will derive surprising properties of reversible Markov chains. T3 - ZIB-Report - 16-37 KW - Reversible Markov chain KW - Monte Carlo methods KW - Computation error KW - Measurable state space KW - Markov operator Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59933 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP 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. T3 - ZIB-Report - 16-36 KW - graph transformation KW - Steiner tree problems KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59777 SN - 1438-0064 ER - TY - GEN A1 - Zhang, Wei A1 - Hartmann, Carsten A1 - Schütte, Christof T1 - Effective Dynamics Along Given Reaction Coordinates, and Reaction Rate Theory N2 - In molecular dynamics and related fields one considers dynamical descriptions of complex systems in full (atomic) detail. In order to reduce the overwhelming complexity of realistic systems (high dimension, large timescale spread, limited computational resources) the projection of the full dynamics onto some reaction coordinates is examined in order to extract statistical information like free energies or reaction rates. In this context, the effective dynamics that is induced by the full dynamics on the reaction coordinate space has attracted considerable attention in the literature. In this article, we contribute to this discussion: We first show that if we start with an ergodic diffusion processes whose invariant measure is unique then these properties are inherited by the effective dynamics. Then, we give equations for the effective dynamics, discuss whether the dominant timescales and reaction rates inferred from the effective dynamics are accurate approximations of such quantities for the full dynamics, and compare our findings to results from approaches like Zwanzig-Mori, averaging, or homogenization. Finally, by discussing the algorithmic realization of the effective dynamics, we demonstrate that recent algorithmic techniques like the ”equation-free” approach and the ”heterogeneous multiscale method” can be seen as special cases of our approach. T3 - ZIB-Report - 16-35 KW - Ergodic diffusion KW - reaction coordinate KW - effective dynamics KW - model reduction KW - equation-free KW - heterogeneous multiscale method Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59706 SN - 1438-0064 ER - TY - GEN A1 - Costa, Marta A1 - Manton, James D. A1 - Ostrovsky, Aaron D. A1 - Prohaska, Steffen A1 - Jefferis, Gregory S.X.E. T1 - NBLAST: Rapid, sensitive comparison of neuronal structure and construction of neuron family databases N2 - Neural circuit mapping is generating datasets of 10,000s of labeled neurons. New computational tools are needed to search and organize these data. We present NBLAST, a sensitive and rapid algorithm, for measuring pairwise neuronal similarity. NBLAST considers both position and local geometry, decomposing neurons into short segments; matched segments are scored using a probabilistic scoring matrix defined by statistics of matches and non-matches. We validated NBLAST on a published dataset of 16,129 single Drosophila neurons. NBLAST can distinguish neuronal types down to the finest level (single identified neurons) without a priori information. Cluster analysis of extensively studied neuronal classes identified new types and unreported topographical features. Fully automated clustering organized the validation dataset into 1052 clusters, many of which map onto previously described neuronal types. NBLAST supports additional query types including searching neurons against transgene expression patterns. Finally we show that NBLAST is effective with data from other invertebrates and zebrafish. T3 - ZIB-Report - 16-34 KW - neuroinformatics KW - NBLAST KW - neuron similarity KW - cell type KW - clustering Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59672 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Hege, Hans-Christian A1 - Weiser, Martin T1 - Using sparse kernels to design computer experiments with tunable precision N2 - Statistical methods to design computer experiments usually rely on a Gaussian process (GP) surrogate model, and typically aim at selecting design points (combinations of algorithmic and model parameters) that minimize the average prediction variance, or maximize the prediction accuracy for the hyperparameters of the GP surrogate. In many applications, experiments have a tunable precision, in the sense that one software parameter controls the tradeoff between accuracy and computing time (e.g., mesh size in FEM simulations or number of Monte-Carlo samples). We formulate the problem of allocating a budget of computing time over a finite set of candidate points for the goals mentioned above. This is a continuous optimization problem, which is moreover convex whenever the tradeoff function accuracy vs. computing time is concave. On the other hand, using non-concave weight functions can help to identify sparse designs. In addition, using sparse kernel approximations drastically reduce the cost per iteration of the multiplicative weights updates that can be used to solve this problem. T3 - ZIB-Report - 16-33 KW - Optimal design of computer experiments KW - Sparse kernels KW - Gaussian Process Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59605 SN - 1438-0064 ER - TY - GEN A1 - Becker, Pascal-Nicolas A1 - Bertelmann, Roland A1 - Ceynowa, Klaus A1 - Christof, Jürgen A1 - Dierkes, Thomas A1 - Goltz-Fellgiebel, Julia Alexandra A1 - Groß, Matthias A1 - Heidrich, Regina A1 - Höhnow, Tobias A1 - Kassube, Michael A1 - Koch, Thorsten A1 - Kuberek, Monika A1 - Landes, Lilian A1 - Pampel, Heinz A1 - Putnings, Markus A1 - Rusch, Beate A1 - Schäffler, Hildegard A1 - Schobert, Dagmar A1 - Schwab, Oliver A1 - Schwidder, Jens A1 - Söllner, Konstanze A1 - Stoyanova, Tonka A1 - Vierkant, Paul T1 - DeepGreen – Metadata Schema for the exchange of publications between publishers and open access repositories. Version 1.1. June 2016 N2 - In 2011, important priorities were set to realize green publications in the open access movement in Germany. With financial support from the German Research Foundation (DFG), libraries negotiated Alliance licenses with publishers that guarantee extensive open access rights. Authors of institutions, that have therewith access to licensed journals, can freely publish their articles immediately or after a short embargo period in a repository of their choice. However, authors hesitantly use these open access rights. Also libraries – as managers of institutional and subject based repositories and thus legitimated representatives for the authors – only rarely make use of these rights. The aim of DeepGreen is to make the majority of those publications available online. Together with publishers of the Alliance licenses, the project consortium wants to develop a nearly fully automated workflow that covers both the delivery of data, including the full texts, of the publishers, as well as the data transformation to the necessary import formats and the loading process into the repositories. An intermediate “publication router” will serve as a distribution platform. The DeepGreen metadata schema contains metadata properties describing a wide range of deliverable bibliographic metadata from the Alliance license publishers (most common standards are JATS and CrossRef XML) as well as its compliance with technical, quality and metadata standards of the repositories. The schema includes required metadata elements and optional properties providing additional information.The metadata schema is aligned to the OCLC repository best practices (“Best Practices for CONTENTdm and other OAI-PMH compliant repositories: creating sharable metadata”, URL: http://www.oclc.org/content/dam/support/wcdigitalcollectiongateway/MetadataBestPractices.pdf). The current version of the schema is subject to changes as the functional requirements and workflow practices are evolving during the project experiences and prototype production. T3 - ZIB-Report - 16-32 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59580 SN - 1438-0064 N1 - This work is in the public domain: CC0 1.0 Universal (CC0 1.0) Public Domain Dedication. https://creativecommons.org/publicdomain/zero/1.0/ ER - TY - GEN A1 - Cockayne, Jon A1 - Oates, Chris A1 - Sullivan, T. J. A1 - Girolami, Mark T1 - Probabilistic Meshless Methods for Partial Differential Equations and Bayesian Inverse Problems N2 - This paper develops a class of meshless methods that are well-suited to statistical inverse problems involving partial differential equations (PDEs). The methods discussed in this paper view the forcing term in the PDE as a random field that induces a probability distribution over the residual error of a symmetric collocation method. This construction enables the solution of challenging inverse problems while accounting, in a rigorous way, for the impact of the discretisation of the forward problem. In particular, this confers robustness to failure of meshless methods, with statistical inferences driven to be more conservative in the presence of significant solver error. In addition, (i) a principled learning-theoretic approach to minimise the impact of solver error is developed, and (ii) the challenging setting of inverse problems with a non-linear forward model is considered. The method is applied to parameter inference problems in which non-negligible solver error must be accounted for in order to draw valid statistical conclusions. T3 - ZIB-Report - 16-31 KW - Probabilistic Numerics KW - Partial Differential Equations KW - Inverse Problems KW - Meshless Methods KW - Gaussian Processes KW - Pseudo-Marginal MCMC Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59513 SN - 1438-0064 ER - TY - GEN A1 - Brandt, Christopher A1 - Tycowicz, Christoph von A1 - Hildebrandt, Klaus T1 - Geometric Flows of Curves in Shape Space for Processing Motion of Deformable Objects N2 - We introduce techniques for the processing of motion and animations of non-rigid shapes. The idea is to regard animations of deformable objects as curves in shape space. Then, we use the geometric structure on shape space to transfer concepts from curve processing in R^n to the processing of motion of non-rigid shapes. Following this principle, we introduce a discrete geometric flow for curves in shape space. The flow iteratively replaces every shape with a weighted average shape of a local neighborhood and thereby globally decreases an energy whose minimizers are discrete geodesics in shape space. Based on the flow, we devise a novel smoothing filter for motions and animations of deformable shapes. By shortening the length in shape space of an animation, it systematically regularizes the deformations between consecutive frames of the animation. The scheme can be used for smoothing and noise removal, e.g., for reducing jittering artifacts in motion capture data. We introduce a reduced-order method for the computation of the flow. In addition to being efficient for the smoothing of curves, it is a novel scheme for computing geodesics in shape space. We use the scheme to construct non-linear “Bézier curves” by executing de Casteljau’s algorithm in shape space. T3 - ZIB-Report - 16-29 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59504 SN - 1438-0064 ER - TY - GEN A1 - Amrhein, Kilian A1 - Hasler, Tim A1 - Klindt, Marco A1 - Oltmanns, Elias A1 - Peters-Kottig, Wolfgang T1 - Digitale Langzeitarchivierung: Mustervorlage für Übernahmevereinbarungen N2 - Digitale Langzeitarchivierung erfolgt auf Grundlage verbindlicher Regelungen zwischen Langzeitarchiv und Datengeber. Detaillierte organisatorische und technische Bedingungen für Datenübernahmen werden dabei in Absprache zwischen den Kooperationspartnern in einer Übernahmevereinbarung festgehalten. Im Rahmen der Entwicklung des Langzeitarchivs EWIG am Zuse Institute Berlin ist die hier dokumentierte Mustervorlage für Übernahmevereinbarungen entstanden. T3 - ZIB-Report - 16-27 KW - digital preservation KW - submission agreement KW - digitale Langzeitarchivierung KW - KOBV KW - digiS Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59452 SN - 1438-0064 ER - TY - GEN A1 - Sullivan, T. J. T1 - Well-posed Bayesian inverse problems and heavy-tailed stable Banach space priors N2 - This article extends the framework of Bayesian inverse problems in infinite-dimensional parameter spaces, as advocated by Stuart (Acta Numer. 19:451–559, 2010) and others, to the case of a heavy-tailed prior measure in the family of stable distributions, such as an infinite-dimensional Cauchy distribution, for which polynomial moments are infinite or undefined. It is shown that analogues of the Karhunen–Loève expansion for square-integrable random variables can be used to sample such measures. Furthermore, under weaker regularity assumptions than those used to date, the Bayesian posterior measure is shown to depend Lipschitz continuously in the Hellinger metric upon perturbations of the misfit function and observed data. T3 - ZIB-Report - 16-30 KW - Bayesian inverse problems KW - heavy-tailed distribution KW - Karhunen–Loève expansion KW - stable distribution KW - uncertainty quantification KW - well-posedness Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59422 SN - 1438-0064 ER - TY - GEN A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework 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. T3 - ZIB-Report - 16-24 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59377 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) N2 - In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule. T3 - ZIB-Report - 16-25 KW - Cumulative Scheduling KW - Energetic Reasoning KW - Sweep Line Algorithm Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59332 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Balzer, Felix A1 - Borndörfer, Ralf A1 - Spies, Claudia A1 - von Dincklage, Falk T1 - Makespan and Tardiness in Activity Networks with Lognormal Activity Durations N2 - We propose an algorithm to approximate the distribution of the completion time (makespan) and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling, where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable. This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits. We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very promising results, especially for the approximation of the mean overtime in operating rooms, for which our algorithm yields results of a similar quality to Monte-Carlo simulations requiring an amount of computing time several orders of magnitude larger. T3 - ZIB-Report - 16-23 KW - scheduling KW - activity network KW - lognormal distribution Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59290 SN - 1438-0064 ER - TY - GEN A1 - Kramer, Tobias A1 - Noack, Matthias T1 - On the origin of inner coma structures observed by Rosetta during a diurnal rotation of comet 67P/Churyumov-Gerasimenko. N2 - The Rosetta probe around comet 67P/Churyumov-Gerasimenko (67P) reveals an anisotropic dust distribution of the inner coma with jet-like structures. The physical processes leading to jet formation are under debate, with most models for cometary activity focusing on localised emission sources, such as cliffs or terraced regions. Here we suggest, by correlating high-resolution simulations of the dust environment around 67P with observations, that the anisotropy and the background dust density of 67P originate from dust released across the entire sunlit surface of the nucleus rather than from few isolated sources. We trace back trajectories from coma regions with high local dust density in space to the non-spherical nucleus and identify two mechanisms of jet formation: areas with local concavity in either two dimensions or only one. Pits and craters are examples of the first case, the neck region of the bilobed nucleus of 67P for the latter one. The conjunction of multiple sources in addition to dust released from all other sunlit areas results in a high correlation coefficient (∼0.8) of the predictions with observations during a complete diurnal rotation period of 67P. T3 - ZIB-Report - 16-26 KW - comet KW - 67p Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59225 SN - 1438-0064 ER -