ZIB-Report
Refine
Year of publication
- 2017 (76) (remove)
Document Type
- ZIB-Report (76)
Keywords
- maximum-weight connected subgraph (2)
- metastability (2)
- mixed-integer programming (2)
- reaction coordinate (2)
- transfer operator (2)
- transition manifold (2)
- 2D distance map (1)
- Adaptive Importance Sampling (1)
- Algorithm Analysis (1)
- Amira (1)
Institute
- Mathematical Optimization (35)
- Numerical Mathematics (22)
- Mathematical Optimization Methods (14)
- Visual Data Analysis (13)
- Visual and Data-centric Computing (13)
- Mathematics of Transportation and Logistics (7)
- Computational Medicine (5)
- Digital Data and Information for Society, Science, and Culture (5)
- Energy Network Optimization (4)
- Therapy Planning (4)
17-74
Given a time-dependent stochastic process with trajectories x(t) in a space $\Omega$, there may be sets such that the corresponding trajectories only very rarely cross the boundaries of these sets. We can analyze such a process in terms of metastability or coherence. Metastable sets M are defined in space $M\subset\Omega$, coherent sets $M(t)\subset\Omega$ are defined in space and time. Hence, if we extend the space by the time-variable t, coherent sets are metastable sets in $\Omega\times[0,\infty]$. This relation can be exploited, because there already exist spectral algorithms for the identification of metastable sets. In this article we show that these well-established spectral algorithms (like PCCA+) also identify coherent sets of non-autonomous dynamical systems. For the identification of coherent sets, one has to compute a discretization (a matrix T) of the transfer operator of the process using a space-timediscretization scheme. The article gives an overview about different time-discretization schemes and shows their applicability in two different fields of application.
17-69
The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l.
17-72
Degenerative Gelenkerkrankungen, wie die Osteoarthrose, sind ein häufiges Krankheitsbild unter älteren Erwachsenen. Hierbei verringert sich u.a. der Gelenkspalt aufgrund degenerierten Knorpels oder geschädigter Menisci. Ein in den Gelenkspalt eingebrachter interpositionaler Spacer soll die mit der Osteoarthrose einhergehende verringerte Gelenkkontaktfläche erhöhen und so der teilweise oder vollständige Gelenkersatz hinausgezögert oder vermieden werden.
In dieser Arbeit präsentieren wir eine Planungssoftware für die Auswahl und Positionierung eines interpositionalen Spacers am Patientenmodell. Auf einer MRT-basierten Bildsegmentierung aufbauend erfolgt eine geometrische Rekonstruktion der 3D-Anatomie des Kniegelenks. Anhand dieser wird der Gelenkspalt bestimmt, sowie ein Spacer ausgewählt und algorithmisch vorpositioniert. Die Positionierung des Spacers ist durch den Benutzer jederzeit interaktiv anpassbar.
Für jede Positionierung eines Spacers wird ein Fitness-Wert zur Knieanatomie des jeweiligen Patienten berechnet und den Nutzern Rückmeldung hinsichtlich Passgenauigkeit gegeben. Die Software unterstützt somit als Entscheidungshilfe die behandelnden Ärzte bei der patientenspezifischen Spacerauswahl.
17-71
In this study we investigate methods for fitting a Statistical Shape Model (SSM) to intraoperatively acquired point cloud data from a surgical navigation system. We validate the fitted models against the pre-operatively acquired Magnetic Resonance Imaging (MRI) data from the same patients.
We consider a cohort of 10 patients who underwent navigated total knee arthroplasty. As part of the surgical protocol the patients’ distal femurs were partially digitized. All patients had an MRI scan two months pre-operatively. The MRI data were manually segmented and the reconstructed bone surfaces used as ground truth against which the fit was compared. Two methods were used to fit the SSM to the data, based on (1) Iterative Closest Points (ICP) and (2) Gaussian Mixture Models (GMM).
For both approaches, the difference between model fit and ground truth surface averaged less than 1.7 mm and excellent correspondence with the distal femoral morphology can be demonstrated.
17-53
Spectral deferred correction (SDC) Methoden, vorgestellt von Dutt, Greengard und
Rokhlin in [1], sind iterative Verfahren zur numerischen Lösung von Anfangswertproblemen für gewöhnliche Differentialgleichungen. Wenn diese Methoden konvergieren, dann wird unter Verwendung von Zeitschrittverfahren niedriger Ordnung eine Kollokationslösung berechnet. Die Lösung von steifen Anfangswertproblemen ist eine relevante Problemstellung in der numerischen Mathematik. SDC-Methoden, speziell für steife Probleme, werden von Martin Weiser in [2] konstruiert. Die Theorie und die Experimente beziehen sich dabei auf Probleme, die aus räumlich semidiskretisierten Reaktions-Diffusions-Gleichungen entstehen.
In dieser Arbeit werden die Ansätze aus [2] auf Konvektions-Diffusions-Gleichungen
angewendet und das resultierende Konvergenzverhalten von SDC-Methoden untersucht.
Basierend auf einem einfachen Konvektions-Diffusions-Operator, dessen spektrale Eigenschaften umfassend studiert werden, wird ein Schema zur Verbesserung dieses Verhaltens entwickelt. Numerische Experimente zeigen, dass eine Verbesserung der in [1] eingeführten SDC-Methoden möglich ist. Die Untersuchungen ergeben weiterhin, dass das auch für komplexere Konvektions-Diffusions-Probleme gilt.
[1] Alok Dutt, Leslie Greengard, und Vladimir Rokhlin. “Spectral deferred correction
methods for ordinary differential equations.” In: BIT 40.2 (2000), pp. 241–266.
[2] Martin Weiser. “Faster SDC convergence on non-equidistant grids by DIRK
sweeps.” In: BIT 55.4 (2015), pp. 1219–1241.
17-63
Rolling stock optimization is a task that naturally arises by operating a railway system.
It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike.
Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.
17-62
Introduction – Many biological structures show recurring tiling patterns on one structural level or the other. Current image acquisition techniques are able to resolve those tiling patterns to allow quantitative analyses. The resulting image data, however, may contain an enormous number of elements. This renders manual image analysis infeasible, in particular when statistical analysis is to be conducted, requiring a larger number of image data to be analyzed. As a consequence, the analysis process needs to be automated to a large degree. In this paper, we describe a multi-step image segmentation pipeline for the automated segmentation of the calcified cartilage into individual tesserae from computed tomography images of skeletal elements of stingrays.
Methods – Besides applying state-of-the-art algorithms like anisotropic diffusion smoothing, local thresholding for foreground segmentation, distance map calculation, and hierarchical watershed, we exploit a graph-based representation for fast correction of the segmentation. In addition, we propose a new distance map that is computed only in the plane that locally best approximates the calcified cartilage. This distance map drastically improves the separation of individual tesserae. We apply our segmentation pipeline to hyomandibulae from three individuals of the round stingray (Urobatis halleri), varying both in age and size.
Results – Each of the hyomandibula datasets contains approximately 3000 tesserae. To evaluate the quality of the automated segmentation, four expert users manually generated ground truth segmentations of small parts of one hyomandibula. These ground truth segmentations allowed us to compare the segmentation quality w.r.t. individual tesserae. Additionally, to investigate the segmentation quality of whole skeletal elements, landmarks were manually placed on all tesserae and their positions were then compared to the segmented tesserae. With the proposed segmentation pipeline, we sped up the processing of a single skeletal element from days or weeks to a few hours.
17-66
Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.
17-64
Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them.
This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances.
PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation.
17-59
This report aims to explain and extend pattern databases as a tool in finding optimal solutions to combination puzzles. Using sliding tile puzzles as an example, an overview over techniques to construct and use pattern databases is given, analysed, and extended. As novel results, zero aware additive pattern databases and PDB catalogues are introduced. This report originally appeared as a bachelor thesis at Humboldt University of Berlin under the title Notes on the Construction of Tablebases.