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 - GEN A1 - Shinano, Yuji T1 - UG - Ubiquity Generator Framework v0.9.1 N2 - UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment. It exploits the powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc. without the need for base solver parallelization. UG framework, ParaSCIP(ug[SCIP,MPI]) and FiberSCIP (ug[SCIP,Pthreads]) are available as a beta version. For MIP solving, ParaSCIP and FiberSCIP are well debugged and should be stable. For MINLP solving, they are relatively stable, but not as thoroughly debugged. This release version should handle branch-and-cut approaches where subproblems are defined by variable bounds and also by constrains for ug[SCIP,*] ParaSCIP and FiberSCIP). Therefore, problem classes other than MIP or MINLP can be handled, but they have not been tested yet. v0.9.1: Update orbitope cip files. KW - parallelization framework KW - branch-and-bound parallelization KW - integer optimization Y1 - 2020 U6 - https://doi.org/10.12752/8508 ER - TY - GEN A1 - Shinano, Yuji T1 - The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound N2 - 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. T3 - ZIB-Report - 17-60 KW - Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65545 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji T1 - UG - Ubiquity Generator Framework v1.0.0beta N2 - UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment. It exploits the powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc. without the need for base solver parallelization. UG framework, ParaSCIP(ug[SCIP,MPI]) and FiberSCIP (ug[SCIP,Pthreads]) are available as a beta version. v1.0.0: new documentation and cmake, generalization of ug framework, implementation of selfsplitrampup for fiber- and parascip, better memory and time limit handling. KW - parallelization framework KW - branch-and-bound parallelization KW - integer optimization Y1 - 2021 U6 - https://doi.org/10.12752/8521 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 - Ribera Borrell, Enric A1 - Quer, Jannes A1 - Richter, Lorenz A1 - Schütte, Christof T1 - Improving control based importance sampling strategies for metastable diffusions via adapted metadynamics N2 - Sampling rare events in metastable dynamical systems is often a computationally expensive task and one needs to resort to enhanced sampling methods such as importance sampling. Since we can formulate the problem of finding optimal importance sampling controls as a stochastic optimization problem, this then brings additional numerical challenges and the convergence of corresponding algorithms might as well suffer from metastabilty. In this article we address this issue by combining systematic control approaches with the heuristic adaptive metadynamics method. Crucially, we approximate the importance sampling control by a neural network, which makes the algorithm in principle feasible for high dimensional applications. We can numerically demonstrate in relevant metastable problems that our algorithm is more effective than previous attempts and that only the combination of the two approaches leads to a satisfying convergence and therefore to an efficient sampling in certain metastable settings. T3 - ZIB-Report - 21-40 KW - importance sampling KW - stochastic optimal control KW - rare event simulation KW - metastability KW - neural networks KW - metadynamics Y1 - 2021 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 - 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 - THES A1 - Paskin, Martha T1 - Estimating 3D Shape of the Head Skeleton of Basking Sharks Using Annotated Landmarks on a 2D Image N2 - Basking sharks are thought to be one of the most efficient filter-feeding fish in terms of the throughput of water filtered through their gills. Details about the underlying morphology of their branchial region have not been studied due to various challenges in acquiring real-world data. The present thesis aims to facilitate this, by developing a mathematical shape model which constructs the 3D structure of the head skeleton of a basking shark using annotated landmarks on a single 2D image. This is an ill-posed problem as estimating the depth of a 3D object from a single 2D view is, in general, not possible. To reduce this ambiguity, we create a set of pre-defined training shapes in 3D from CT scans of basking sharks. First, the damaged structures of the sharks in the scans are corrected via solving a set of optimization problems, before using them as accurate 3D representations of the object. Then, two approaches are employed for the 2D-to-3D shape fitting problem–an Active Shape Model approach and a Kendall’s Shape Space approach. The former represents a shape as a point on a high-dimensional Euclidean space, whereas the latter represents a shape as an equivalence class of points in this Euclidean space. Kendall’s shape space approach is a novel technique that has not yet been applied in this context, and a comprehensive comparison of the two approaches suggests this approach to be superior for the problem at hand. This can be credited to an improved interpolation of the training shapes. N2 - Riesenhaie zählen zu den effizientesten Filtrierern hinsichtlich des durch die Kiemen gefilterten Wasservolumens. Die Kiemenregion dieser Tiere besitzt eine markante Morphologie, die jedoch bisher nicht umfassend erforscht werden konnte, da es schwierig ist, reale Daten dieser Tiere zu erheben. Die vorliegende Arbeit zielt darauf ab, dies durch die Entwicklung eines mathematischen Formmodels zu ermöglichen, das es erlaubt, die 3D-Struktur des Schädelskeletts anhand von Landmarken, die auf einem 2D-Bild platziert werden, zu rekonstruieren. Die hierzu benötigte Tiefenbestimmung der Landmarken aus einer 2D-Projektion ist ein unterbestimmtes Problem. Wir lösen dies durch die Hinzunahme von Trainingsformen, welche wir aus CT-Scans von Riesenhaien gewinnen. Der Zustand der tomografierten Exemplare erfordert jedoch einen vorhergehenden Korrekturschritt, den wir mit Hilfe eines Optimierungsansatzes lösen, bevor die extrahierten Strukturen als 3D-Trainingsformen dienen können. Um die 3D-Struktur des Schädelskelettes aus 2D-Landmarken zu rekonstruieren, vergleichen wir zwei Ansätze – den sogenannten Active-Shape-Model (ASM)-Ansatz und einen Ansatz basierend auf Kendalls Formenraum. Während eine Form des ASM-Ansatzes durch einen Punkt in einem hochdimensionalen Euklidischen Raum repräsentiert ist, repräsentiert eine Form im Kendall-Formenraum eine Äquivalenzklasse von Punkten des Euklidischen Raumes. Die Anwendung des Kendall-Formenraumes für das beschriebene Problem ist neu und ein umfassender Vergleich der Methoden hat ergeben, dass dieser Ansatz für die spezielle Anwendung zu besseren Ergebnissen führt. Wir führen dies auf die überlegene Interpolation der Trainingsformen in diesem Raum zurück. Y1 - 2022 UR - https://arxiv.org/abs/2207.12687 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Werner, Axel A1 - Wessäly, Roland T1 - Estimating trenching costs in FTTx network planning N2 - 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". T3 - ZIB-Report - 11-49 KW - Optical access networks KW - Optimization KW - Steiner trees Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14884 SN - 1438-0064 ER -