TY - GEN
A1 - Büsing, Christina
A1 - D'Andreagiovanni, Fabio
A1 - Raymond, Annie
T1 - 0-1 Multiband Robust Optimization
N2 - 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.
T3 - ZIB-Report - 13-77
KW - Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44093
SN - 1438-0064
ER -
TY - GEN
A1 - D'Andreagiovanni, Fabio
A1 - Krolikowski, Jonatan
A1 - Pulaj, Jonad
T1 - A hybrid primal heuristic for Robust Multiperiod Network Design
N2 - 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.
T3 - ZIB-Report - 13-78
KW - Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44081
SN - 1438-0064
ER -
TY - GEN
A1 - Büsing, Christina
A1 - D'Andreagiovanni, Fabio
T1 - A new theoretical framework for Robust Optimization under multi-band uncertainty
N2 - 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.
T3 - ZIB-Report - 13-61
KW - Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42644
UR - http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6
SN - 1438-0064
ER -
TY - GEN
A1 - Wolf, Thomas
T1 - A Study of Genetic Algorithms solving a combinatorial Puzzle
N2 - 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.
T3 - ZIB-Report - SC-98-01
Y1 - 1998
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3445
ER -
TY - GEN
A1 - Pfeuffer, Frank
A1 - Werner, Axel
T1 - Adaptive telecommunication network operation with a limited number of reconfigurations
N2 - 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.
T3 - ZIB-Report - 15-36
KW - Telecommunication
KW - Network Design
KW - Dynamic Traffic
KW - Branch and Bound
Y1 - 2015
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55547
SN - 1438-0064
ER -
TY - GEN
A1 - Quer, Jannes
A1 - Donati, Luca
A1 - Keller, Bettina
A1 - Weber, Marcus
T1 - An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates
N2 - 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.
T3 - ZIB-Report - 17-09
KW - Adaptive Importance Sampling
KW - Molecular Dynamics
KW - Metastability
KW - Variance Reduction
KW - Non Equilibrium Sampling
KW - Metadynamics
KW - Girsanov
Y1 - 2017
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62075
SN - 1438-0064
ER -
TY - THES
A1 - Hoffmann, Marie
T1 - Approximate Algorithms for Distributed Systems
N2 - 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.
KW - peer-to-peer, machine learning, approximate, clustering, quantile, linear regression
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42370
ER -
TY - GEN
A1 - Weber, Britta
A1 - Tranfield, Erin M.
A1 - Höög, Johanna L.
A1 - Baum, Daniel
A1 - Antony, Claude
A1 - Hyman, Tony
A1 - Verbavatz, Jean-Marc
A1 - Prohaska, Steffen
T1 - Automated stitching of microtubule centerlines across serial electron tomograms
N2 - 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.
T3 - ZIB-Report - 14-41
KW - electron tomography
KW - microtubules
KW - serial sectioning
KW - image analysis
KW - geometry reconstruction
KW - image and geometry alignment
KW - point correspondence
Y1 - 2014
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52958
SN - 1438-0064
ER -
TY - GEN
A1 - Schäfer, Patrick
T1 - Bag-Of-SFA-Symbols in Vector Space (BOSS VS)
N2 - 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.
T3 - ZIB-Report - 15-30
KW - Time Series
KW - Classification
KW - Data Mining
Y1 - 2015
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54984
SN - 1438-0064
ER -
TY - GEN
A1 - Zakrzewska, Anna
A1 - D'Andreagiovanni, Fabio
A1 - Ruepp, Sarah
A1 - Berger, Michael S.
T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks
N2 - 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.
T3 - ZIB-Report - 13-63
KW - Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42675
UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384
SN - 1438-0064
ER -