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
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
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
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
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
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
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
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
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
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