Publication Server of Zuse Institute Berlin (ZIB)
Not a member yet
6648 research outputs found
Sort by
Cutting Plane Selection with Analytic Centers and Multiregression
No full textCutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method
Adaptive Gaussian Process Regression for Efficient Building of Surrogate Models in Inverse Problems
No full textIn a task where many similar inverse problems must be solved, evaluating costly simulations is impractical. Therefore, replacing the model y with a surrogate model y(s) that can be evaluated quickly leads to a significant speedup. The approximation quality of the surrogate model depends strongly on the number, position, and accuracy of the sample points. With an additional finite computational budget, this leads to a problem of (computer) experimental design. In contrast to the selection of sample points, the trade-off between accuracy and effort has hardly been studied systematically. We therefore propose an adaptive algorithm to find an optimal design in terms of
position and accuracy. Pursuing a sequential design by incrementally appending the computational budget leads to a convex and constrained optimization problem. As a surrogate, we construct a Gaussian process regression model. We measure the global approximation error in terms of its impact on the accuracy of the identified parameter and aim for a uniform absolute tolerance, assuming that y(s) is computed by finite element calculations. A priori error estimates and a coarse estimate of computational effort relate the expected improvement of the surrogate model error to computational effort, resulting in the most efficient combination of sample point and evaluation tolerance. We also allow for improving the accuracy of already existing sample points by continuing previously truncated finite element solution procedures
On the Accuracy of Eikonal Approximations in Cardiac Electrophysiology in the Presence of Fibrosis
No full textFibrotic tissue is one of the main risk factors for cardiac arrhythmias. It is therefore a key component in computational studies. In this work, we compare the monodomain equation to two eikonal models for cardiac electrophysiology in the presence of fibrosis. We show that discontinuities in the conductivity field, due to the presence of fibrosis, introduce a delay in the activation times. The monodomain equation and eikonal-diffusion model correctly capture these delays, contrarily to the classical eikonal equation. Importantly, a coarse space discretization of the monodomain equation amplifies these delays, even after accounting for numerical error in conduction velocity. The numerical discretization may also introduce artificial conduction blocks and hence increase propagation complexity. Therefore, some care is required when comparing eikonal models to the discretized monodomain equation
Impact Study of Numerical Discretization Accuracy on Parameter Reconstructions and Model Parameter Distributions
No full textIn optical nano metrology numerical models are used widely for parameter reconstructions. Using the Bayesian target vector optimization method we fit a finite element numerical model to a Grazing Incidence x-ray fluorescence data set in order to obtain the geometrical parameters of a nano structured line grating. Gaussian process, stochastic machine learning surrogate models, were trained during the reconstruction and afterwards sampled with a Markov chain Monte Carlo sampler to determine the distribution of the reconstructed model parameters. The numerical discretization parameters of the used finite element model impact the numerical discretization error of the forward model. We investigated the impact of the polynomial order of the finite element ansatz functions on the reconstructed parameters as well as on the model parameter distributions. We showed that such a convergence study allows to determine numerical parameters which allows for efficient and accurate reconstruction results
Enhancing molecular visualization: Perceptual evaluation of line variables with application to uncertainty visualization
No full textData are often subject to some degree of uncertainty, whether aleatory or epistemic. This applies both to experimental data acquired with sensors as well as to simulation data. Displaying these data and their uncertainty faithfully is crucial for gaining knowledge. Specifically, the effective communication of the uncertainty can influence the interpretation of the data and the user’s trust in the visualization. However, uncertainty-aware visualization has gotten little attention in molecular visualization. When using the established molecular representations, the physicochemical attributes of the molecular data usually already occupy the common visual channels like shape, size, and color. Consequently, to encode uncertainty information, we need to open up another channel by using feature lines. Even though various line variables have been proposed for uncertainty visualizations, they have so far been primarily used for two-dimensional data and there has been little perceptual evaluation. Thus, we conducted two perceptual studies to determine the suitability of the line variables blur, dashing, grayscale, sketchiness, and width for distinguishing several values in molecular visualizations. While our work was motivated by uncertainty visualization, our techniques and study results also apply to other types of scalar data
On the Split Closure of the Periodic Timetabling Polytope
No full textThe Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables.
We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed.
Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances
Convergence Properties of Newton's Method for Globally Optimal Free Flight Trajectory Optimization
No full textThe algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition
Geometric Data Analysis: Advancements of the Statistical Methodology and Applications
No full textData analysis has become fundamental to our society and comes in multiple facets and approaches. Nevertheless, in research and applications, the focus was primarily on data from Euclidean vector spaces. Consequently, the majority of methods that are applied today are not suited for more general data types. Driven by needs from fields like image processing, (medical) shape analysis, and network analysis, more and more attention has recently been given to data from non-Euclidean spaces---particularly (curved) manifolds. It has led to the field of geometric data analysis whose methods explicitly take the structure (for example, the topology and geometry) of the underlying space into account.
This thesis contributes to the methodology of geometric data analysis by generalizing several fundamental notions from multivariate statistics to manifolds. We thereby focus on two different viewpoints.
First, we use Riemannian structures to derive a novel regression scheme for general manifolds that relies on splines of generalized Bézier curves. It can accurately model non-geodesic relationships, for example, time-dependent trends with saturation effects or cyclic trends. Since Bézier curves can be evaluated with the constructive de Casteljau algorithm, working with data from manifolds of high dimensions (for example, a hundred thousand or more) is feasible. Relying on the regression, we further develop
a hierarchical statistical model for an adequate analysis of longitudinal data in manifolds, and a method to control for confounding variables.
We secondly focus on data that is not only manifold- but even Lie group-valued, which is frequently the case in applications. We can only achieve this by endowing the group with an affine connection structure that is generally not Riemannian. Utilizing it, we derive generalizations of several well-known dissimilarity measures between data distributions that can be used for various tasks, including hypothesis testing. Invariance under data translations is proven, and a connection to continuous distributions is given for one measure.
A further central contribution of this thesis is that it shows use cases for all notions in real-world applications, particularly in problems from shape analysis in medical imaging and archaeology. We can replicate or further quantify several known findings for shape changes of the femur and the right hippocampus under osteoarthritis and Alzheimer's, respectively. Furthermore, in an archaeological application, we obtain new insights into the construction principles of ancient sundials. Last but not least, we use the geometric structure underlying human brain connectomes to predict cognitive scores. Utilizing a sample selection procedure, we obtain state-of-the-art results
Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice
No full textWe consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances
