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
Document Type
- ZIB-Report (46)
- Master's Thesis (6)
- Software (4)
- Article (1)
- Bachelor's Thesis (1)
Keywords
- Ubiquity Generator Framework (3)
- Computational Diagnosis (2)
- Convex Optimization (2)
- Discrete optimization (2)
- Knee Osteoarthritis (2)
- Lattice problem (2)
- Lattice-based cryptography (2)
- MSM (2)
- Machine Learning (2)
- Parallel algorithms (2)
- Reversible Markov Chain (2)
- Shortest vector problem (2)
- branch-and-bound parallelization (2)
- integer optimization (2)
- parallelization framework (2)
- 2-photon microscopy (1)
- ADOL-C (1)
- Adaptive Importance Sampling (1)
- Automatic differentiation (1)
- Bayesian inverse problem (1)
- Branch and Bound (1)
- Branchwidth (1)
- Carvingwidth (1)
- Classification (1)
- Clinch number (1)
- Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design (1)
- Combinatorial optimization (1)
- Computational graph (1)
- Connected Component Labeling (1)
- DVR (1)
- Data Mining (1)
- Data Uncertainty (1)
- Dynamic Traffic (1)
- Elimination number (1)
- Forschungsdatenmanagement (1)
- GPGPU (1)
- GPU acceleration (1)
- Gaussian mixture model (1)
- Generalized Hermite interpolation (1)
- Girsanov (1)
- Harvest Scheduling (1)
- Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation (1)
- Integer programming (1)
- Ising Model (1)
- Langzeitverfügbarkeit (1)
- Lipschitz continuity (1)
- MINLP (1)
- MIP (1)
- MIPLIB (1)
- Metadynamics (1)
- Metastability (1)
- Mixed Integer Programming (1)
- Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB (1)
- Molecular Dynamics (1)
- Monte Carlo methods for light transport (1)
- Multiband Robustness (1)
- Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics (1)
- NBLAST (1)
- Network Design (1)
- Network Design, Demand Uncertainty, Robust Optimization, Telecommunications (1)
- Node merging (1)
- Non Equilibrium Sampling (1)
- Optical access networks (1)
- Optimization (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- Parallel Branch-and-Bound (1)
- Parallel processing (1)
- Parallelization, Branch-and-bound, Mixed Integer Programming, UG, ParaSCIP, FiberSCIP, ParaXpress, FiberXpress, SCIP-Jack (1)
- Parameterized complexity (1)
- Periodic Event Scheduling Problem (1)
- Periodic timetabling (1)
- QAP (1)
- Racing ParaSCIP (1)
- Robust Optimization (1)
- Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design (1)
- Round-robin tournament (1)
- SCIP (1)
- Scheduling, Extended Formulations, Network Migration, WDM Networks (1)
- Sports league (1)
- Steiner trees (1)
- Swendsen-Wang Multi-Cluster Algorithm (1)
- Telecommunication (1)
- Tiebreaking criteria (1)
- Time Series (1)
- Treewidth (1)
- Variance Reduction (1)
- Xeon Phi (1)
- acyclic orientations (1)
- algorithm (1)
- bipolar orientations (1)
- boundary conditions (1)
- brain wiring (1)
- branch-and-bound (1)
- cell type (1)
- chromophore concentration (1)
- clustering (1)
- competitive analysis (1)
- constraint integer programming (1)
- coordinate search (1)
- deterministic parallelism (1)
- dht (1)
- digitally reconstructed radiographs (1)
- direct volume rendering (1)
- electron tomography (1)
- enumeration algorithm (1)
- filopodia (1)
- geometric morphometrics (1)
- geometric statistics (1)
- geometry reconstruction (1)
- growth cone dynamics (1)
- image analysis (1)
- image and geometry alignment (1)
- image registration (1)
- importance sampling (1)
- level of detail (1)
- mesh deformation (1)
- metadynamics (1)
- metastability (1)
- microtubules (1)
- mixed integer nonlinear programming (1)
- mixed integer programming (1)
- model (1)
- model-based inversion (1)
- multiple sources and sinks (1)
- natural scene (1)
- neural networks (1)
- neuroinformatics (1)
- neuron similarity (1)
- online algorithms (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- oxygen saturation (1)
- parallel (1)
- peer-to-peer, machine learning, approximate, clustering, quantile, linear regression (1)
- photoacoustic imaging (1)
- picking (1)
- point correspondence (1)
- pointing (1)
- posterior consistency (1)
- probabilistic analysis (1)
- probabilistic numerics (1)
- quantitative photoacoustic tomography (1)
- random likelihood (1)
- randomised misfit (1)
- rare event simulation (1)
- rendering (1)
- scalaris (1)
- serial sectioning (1)
- shape analysis (1)
- software information, software citation, mathematical research data (1)
- statistical shape and intensity models (1)
- stochastic optimal control (1)
- surrogate model (1)
- survey (1)
- uncertainty quantification (1)
- unfolding, papyri, computed tomography (1)
- volume rendering (1)
Institute
- Mathematical Optimization (23)
- Visual and Data-centric Computing (14)
- Visual Data Analysis (11)
- Applied Algorithmic Intelligence Methods (7)
- Mathematics of Telecommunication (7)
- Numerical Mathematics (5)
- Distributed Algorithms and Supercomputing (4)
- Mathematical Optimization Methods (3)
- Computational Molecular Design (2)
- Digital Data and Information for Society, Science, and Culture (2)
Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
(2018)
The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.
SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.
In this paper, the concepts and design for an efficient information service for mathematical software and further mathematical research data are presented. The publication-based approach and the Web-based approach are the main building blocks of the service and will be discussed. Heuristic methods are used for identification, extraction, and ranking of information about software and other mathematical research data. The methods provide not only information about the research data but also link software and mathematical research data to the scientific context.
The goal of quantitative photoacoustic tomography (qPAT) is to recover maps of the chromophore distributions from multiwavelength images of the initial pressure. Model-based inversions that incorporate the physical processes underlying the photoacoustic (PA) signal generation represent a promising approach. Monte-Carlo models of the light transport are computationally expensive, but provide accurate fluence distributions predictions, especially in the ballistic and quasi-ballistic regimes. Here, we focus on the inverse problem of 3D qPAT of blood oxygenation and investigate the application of the Monte-Carlo method in a model-based inversion scheme. A forward model of the light transport based on the MCX simulator and acoustic propagation modeled by the k-Wave toolbox was used to generate a PA image data set acquired in a tissue phantom over a planar detection geometry. The combination of the optical and acoustic models is shown to account for limited-view artifacts. In addition, the errors in the fluence due to, for example, partial volume artifacts and absorbers immediately adjacent to the region of interest are investigated. To accomplish large-scale inversions in 3D, the number of degrees of freedom is reduced by applying image segmentation to the initial pressure distribution to extract a limited number of regions with homogeneous optical parameters. The absorber concentration in the tissue phantom was estimated using a coordinate descent parameter search based on the comparison between measured and modeled PA spectra. The estimated relative concentrations using this approach lie within 5 % compared to the known concentrations. Finally, we discuss the feasibility of this approach to recover the blood oxygenation from experimental data.
An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates
(2017)
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.
Ancient Egyptian papyri are often folded, rolled up or kept as small packages, sometimes even sealed. Physically unrolling or unfolding these packages might severely damage them. We demonstrate a way to get access to the hidden script without physical unfolding by employing computed tomography and mathematical algorithms for virtual unrolling and unfolding. Our algorithmic approaches are combined with manual interaction. This provides the necessary flexibility to enable the unfolding of even complicated and partly damaged papyrus packages. In addition, it allows us to cope with challenges posed by the structure of ancient papyrus, which is rather irregular, compared to other writing substrates like metallic foils or parchment. Unfolding of packages is done in two stages. In the first stage, we virtually invert the physical folding process step by step until the partially unfolded package is topologically equivalent to a scroll or a papyrus sheet folded only along one fold line. To minimize distortions at this stage, we apply the method of moving least squares. In the second stage, the papyrus is simply flattened, which requires the definition of a medial surface. We have applied our software framework to several papyri. In this work, we present the results of applying our approaches to mockup papyri that were either rolled or folded along perpendicular fold lines. In the case of the folded papyrus, our approach represents the first attempt to address the unfolding of such complicated folds.
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.
PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.
Neural circuit mapping is generating datasets of 10,000s of labeled neurons. New computational tools are needed to search and organize these data. We present NBLAST, a sensitive and rapid algorithm, for measuring pairwise neuronal similarity. NBLAST considers both position and local geometry, decomposing neurons into short segments; matched segments are scored using a probabilistic scoring matrix defined by statistics of matches and non-matches.
We validated NBLAST on a published dataset of 16,129 single Drosophila neurons. NBLAST can distinguish neuronal types down to the finest level (single identified neurons) without a priori information. Cluster analysis of extensively studied neuronal classes identified new types and unreported topographical features. Fully automated clustering organized the validation dataset into 1052 clusters, many of which map onto previously described neuronal types. NBLAST supports additional query types including searching neurons against transgene expression patterns. Finally we show that NBLAST is effective with data from other invertebrates and zebrafish.
It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x − x̌|| ||x − x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton’s method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods.