## 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)

### Refine

#### Year of publication

- 2015 (4) (remove)

#### Document Type

- ZIB-Report (3)
- Article (1)

#### Keywords

- Branch and Bound (1)
- Classification (1)
- Convex Optimization (1)
- Data Mining (1)
- Dynamic Traffic (1)
- MIPLIB (1)
- MSM (1)
- Mixed Integer Programming (1)
- Network Design (1)
- Node merging (1)

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.

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.

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.

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.