344
eng
reportzib
0
1998-01-19
1998-01-19
--
A Study of Genetic Algorithms solving a combinatorial Puzzle
The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings.
SC-98-01
345
urn:nbn:de:0297-zib-3445
Thomas Wolf
ZIB-Report
SC-98-01
Informatik, Informationswissenschaft, allgemeine Werke
COMBINATORICS (For finite fields, see 11Txx)
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/344/SC-98-01.ps
https://opus4.kobv.de/opus4-zib/files/344/SC-98-01.pdf
1488
eng
reportzib
0
2012-03-19
2012-03-19
--
Estimating trenching costs in FTTx network planning
In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".
1438-0064
urn:nbn:de:0297-zib-14884
10.1007/978-3-642-29210-1_15
Appeared in: Operations Research Proceedings 2011. D. Klatte, H.-J. Lüthi, K. Schmedders (eds.) 2012, pp. 89-94
Axel Werner
Sebastian Orlowski
Axel Werner
Roland Wessäly
ZIB-Report
11-49
eng
uncontrolled
Optical access networks
eng
uncontrolled
Optimization
eng
uncontrolled
Steiner trees
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1488/OR-Proc-2011.pdf
1434
2011
eng
reportzib
0
2011-12-19
2011-12-19
--
Perception-Oriented Picking of Structures in Direct Volumetric Renderings
Radiologists from all application areas are trained to read slice-based visualizations of 3D medical image data. Despite the numerous
examples of sophisticated three-dimensional renderings, especially all variants of direct volume rendering, such methods are
often considered not very useful by radiologists who prefer slice-based visualization. Just recently there have been attempts to bridge this
gap between 2D and 3D renderings. These attempts include specialized techniques for volume picking that result in repositioning slices.
In this paper, we present a new volume picking technique that, in contrast to previous work, does not require pre-segmented data or metadata. The positions picked by our method are solely based on the data itself, the transfer function and,
most importantly, on the way the volumetric rendering is perceived by viewers. To demonstrate the usefulness of the proposed method
we apply it for automatically
repositioning slices in an abdominal MRI
scan, a data set from a flow simulation and a number of other volumetric scalar fields. Furthermore we discuss how the method can be implemented in combination with various different volumetric rendering techniques.
1438-0064
11-45
urn:nbn:de:0297-zib-14343
no
Alexander Wiebel
Alexander Wiebel
Frans M. Vos
Hans-Christian Hege
ZIB-Report
11-45
eng
uncontrolled
DVR
eng
uncontrolled
picking
eng
uncontrolled
pointing
eng
uncontrolled
direct volume rendering
PHYSICAL SCIENCES AND ENGINEERING
LIFE AND MEDICAL SCIENCES
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Visual Data Analysis
Hege, Hans-Christian
VIGOR++
https://opus4.kobv.de/opus4-zib/files/1434/result.pdf
5329
2014
eng
reportzib
0
--
2014-12-10
--
Computing the nearest reversible Markov chain
Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.
1438-0064
urn:nbn:de:0297-zib-53292
Adam Nielsen
Adam Nielsen
Marcus Weber
ZIB-Report
14-48
eng
uncontrolled
Reversible Markov Chain
eng
uncontrolled
Convex Optimization
eng
uncontrolled
MSM
LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Numerical Mathematics
Computational Molecular Design
Weber, Marcus
BMS-Nielsen
https://opus4.kobv.de/opus4-zib/files/5329/ZR-14-48.pdf
5330
2015
eng
483
499
3
22
article
0
--
--
--
Computing the nearest reversible Markov chain
Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.
Numerical Linear Algebra with Applications
10.1002/nla.1967
yes
urn:nbn:de:0297-zib-53292
Adam Nielsen
Adam Nielsen
Marcus Weber
eng
uncontrolled
Reversible Markov Chain
deu
uncontrolled
Convex Optimization
deu
uncontrolled
MSM
LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Numerical Mathematics
Computational Molecular Design
Weber, Marcus
BMS-Nielsen
EyeTracking
NonequiMSM
SFB1114-A5
4221
deu
111
bachelorthesis
0
2013-08-29
2013-08-29
2013-01-24
Effiziente Reoptimierung in Branch&Bound-Verfahren für die Steuerung von Aufzügen
Heutzutage ist eine Vielzahl der mehrstöckigen Gebäude mit Personenaufzugsgruppen
ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei
diesen Systemen betätigt jeder ankommende Passagier eine der beiden Richtungstasten
und teilt dem dahinterstehenden Steuerungsalgorithmus seine gewünschte Startetage
und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug
mit gleicher Fahrtrichtung und ausreichend Kapazität. Die entsprechende Zieletage
wird dem System erst nach dem Betreten der Fahrgastkabine mitgeteilt. Neben diesen
konventionellen Systemen gibt es Aufzugsgruppen mit Zielrufsteuerung. Die Besonderheit
eines zielrufgesteuerten Systems ist, dass ein ankommender Passagier bereits auf
der Startetage seine gewünschte Zieletage angibt und eine Rückmeldung vom System
erhält, welchen Aufzug er nutzen soll. Diese Zuweisung durch das System hat das Ziel,
die Warte- und Reisezeiten der Passagiere zu minimieren. Ein wesentlicher Faktor bei
der Berechnung warte- und reisezeitminimaler Fahrpläne ist das momentane Verkehrsmuster.
Eine Einteilung der Verkehrsszenarien lässt sich am besten bei Bürogebäuden
vornehmen. So ist es typisch für die Morgenstunden, dass jeder Passagier auf einer
Zugangsebene seine Fahrt beginnt und alle Passagiere die gleiche Fahrtrichtung haben.
Unter einer Zugangsebene ist z. B. der Haupteingang oder ein Parkdeck zu verstehen.
Ein weiterer wesentlicher Punkt bei Zielrufsystemen ist die Art der Zuweisung der Passagiere
durch das System. Zum einen gibt es unmittelbar zuweisende (UZ-) Systeme.
In einem UZ-System wird nach jeder Ankunft eines Passagiers eine Momentaufnahme
des momentanen Verkehrs erstellt und es findet eine Neuplanung und Zuweisung statt.
Eine solche Momentaufnahme werden wir im späteren Verkauf als Schnappschussproblem
bezeichnen. Jeder Passagier bekommt im Anschluss an die Lösung des Schnappschussproblems
eine Mitteilung vom System, z. B. über ein Display, welchen Aufzug
er benutzen soll. Zum anderen gibt es verzögert zuweisende (VZ-) Systeme. In diesen
Systemen wird die Erstellung und Lösung eines Schnappschussproblems bis kurz vor
Ankunft eines Aufzuges auf einer Etage verzögert. In einem VZ-System teilt das System
allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit.
Jeder Passagier, der einen Ruf getätigt hat und zu einer dieser Zieletagen fahren will,
kann jetzt diesen Aufzug betreten. Durch die Verzögerung muss im Vergleich zu einem
UZ-System eine weitaus größere Menge von Passagieren zugewiesen werden. Dadurch
kann der Lösungsprozess bedeutend aufwändiger werden. Vorteil eines VZ-Systems ist
hingegen der größere Freiheitsgrad bei der Optimierung, da aufgrund der späten Zuweisung
die weitere Verkehrsentwicklung mit einbezogen werden kann.
VZ-Systeme sind aufgrund des größeren Freiheitsgrades interessant für die
Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren Lösung dieser
Art von Schnappschussproblemen befassen. Es genügt dabei den Lösungsprozess eines
Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der benötigten
Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion
zulässiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung
innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer
Menge zulässiger Touren mit negativen reduzierten Kosten. Eine effiziente Reoptimierung
zeichnet sich durch die Wiederverwendung und Aufbereitung von Informationen
aus vorangegangenen Iterationsrunden desselben Schnappschussproblems aus. Zu den
wichtigen Informationen gehört der konstruierte Suchbaum der vorherigen Iterationsrunde
mit seinen ausgeloteten (abgeschnittenen) Blättern sowie konstruierten Touren
bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur Lösung des
Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und
Aufbereitung von Informationen nennen wir Warmstart.
urn:nbn:de:0297-zib-42210
Benjamin Hiller
Jakob Witzig
Jakob Witzig
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Studienabschlussarbeiten
Mathematical Optimization
Witzig, Jakob
Zuse Institute Berlin (ZIB)
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/4221/Bachelorarbeit.pdf
6207
eng
reportzib
0
--
2017-01-03
--
An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates
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.
1438-0064
urn:nbn:de:0297-zib-62075
Jannes Quer
Jannes Quer
Luca Donati
Bettina Keller
Marcus Weber
ZIB-Report
17-09
eng
uncontrolled
Adaptive Importance Sampling
eng
uncontrolled
Molecular Dynamics
eng
uncontrolled
Metastability
eng
uncontrolled
Variance Reduction
eng
uncontrolled
Non Equilibrium Sampling
eng
uncontrolled
Metadynamics
eng
uncontrolled
Girsanov
Computer Applications
DYNAMICAL SYSTEMS AND ERGODIC THEORY [See also 26A18, 28Dxx, 34Cxx, 34Dxx, 35Bxx, 46Lxx, 58Jxx, 70-XX]
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
NUMERICAL ANALYSIS
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Numerical Mathematics
Weber, Marcus
SFB1114-A5
Quer, jannes
https://opus4.kobv.de/opus4-zib/files/6207/AISZIB.pdf
6231
2017
eng
reportzib
0
--
2017-03-24
--
Monte-Carlo-based inversion scheme for 3D quantitative photoacoustic tomography
The goal of quantitative photoacoustic tomography (qPAT) is to recover maps of the chromophore distributions from multiwavelength images of the initial pressure. Model-based inversions that incorporate the physical processes underlying the photoacoustic (PA) signal generation represent a promising approach. Monte-Carlo models of the light transport are computationally expensive, but provide accurate fluence distributions predictions, especially in the ballistic and quasi-ballistic regimes. Here, we focus on the inverse problem of 3D qPAT of blood oxygenation and investigate the application of the Monte-Carlo method in a model-based inversion scheme. A forward model of the light transport based on the MCX simulator and acoustic propagation modeled by the k-Wave toolbox was used to generate a PA image data set acquired in a tissue phantom over a planar detection geometry. The combination of the optical and acoustic models is shown to account for limited-view artifacts. In addition, the errors in the fluence due to, for example, partial volume artifacts and absorbers immediately adjacent to the region of interest are investigated. To accomplish large-scale inversions in 3D, the number of degrees of freedom is reduced by applying image segmentation to the initial pressure distribution to extract a limited number of regions with homogeneous optical parameters. The absorber concentration in the tissue phantom was estimated using a coordinate descent parameter search based on the comparison between measured and modeled PA spectra. The estimated relative concentrations using this approach lie within 5 % compared to the known concentrations. Finally, we discuss the feasibility of this approach to recover the blood oxygenation from experimental data.
1438-0064
urn:nbn:de:0297-zib-62318
10.1117/12.2251945
Appeared in: Proc. SPIE 10064, Photons Plus Ultrasound: Imaging and Sensing 2017, 100645J (March 23, 2017)
Bernhard Kaplan
Bernhard Kaplan
Jan Laufer
Steffen Prohaska
Jens Buchmann
ZIB-Report
17-04
eng
uncontrolled
quantitative photoacoustic tomography
eng
uncontrolled
model-based inversion
eng
uncontrolled
oxygen saturation
eng
uncontrolled
chromophore concentration
eng
uncontrolled
photoacoustic imaging
eng
uncontrolled
Monte Carlo methods for light transport
eng
uncontrolled
boundary conditions
eng
uncontrolled
coordinate search
Computer Applications
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Visual Data Analysis
Prohaska, Steffen
Kaplan, Bernhard
dfg-photom
https://opus4.kobv.de/opus4-zib/files/6231/zib_report_qpat.pdf
6182
eng
reportzib
0
--
2017-01-25
--
Revealing hidden text in rolled and folded papyri
Ancient Egyptian papyri are often folded, rolled up or kept as small packages, sometimes even sealed. Physically unrolling or unfolding these packages might severely damage them. We demonstrate a way to get access to the hidden script without physical unfolding by employing computed tomography and mathematical algorithms for virtual unrolling and unfolding. Our algorithmic approaches are combined with manual interaction. This provides the necessary flexibility to enable the unfolding of even complicated and partly damaged papyrus packages. In addition, it allows us to cope with challenges posed by the structure of ancient papyrus, which is rather irregular, compared to other writing substrates like metallic foils or parchment. Unfolding of packages is done in two stages. In the first stage, we virtually invert the physical folding process step by step until the partially unfolded package is topologically equivalent to a scroll or a papyrus sheet folded only along one fold line. To minimize distortions at this stage, we apply the method of moving least squares. In the second stage, the papyrus is simply flattened, which requires the definition of a medial surface. We have applied our software framework to several papyri. In this work, we present the results of applying our approaches to mockup papyri that were either rolled or folded along perpendicular fold lines. In the case of the folded papyrus, our approach represents the first attempt to address the unfolding of such complicated folds.
1438-0064
urn:nbn:de:0297-zib-61826
10.1007/s00339-017-0808-6
Appeared in: Applied Physics A 123 (2017) pp. 171
Daniel Baum
Daniel Baum
Norbert Lindow
Hans-Christian Hege
Verena Lepper
Tzulia Siopi
Frank Kutz
Kristin Mahlow
Heinz-Eberhard Mahnke
ZIB-Report
17-02
eng
uncontrolled
unfolding, papyri, computed tomography
Computer Applications
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Visual Data Analysis
Baum, Daniel
Hege, Hans-Christian
Lindow, Norbert
no-project
https://opus4.kobv.de/opus4-zib/files/6182/ZR-17-02.pdf
5498
eng
reportzib
0
--
2015-05-08
--
Bag-Of-SFA-Symbols in Vector Space (BOSS VS)
Time series classification mimics the human understanding of similarity. When it comes to larger datasets, state of the art classifiers reach their limits in terms of unreasonable training or testing times. One representative example is the 1-nearest-neighbor DTW classifier (1-NN DTW) that is commonly used as the benchmark to compare to and has several shortcomings: it has a quadratic time and it degenerates in the presence of noise. To reduce the computational complexity lower bounding techniques or recently a nearest centroid classifier have been introduced. Still, execution times to classify moderately sized datasets on a single core are in the order of hours. We present our Bag-Of-SFA-Symbols in Vector Space (BOSS VS) classifier that is robust and accurate due to invariance to noise, phase shifts, offsets, amplitudes and occlusions. We show that it is as accurate while being multiple orders of magnitude faster than state of the art classifiers. Using the BOSS VS allows for mining massive time series datasets and real-time analytics.
1438-0064
urn:nbn:de:0297-zib-54984
Patrick Schäfer
Patrick Schäfer
ZIB-Report
15-30
eng
uncontrolled
Time Series
eng
uncontrolled
Classification
eng
uncontrolled
Data Mining
Information Search and Retrieval
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Distributed Algorithms and Supercomputing
Schäfer, Patrick
no-project
https://opus4.kobv.de/opus4-zib/files/5498/ZR-15-30.pdf
5554
eng
reportzib
0
--
2015-07-10
--
Adaptive telecommunication network operation with a limited number of reconfigurations
Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators’ concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch & Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.
1438-0064
urn:nbn:de:0297-zib-55547
Frank Pfeuffer
Axel Werner
Axel Werner
ZIB-Report
15-36
eng
uncontrolled
Telecommunication
eng
uncontrolled
Network Design
eng
uncontrolled
Dynamic Traffic
eng
uncontrolled
Branch and Bound
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
SASER-Siegfried
https://opus4.kobv.de/opus4-zib/files/5554/lim-reconf-ZR.pdf
https://opus4.kobv.de/opus4-zib/files/5554/lim-reconf-ZR-v2.pdf
6551
2017
eng
ZIB-Report 17-58
reportzib
0
2017-07-11
2017-07-11
--
Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs
PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.
1438-0064
urn:nbn:de:0297-zib-65517
Lluis-Miquel Munguia
Yuji Shinano
Geoffrey Oxberry
Deepak Rajan
Yuji Shinano
ZIB-Report
17-58
eng
uncontrolled
PIPS-SBB, UG, Parallel Branch and Bound
eng
psyndex
PIPS-SBB, UG, Parallel Branch and Bound
Mathematics of Computing
Computing Methodologies
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MODAL-SynLab
https://opus4.kobv.de/opus4-zib/files/6551/ZIB-Report-17-58.pdf
1425
2011
eng
reportzib
0
2011-11-05
2011-11-05
--
Level of Detail for Trees Using Clustered Ellipsoids
We present a level of detail method for trees based on ellipsoids and lines. We leverage the Expectation Maximization algorithm with a Gaussian Mixture Model to create a hierarchy of high-quality leaf clusterings, while the branches are simplified using agglomerative bottom-up clustering to preserve the connectivity. The simplification runs in a preprocessing step and requires no human interaction. For a fly by over and through a scene of 10k trees, our method renders on average at 40 ms/frame, up to 6 times faster than billboard clouds with comparable artifacts.
1438-0064
11-41
urn:nbn:de:0297-zib-14251
no
Malte Clasen
Steffen Prohaska
Philip Paar
Steffen Prohaska
ZIB-Report
11-41
eng
uncontrolled
level of detail
eng
uncontrolled
rendering
eng
uncontrolled
natural scene
eng
uncontrolled
Gaussian mixture model
Computing Methodologies
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY
NUMERICAL ANALYSIS
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Visual Data Analysis
Image Analysis in Biology and Materials Science
Prohaska, Steffen
https://opus4.kobv.de/opus4-zib/files/1425/zibreport.pdf
5295
eng
reportzib
0
--
2014-10-28
--
Automated stitching of microtubule centerlines across serial electron tomograms
Tracing microtubule centerlines in serial section electron tomography requires microtubules to be stitched across sections, that is lines from different sections need to be aligned, endpoints need to be matched at section boundaries to establish a correspondence between neighboring sections, and corresponding lines need to be connected across multiple sections. We present computational methods for these tasks: 1) An initial alignment is computed using a distance compatibility graph. 2) A fine alignment is then computed with a probabilistic variant of the iterative closest points algorithm, which we extended to handle the orientation of lines by introducing a periodic random variable to the probabilistic formulation. 3) Endpoint correspondence is established by formulating a matching problem in terms of a Markov random field and computing the best matching with belief propagation. Belief propagation is not generally guaranteed to converge to a minimum. We show how convergence can be achieved, nonetheless, with minimal manual input. In addition to stitching microtubule centerlines, the correspondence is also applied to transform and merge the electron tomograms. We applied the proposed methods to samples from the mitotic spindle in C. elegans, the meiotic spindle in X. laevis, and sub-pellicular microtubule arrays in T. brucei. The methods were able to stitch microtubules across section boundaries in good agreement with experts’ opinions for the spindle samples. Results, however, were not satisfactory for the microtubule arrays. For certain experiments, such as an analysis of the spindle, the proposed methods can replace manual expert tracing and thus enable the analysis of microtubules over long distances with reasonable manual effort.
1438-0064
urn:nbn:de:0297-zib-52958
10.1371/journal.pone.0113222
published in PLoS ONE
Britta Weber
Steffen Prohaska
Erin M. Tranfield
Johanna L. Höög
Daniel Baum
Claude Antony
Tony Hyman
Jean-Marc Verbavatz
Steffen Prohaska
ZIB-Report
14-41
eng
uncontrolled
electron tomography
eng
uncontrolled
microtubules
eng
uncontrolled
serial sectioning
eng
uncontrolled
image analysis
eng
uncontrolled
geometry reconstruction
eng
uncontrolled
image and geometry alignment
eng
uncontrolled
point correspondence
Applications
Biology and genetics (REVISED)
Cell processes
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
BIOLOGY AND OTHER NATURAL SCIENCES
Visual Data Analysis
Image Analysis in Biology and Materials Science
Baum, Daniel
Prohaska, Steffen
MICROTUBULES
SPINDLE
https://opus4.kobv.de/opus4-zib/files/5295/zibreport-14-41_v1.pdf
1650
eng
reportzib
0
2012-11-15
2012-11-15
--
Stochastic dominance analysis of Online Bin Coloring algorithms
This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.
1438-0064
urn:nbn:de:0297-zib-16502
Benjamin Hiller
Benjamin Hiller
Tjark Vredeveld
ZIB-Report
12-42
eng
uncontrolled
online algorithms, stochastic dominance, algorithm analysis, Markov chains
PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MATHEON-B14:Comb-Log
https://opus4.kobv.de/opus4-zib/files/1650/ZR-12-42.pdf
4267
eng
reportzib
0
2013-10-03
2013-10-03
--
Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks
We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
1438-0064
urn:nbn:de:0297-zib-42675
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384
Appeared in: Proceedings of the 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt 2013) - RAWNET/WNC3’13, pp.652-658, 13-17 May 2013, Tsukuba Science City, Japan
Anna Zakrzewska
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Sarah Ruepp
Michael S. Berger
ZIB-Report
13-63
eng
uncontrolled
Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
INFORMATION AND COMMUNICATION, CIRCUITS
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4267/ZR-13-63.pdf
4265
eng
reportzib
0
2013-10-03
2013-10-03
--
Scheduling technology migration in WDM Networks
The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).
1438-0064
urn:nbn:de:0297-zib-42654
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670
Appeared in: Proceedings of the 14th ITG Symposium on Photonic Networks 2013, pp. 1-5, 6-7 May 2013, Leipzig, Germany
Andreas Bley
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Daniel Karch
ZIB-Report
13-62
eng
uncontrolled
Scheduling, Extended Formulations, Network Migration, WDM Networks
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4265/ZR-13-62.pdf
4264
eng
reportzib
0
2013-10-03
2013-10-03
--
A new theoretical framework for Robust Optimization under multi-band uncertainty
We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.
1438-0064
urn:nbn:de:0297-zib-42644
http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6
10.1007/978-3-319-00795-3_17
To appear in Operations Research Proceedings 2012 - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012, Helber, S. et al. (Eds.), Springer, Heidelberg.
Christina Büsing
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
ZIB-Report
13-61
eng
uncontrolled
Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4264/ZR-13-61.pdf
4255
eng
reportzib
0
2013-09-25
2013-09-25
--
Network Planning under Demand Uncertainty with Robust Optimization
The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.
1438-0064
urn:nbn:de:0297-zib-42557
10.1109/MCOM.2014.6736760
Accepted for publication in IEEE Communications Magazine, special issue Advances in Network Planning, on September 8th 2013
Thomas Bauschert
Fabio D'Andreagiovanni
Christina Büsing
Fabio D'Andreagiovanni
Arie M. C. A. Koster
Manuel Kutschka
Uwe Steglich
ZIB-Report
13-59
eng
uncontrolled
Network Design, Demand Uncertainty, Robust Optimization, Telecommunications
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4255/ZR-13-59.pdf
5406
2014
2014
eng
176
masterthesis
0
--
--
2014-10-20
Reoptimization Techniques in MIP Solvers
Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem
becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems.
In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process
of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence.
At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this
thesis, 2013. Since most of the state-of-the-art MIP
solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process.
urn:nbn:de:0297-zib-54067
Martin Grötschel
Jakob Witzig
Jakob Witzig
Benjamin Hiller
Computer Applications
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Mathematical Optimization
Witzig, Jakob
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/5406/Masterarbeit.pdf
4338
eng
reportzib
0
2013-12-18
2013-12-18
--
Multiband Robust Optimization and its Adoption in Harvest Scheduling
A central assumption in classical optimization is that all the input data of a
problem are exact. However, in many real-world problems, the input data are subject
to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal
solutions that are actually suboptimal or even infeasible. Robust optimization
offers a remedy for optimization under uncertainty by considering only the subset of
solutions protected against the data deviations. In this paper, we provide an overview
of the main theoretical results of multiband robustness, a new robust optimization
model that extends and refines the classical theory introduced by Bertsimas and Sim.
After introducing some new results for the special case of pure binary programs, we
focus on the harvest scheduling problem and show how multiband robustness can
be adopted to tackle the uncertainty affecting the volume of produced timber and
grant a reduction in the price of robustness.
1438-0064
urn:nbn:de:0297-zib-43380
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Annie Raymond
ZIB-Report
13-76
eng
uncontrolled
Data Uncertainty
eng
uncontrolled
Robust Optimization
eng
uncontrolled
Multiband Robustness
eng
uncontrolled
Harvest Scheduling
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4338/ZR-13-76_RobustHarvestScheduling_DAndreagiovanniRaymond.pdf
4408
eng
reportzib
0
2014-02-12
2013-12-30
--
A hybrid primal heuristic for Robust Multiperiod Network Design
We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty.
Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.
1438-0064
urn:nbn:de:0297-zib-44081
To appear in EvoApplications - Proc. of EvoStar 2014, Esparcia-Alcazar, A. et al. (Eds.), Lecture Notes in Computer Science, Springer, Heidelberg
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Jonatan Krolikowski
Jonad Pulaj
ZIB-Report
13-78
eng
uncontrolled
Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
Pulaj, Jonad
https://opus4.kobv.de/opus4-zib/files/4408/ZR-13-78_RobustMultiperiodNetworkDesign_DAndreatiovanniEtAl.pdf
4409
eng
reportzib
0
2014-02-12
2013-12-30
--
0-1 Multiband Robust Optimization
We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM.
1438-0064
urn:nbn:de:0297-zib-44093
To appear in: Operations Research Proceedings 2013 - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Erasmus University Rotterdam, The Netherlands, September 3-6, 2013, Springer, Heidelberg
Christina Büsing
Fabio D'Andreagiovanni
Fabio D'Andreagiovanni
Annie Raymond
ZIB-Report
13-77
eng
uncontrolled
Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematics of Telecommunication
https://opus4.kobv.de/opus4-zib/files/4409/ZR-13-77_01MultibandRobustOptimizationGOR2013.pdf
5640
2015
eng
reportzib
0
2015-10-27
2015-10-27
--
Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores
This paper describes how we solved 12 previously unsolved mixed-integer program-
ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we
used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP
computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper
we describe the basic parallelization mechanism of ParaSCIP, improvements of the
dynamic load balancing and novel techniques to exploit the power of parallelization
for MIP solving. We give a detailed overview of computing times and statistics for
solving open MIPLIB instances.
1438-0064
urn:nbn:de:0297-zib-56404
10.1109/IPDPS.2016.56
Appeared in: Proc. of 30th IEEE International Parallel & Distributed Processing Symposium
Yuji Shinano
Yuji Shinano
Tobias Achterberg
Timo Berthold
Stefan Heinz
Thorsten Koch
Michael Winkler
ZIB-Report
15-53
eng
uncontrolled
Mixed Integer Programming
eng
uncontrolled
Parallel processing
eng
uncontrolled
Node merging
eng
uncontrolled
Racing ParaSCIP
eng
uncontrolled
Ubiquity Generator Framework
eng
uncontrolled
MIPLIB
Software
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Achterberg, Tobias
Koch, Thorsten
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53.pdf
https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53-rev.pdf
4259
eng
reportzib
0
2013-09-27
2013-09-27
--
FiberSCIP - A shared memory parallelization of SCIP
Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.
1438-0064
urn:nbn:de:0297-zib-42595
10.1287/ijoc.2017.0762
INFORMS Journal on Computing
Yuji Shinano
Yuji Shinano
Stefan Heinz
Stefan Vigerske
Michael Winkler
ZIB-Report
13-55
eng
uncontrolled
parallel
eng
uncontrolled
branch-and-bound
eng
uncontrolled
deterministic parallelism
eng
uncontrolled
constraint integer programming
eng
uncontrolled
mixed integer programming
eng
uncontrolled
mixed integer nonlinear programming
eng
uncontrolled
SCIP
eng
uncontrolled
MIP
eng
uncontrolled
MINLP
Software
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Mathematical Optimization Methods
Heinz, Stefan
Shinano, Yuji
Vigerske, Stefan
Winkler, Michael
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib.pdf
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev.pdf
https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev3.pdf
6554
eng
reportzib
0
--
2017-07-11
--
The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound
Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.
1438-0064
urn:nbn:de:0297-zib-65545
Yuji Shinano
Yuji Shinano
ZIB-Report
17-60
eng
uncontrolled
Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack
Software
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6554/ZIB-Report-17-60.pdf
4218
eng
reportzib
0
2013-08-26
2013-08-26
--
Swendsen-Wang Multi-Cluster Algorithm for the 2D/3D Ising Model on Xeon Phi and GPU
Simulations of the critical Ising model by means of local update algorithms suffer from critical slowing down. One way to partially compensate for the influence of this phenomenon on the runtime of simulations is using increasingly faster and parallel computer hardware. Another approach is using algorithms that do not suffer
from critical slowing down, such as cluster algorithms. This paper reports on the Swendsen-Wang multi-cluster algorithm on Intel Xeon Phi coprocessor 5110P, Nvidia Tesla M2090 GPU, and x86
multi-core CPU. We present shared memory versions of the said algorithm for the simulation of the two- and three-dimensional Ising model. We use a combination of local cluster search and global label reduction by means of atomic hardware primitives. Further, we
describe an MPI version of the algorithm on Xeon Phi and CPU, respectively. Significant performance improvements over known im
plementations of the Swendsen-Wang algorithm are demonstrated.
1438-0064
urn:nbn:de:0297-zib-42187
10.1145/2503210.2503254
Appeared in: Proceeding SC '13 Proceedings of SC13: International Conference for High Performance Computing, Networking, Storage and Analysis Article No. 83 ACM New York, NY, USA, 2013
yes
Florian Wende
Florian Wende
Thomas Steinke
ZIB-Report
13-44
eng
uncontrolled
Swendsen-Wang Multi-Cluster Algorithm
eng
uncontrolled
Ising Model
eng
uncontrolled
Xeon Phi
eng
uncontrolled
GPGPU
eng
uncontrolled
Connected Component Labeling
Hardware
Computer Applications
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
STATISTICAL MECHANICS, STRUCTURE OF MATTER
Distributed Algorithms and Supercomputing
Steinke, Thomas
Wende, Florian
no-project
https://opus4.kobv.de/opus4-zib/files/4218/wende_steinke.pdf
1513
eng
reportzib
0
2012-04-19
2012-04-19
--
Probabilistic alternatives for competitive analysis
In the last 20 years competitive analysis has become the main tool for
analyzing the quality of online algorithms. Despite of this,
competitive analysis has also been criticized: It sometimes cannot
discriminate between algorithms that exhibit significantly different
empirical behavior, or it even favors an algorithm that is worse from
an empirical point of view. Therefore, there have been several
approaches to circumvent these drawbacks. In this survey, we discuss
probabilistic alternatives for competitive analysis.
1438-0064
urn:nbn:de:0297-zib-15131
10.1007/s00450-011-0149-1
Appeared In: Computer Science - Research and Development August 2012, Volume 27, Issue 3, pp 189-196
Benjamin Hiller
Benjamin Hiller
Tjark Vredeveld
ZIB-Report
11-55
eng
uncontrolled
online algorithms
eng
uncontrolled
probabilistic analysis
eng
uncontrolled
competitive analysis
eng
uncontrolled
survey
Mathematics of Computing
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
https://opus4.kobv.de/opus4-zib/files/1513/ZR-11-55.pdf
4237
eng
75
masterthesis
0
2013-09-07
2013-09-07
2013-02-04
Approximate Algorithms for Distributed Systems
Peer-to-peer (P2P) systems form a special class of distributed systems. Typically, nodes in a P2P system are flat and share the same responsabilities. In this thesis we focus on three problems that occur in P2P systems: the storage of data replicates, quantile computation on distributed data streams, and churn rate estimation. Data replication is one of the oldest techniques to maintain stored data in a P2P system and to reply to read requests. Applications, which use data replication are distributed databases. They are part of an abstract overlay network and do not see the underlying network topology. The question is how to place a set of data replicates in a distributed system such that response times and failure probabilities become minimal without a priori knowledge of the topology of the underlying hardware nodes? We show how to utilize an agglomerative clustering procedure to reach this goal. State-of-the-art algorithms for aggregation of distributed data or data streams require at some point synchronization, or merge data aggregates hierarchically, which does not accompany the basic principle of P2P systems. We test whether randomized communication and merging of data aggregates are able to produce the same results. These data aggregates serve for quantile queries. Constituting and maintaining a P2P overlay network requires frequent message passing. It is a goal to minimize the number of maintenance messages since they consume bandwidth which might be missing for other applications. The lower bound of the frequency for mainte- nance messages is highly dependent on the churn rate of peers. We show how to estimate the mean lifetime of peers and to reduce the frequency for maintenance messages without destabilizing the infrastructure of the constituting overlay.
urn:nbn:de:0297-zib-42370
Thorsten Schütt
Marie Hoffmann
Marie Hoffmann
Katinka Wolter
eng
uncontrolled
peer-to-peer, machine learning, approximate, clustering, quantile, linear regression
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Studienabschlussarbeiten
Distributed Algorithms and Supercomputing
2008-Scalaris
Zuse Institute Berlin (ZIB)
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/4237/MastersThesis_Hoffmann.pdf
https://opus4.kobv.de/opus4-zib/files/4237/MastersThesis_Presentation_Hoffmann.pdf
4228
deu
87
masterthesis
0
2013-09-03
2013-09-03
2013-01-04
Snapshots in Scalaris
Eines der größten Hindernisse beim praktischen Einsatz von Scalaris, einer skalierbaren Implementierung einer verteilten Hashtabelle mit Unterstützung für Transaktionen, ist das Fehlen eines Verfahrens zur Aufnahme eines konsistenten Zustandes des gesamten Systems. Wir stellen in dieser Arbeit ein einfaches Protokoll vor, dass diese Aufgabe erfüllt und sich, auf Grund der von uns gewählten Herangehensweise, leicht implementieren lässt.
Als Ausgangspunkt dafür wählen wir aus einer Reihe von „klassischen“ Snapshot-Algorithmen ein 1993 von Mattern entworfenes Verfahren, welches auf dem Algorithmus von Lai und Yang basiert, aus. Diese Entscheidung basiert auf einer gründlichen Analyse der Protokolle unter Berücksichtigung der Architektur der existierenden Software.
Im nächsten Arbeitsschritt benutzen wir unser vollständiges Wissen über die Interna des Transaktionssystems von Scalaris und vereinfachen damit das Verfahren hinsichtlich Benutzbarkeit und Implementierungskomplexität, ohne die Anforderungen an den aufgenommenen Zustand aufzuweichen. Statt einer losen Anhäufung lokaler Zustände der einzelnen Teilnehmerknoten können wir am Ende eine große Schlüssel-Wert-Tabelle als Ergebnis erzeugen, die konsistent ist, sich leicht weiterverarbeiten lässt und die einem Zustand entspricht, in dem sich das System einmal befunden haben könnte.
Nachdem wir das Verfahren dann in Software umgesetzt haben, werten wir die Ergebnisse hinsichtlich des Einflusses auf die Performanz des Gesamtsystems aus und diskutieren mögliche Weiterentwicklungen.
urn:nbn:de:0297-zib-42282
Alexander Reinefeld
Stefan Keidel
Stefan Keidel
Florian Schintke
eng
uncontrolled
scalaris
eng
uncontrolled
dht
eng
uncontrolled
algorithm
Computer Systems Organization
Software
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Studienabschlussarbeiten
Distributed Algorithms and Supercomputing
2008-Scalaris
Zuse Institute Berlin (ZIB)
Humboldt-Universität zu Berlin
https://opus4.kobv.de/opus4-zib/files/4228/08-03_diplomarbeit_skeidel.pdf
6164
2016
eng
reportzib
0
--
2016-12-28
--
Piecewise linear secant approximation via Algorithmic Piecewise Differentiation
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.
1438-0064
urn:nbn:de:0297-zib-61642
10.1080/10556788.2017.1387256
published at Optimization Methods and Software
Andreas Griewank
Tom Streubel
Tom Streubel
Lutz Lehmann
Richard Hasenfelder
Manuel Radons
ZIB-Report
16-54
eng
uncontrolled
Automatic differentiation
eng
uncontrolled
Computational graph
eng
uncontrolled
Lipschitz continuity
eng
uncontrolled
Generalized Hermite interpolation
eng
uncontrolled
ADOL-C
Mathematics of Computing
NUMERICAL ANALYSIS
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Mathematical Optimization
MODAL-GasLab
Streubel, Tom
Energy Network Optimization
https://opus4.kobv.de/opus4-zib/files/6164/newton_secant_approx_paper.pdf
6226
eng
reportzib
0
--
2017-03-20
--
Design, concepts, and state of the art of the swMATH service
In this paper, the concepts and design for an efficient information service for mathematical software and further mathematical research data are presented. The publication-based approach and the Web-based approach are the main building blocks of the service and will be discussed. Heuristic methods are used for identification, extraction, and ranking of information about software and other mathematical research data. The methods provide not only information about the research data but also link software and mathematical research data to the scientific context.
1438-0064
urn:nbn:de:0297-zib-62263
Hagen Chrapary
Wolfgang Dalitz
Wolfgang Dalitz
Winfried Neun
Wolfram Sperber
ZIB-Report
17-11
eng
uncontrolled
software information, software citation, mathematical research data
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Scientific Information
Dalitz, Wolfgang
MODAL-SynLab
Chrapary, Hagen
https://opus4.kobv.de/opus4-zib/files/6226/aca_final-zib.pdf
4189
2013
eng
reportzib
0
2013-07-30
2013-07-30
--
Fast Generation of Virtual X-ray Images from Deformable Tetrahedral Meshes
We propose a novel GPU-based approach to render virtual X-ray projections of deformable tetrahedral meshes. These meshes represent the shape and the internal density distribution of a particular anatomical structure and are derived from statistical shape and intensity models (SSIMs). We apply our method to improve the geometric reconstruction of 3D anatomy (e.g.\ pelvic bone) from 2D X-ray images. For that purpose, shape and density of a tetrahedral mesh are varied and virtual X-ray projections are generated within an optimization process until the similarity between the computed virtual X-ray and the respective anatomy depicted in a given clinical X-ray is maximized. The OpenGL implementation presented in this work deforms and projects tetrahedral meshes of high resolution (200.000+ tetrahedra) at interactive rates. It generates virtual X-rays that accurately depict the density distribution of an anatomy of interest. Compared to existing methods that accumulate X-ray attenuation in deformable meshes, our novel approach significantly boosts the deformation/projection performance. The proposed projection algorithm scales better with respect to mesh resolution and complexity of the density distribution, and the combined deformation and projection on the GPU scales better with respect to the number of deformation parameters. The gain in performance allows for a larger number of cycles in the optimization process. Consequently, it reduces the risk of being stuck in a local optimum. We believe that our approach contributes in orthopedic surgery, where 3D anatomy information needs to be extracted from 2D X-rays to support surgeons in better planning joint replacements.
1438-0064
urn:nbn:de:0297-zib-41896
no
appeared in IEEE Transactions on Visualization and Computer Graphics
Moritz Ehlke
Moritz Ehlke
Heiko Ramm
Hans Lamecker
Hans-Christian Hege
Stefan Zachow
ZIB-Report
13-38
eng
uncontrolled
digitally reconstructed radiographs
eng
uncontrolled
volume rendering
eng
uncontrolled
mesh deformation
eng
uncontrolled
statistical shape and intensity models
eng
uncontrolled
image registration
eng
uncontrolled
GPU acceleration
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Visual Data Analysis
Visual Data Analysis in Science and Engineering
Therapy Planning
Ehlke, Moritz
Hege, Hans-Christian
Lamecker, Hans
Zachow, Stefan
BSRT-3DFromXray
https://opus4.kobv.de/opus4-zib/files/4189/Report-13-38.pdf
4301
deu
reportzib
0
2013-11-04
2013-11-04
--
Vorschrift oder Thunfisch? – Zur Langzeitverfügbarkeit von Forschungsdaten
„Ich mache ihm ein Angebot, das er nicht ablehnen kann.” Diese Aussage aus einem gänzlich anderen Kontext lässt sich recht treffend übertragen als Wunsch von Dienstleistern und Zweck von Dienstleistungen für Datenproduzenten im Forschungsdatenmanagement. Zwar wirkt Druck zur Datenübergabe nicht förderlich, die Eröffnung einer Option aber sehr wohl. Im vorliegenden Artikel geht es um das Verständnis der Nachhaltigkeit von Forschung und ihren Daten anhand der Erkenntnisse und Erfahrungen aus der ersten Phase des DFG-Projekts EWIG. [Fn 01] Eine Auswahl von Fallstricken beim Forschungsdatenmanagement wird anhand der Erkenntnisse aus Expertengesprächen und eigenen Erfahrungen beim Aufbau von LZA-Workflows vorgestellt. Erste Konzepte in EWIG zur Datenübertragung aus unterschiedlich strukturierten Datenquellen in die „Langfristige Domäne” werden beschrieben.
"I'm gonna make him an offer he can't refuse". This quote from a completely different context can be aptly rendered as a statement of service providers as well as the purpose of services for data producers in the field of research data management. Although pressure is not the leverage of choice if you want researchers to deposit their research data in some kind of repository, offering an option does the trick quite well. In this article we present some of the concepts for sustainability of research and its data from the first phase the of the project EWIG, funded by the Deutsche Forschungsgemeinschaft. A selection of pitfalls in research data management is presented based on the findings from expert interviews and our own experiences in the construction of LTP workflows. First concepts in EWIG to transfer data from differently structured data sources into the "Permanent Domain" are described.
1438-0064
http://libreas.eu/ausgabe23/08hasler/
urn:nbn:de:0297-zib-43010
Ersch. in: Tim Hasler, Wolfgang Peters-Kottig: "Vorschrift oder Thunfisch? – Zur Langzeitverfügbarkeit von Forschungsdaten". LIBREAS. Library Ideas, 23 (2013)
Tim Hasler
Wolfgang Peters-Kottig
Wolfgang Peters-Kottig
ZIB-Report
13-70
deu
uncontrolled
Langzeitverfügbarkeit
deu
uncontrolled
Forschungsdatenmanagement
Information Systems
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Scientific Information
Peters-Kottig, Wolfgang
https://opus4.kobv.de/opus4-zib/files/4301/Hasler-PetersKottig_ZIB-Report 13-70.pdf
6632
eng
1600
1629
4
6
article
0
--
2018-01-04
--
Random forward models and log-likelihoods in Bayesian inverse problems
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.
SIAM/ASA Journal on Uncertainty Quantification
1438-0064
urn:nbn:de:0297-zib-66324
1712.05717
10.1137/18M1166523
2018
yes
Han Cheng Lie
Tim Sullivan
T. J. Sullivan
Aretha Teckentrup
ZIB-Report
18-03
eng
uncontrolled
Bayesian inverse problem
eng
uncontrolled
random likelihood
eng
uncontrolled
surrogate model
eng
uncontrolled
posterior consistency
eng
uncontrolled
probabilistic numerics
eng
uncontrolled
uncertainty quantification
eng
uncontrolled
randomised misfit
STATISTICS
NUMERICAL ANALYSIS
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Numerical Mathematics
Sullivan, Tim
SFB1114 A06
https://opus4.kobv.de/opus4-zib/files/6632/random-bip.pdf
4315
2013
2013
eng
reportzib
0
2013-11-29
--
--
The Filament Editor: An Interactive Software Environment for Visualization, Proof-Editing and Analysis of 3D Neuron Morphology
Neuroanatomical analysis, such as classification of cell types, depends on reliable reconstruction of large numbers of complete 3D dendrite and axon morphologies. At present, the majority of neuron reconstructions are obtained from preparations in a single tissue slice in vitro, thus suffering from cut off dendrites and, more dramatically, cut off axons. In general, axons can innervate volumes of several cubic millimeters and may reach path lengths of tens of centimeters. Thus, their complete reconstruction requires in vivo labeling, histological sectioning and imaging of large fields of view. Unfortunately, anisotropic background conditions across such large tissue volumes, as well as faintly labeled thin neurites, result in incomplete or erroneous automated tracings and even lead experts to make annotation errors during manual reconstructions. Consequently, tracing reliability renders the major bottleneck for reconstructing complete 3D neuron morphologies. Here, we present a novel set of tools, integrated into a software environment named ‘Filament Editor’, for creating reliable neuron tracings from sparsely labeled in vivo datasets. The Filament Editor allows for simultaneous visualization of complex neuronal tracings and image data in a 3D viewer, proof-editing of neuronal tracings, alignment and interconnection across sections, and morphometric analysis in relation to 3D anatomical reference structures. We illustrate the functionality of the Filament Editor on the example of in vivo labeled axons and demonstrate that for the exemplary dataset the final tracing results after proof-editing are independent of the expertise of the human operator.
1438-0064
urn:nbn:de:0297-zib-43157
10.1007/s12021-013-9213-2
Neuroinformatics 12(2), pp 325-339, 2014
no
Vincent J. Dercksen
Vincent Dercksen
Hans-Christian Hege
Marcel Oberlaender
ZIB-Report
13-75
Software
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Visual Data Analysis
Visual Data Analysis in Science and Engineering
Hege, Hans-Christian
Neuro
https://opus4.kobv.de/opus4-zib/files/4315/ZR-13-75.pdf
7059
eng
reportzib
1
--
2018-09-27
--
Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.
1438-0064
urn:nbn:de:0297-zib-70591
Satoshi Ito
Yuji Shinano
Yuji Shinano
ZIB-Report
18-51
eng
uncontrolled
Sports league
eng
uncontrolled
Round-robin tournament
eng
uncontrolled
Tiebreaking criteria
eng
uncontrolled
Clinch number
eng
uncontrolled
Elimination number
eng
uncontrolled
Combinatorial optimization
eng
uncontrolled
Integer programming
Computing Methodologies
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/7059/ZIB-Report-18-51.pdf
5967
eng
reportzib
0
--
2016-06-15
--
NBLAST: Rapid, sensitive comparison of neuronal structure and construction of neuron family databases
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.
1438-0064
urn:nbn:de:0297-zib-59672
10.1016/j.neuron.2016.06.012
appeared also as bioRxiv preprint http://dx.doi.org/10.1101/006346 and in revised form in Neuron
Marta Costa
Steffen Prohaska
James D. Manton
Aaron D. Ostrovsky
Steffen Prohaska
Gregory S. X. E. Jefferis
ZIB-Report
16-34
eng
uncontrolled
neuroinformatics
eng
uncontrolled
NBLAST
eng
uncontrolled
neuron similarity
eng
uncontrolled
cell type
eng
uncontrolled
clustering
Computer Applications
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
BIOLOGY AND OTHER NATURAL SCIENCES
Visual Data Analysis
Prohaska, Steffen
no-project
https://opus4.kobv.de/opus4-zib/files/5967/zibreport-16-34_v1.pdf
7111
eng
reportzib
0
--
2018-12-07
--
Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores
SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.
1438-0064
urn:nbn:de:0297-zib-71118
Yuji Shinano
Yuji Shinano
Daniel Rehfeldt
Thorsten Koch
ZIB-Report
18-58
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Koch, Thorsten
Rehfeldt, Daniel
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58.pdf
https://opus4.kobv.de/opus4-zib/files/7111/ZIB-Report-18-58-rev.pdf