TY - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores N2 - 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. T3 - ZIB-Report - 15-53 KW - Mixed Integer Programming KW - Parallel processing KW - Node merging KW - Racing ParaSCIP KW - Ubiquity Generator Framework KW - MIPLIB Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56404 SN - 1438-0064 ER - TY - JOUR A1 - Nielsen, Adam A1 - Weber, Marcus T1 - Computing the nearest reversible Markov chain JF - Numerical Linear Algebra with Applications N2 - 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. KW - Reversible Markov Chain KW - Convex Optimization KW - MSM Y1 - 2015 U6 - https://doi.org/10.1002/nla.1967 VL - 22 IS - 3 SP - 483 EP - 499 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 - 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 -