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)
Consolidation of commodities and coordination of vehicle routes are fundamental features of supply chain management problems. While locations for consolidation and coordination are typically known a priori, in adaptive transportation networks this is not the case. The identification of such consolidation locations forms part of the decision making process. Supply chain management problems integrating the designation of consolidation locations with the coordination of long haul and local vehicle routing is not only challenging to solve, but also very difficult to formulate mathematically. In this paper, the first mathematical model integrating location clustering with long haul and local vehicle routing is proposed. This mathematical formulation is used to develop algorithms to find high quality solutions. A novel parallel framework is developed that combines exact and heuristic methods to improve the search for high quality solutions and provide valid bounds. The results demonstrate that using exact methods to guide heuristic search is an effective approach to find high quality solutions for difficult supply chain management problems.
The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.
Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult.
大規模二次割当問題への挑戦
(2022)
Estimating 3D Shape of the Head Skeleton of Basking Sharks Using Annotated Landmarks on a 2D Image
(2022)
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.
Morphomatics is an open-source Python library for (statistical) shape analysis developed within the geometric data analysis and processing research group at Zuse Institute Berlin. It contains prototype implementations of intrinsic manifold-based methods that are highly consistent and avoid the influence of unwanted effects such as bias due to arbitrary choices of coordinates.
We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method efficiently implemented on a powerful computer system using the Ubiquity Generator(UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors’ group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results.
Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the first time.
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.
This work presents a fully automated pipeline, centered around a deep neural network, as well as a method to train that network in an efficient manner, that enables accurate detection of lesions in meniscal anatomical subregions. The network architecture is based on a transformer encoder/decoder. It is trained on DESS and tuned on IW TSE 3D MRI scans sourced from the Osteoarthritis Initiative. Furthermore, it is trained in a multilabel, and multitask fashion, using an auxiliary detection head. The former enables implicit localisation
of meniscal defects, that to the best of my knowledge, has not yet been reported elsewhere. The latter enables efficient learning on the entire 3D MRI volume. Thus, the proposed method does not require any expert knowledge at inference. Aggregated inference results from two datasets resulted in an overall AUCROC result of 0.90, 0.91 and 0.93 for meniscal lesion detection anywhere in the knee, in medial and in lateral menisci respectively. These results compare very well to the related work, even though only a fraction of the data has been utilized. Clinical applicability and benefit is yet to be determined.
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.
For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments.
Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.
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.
In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.
Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved 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.
Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib.
Following axon pathfinding, growth cones transition from stochastic filopodial exploration to the formation of a limited number of synapses. How the interplay of filopodia and synapse assembly ensures robust connectivity in the brain has remained a challenging problem. Here, we developed a new 4D analysis method for filopodial dynamics and a data-driven computational model of synapse formation for R7 photoreceptor axons in developing Drosophila brains. Our live data support a 'serial synapse formation' model, where at any time point only a single 'synaptogenic' filopodium suppresses the synaptic competence of other filopodia through competition for synaptic seeding factors. Loss of the synaptic seeding factors Syd-1 and Liprin-α leads to a loss of this suppression, filopodial destabilization and reduced synapse formation, which is sufficient to cause the destabilization of entire axon terminals. Our model provides a filopodial 'winner-takes-all' mechanism that ensures the formation of an appropriate number of synapses.
We consider the use of randomised forward models and log-likelihoods within the Bayesian approach to inverse problems. Such random approximations to the exact forward model or log-likelihood arise naturally when a computationally expensive model is approximated using a cheaper stochastic surrogate, as in Gaussian process emulation (kriging), or in the field of probabilistic numerical methods. We show that the Hellinger distance between the exact and approximate Bayesian posteriors is bounded by moments of the difference between the true and approximate log-likelihoods. Example applications of these stability results are given for randomised misfit models in large data applications and the probabilistic solution of ordinary differential equations.