Publication Server of Zuse Institute Berlin (ZIB)
Not a member yet
6648 research outputs found
Sort by
A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites
No full textRescheduling a railway system comprises many aspects, such as line planning, timetabling, track allocation, and vehicle scheduling. For periodic timetables, these features can be integrated into a single mixed-integer program extending the Periodic Event Scheduling Problem (PESP) with a routing component. We develop a multi-commodity-flow-based heuristic that allows to compute better solutions faster than a black-box MIP approach on real construction site scenarios on the S-Bahn Berlin network
Quantum Approximate Multi-Objective Optimization
No full textThe goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, i.e., the set of all Pareto optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. In this work, we use low-depth Quantum Approximate Optimization Algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with Matrix Product State numerical simulation, and show its potential to outperform classical approaches
Riemannian denoising diffusion probabilistic models
No full textWe propose Riemannian Denoising Diffusion Probabilistic Models (RDDPMs) for learning distributions on submanifolds of Euclidean space that are level sets of functions, including most of the manifolds relevant to applications. Existing methods for generative modeling on manifolds rely on substantial geometric information such as geodesic curves or eigenfunctions of the Laplace-Beltrami operator and, as a result, they are limited to manifolds where such information is available. In contrast, our method, built on a projection scheme, can be applied to more general manifolds, as it only requires being able to evaluate the value and the first order derivatives of the function that defines the submanifold. We provide a theoretical analysis of our method in the continuous-time limit, which elucidates the connection between our RDDPMs and score-based generative models on manifolds. The capability of our method is demonstrated on datasets from previous studies and on new datasets sampled from two high-dimensional manifolds, i.e. SO(10) and the configuration space of molecular system alanine dipeptide with fixed dihedral angle
Embedding large-scale graph and text-based datasets with LLMs
No full textWe propose an unsupervised classification approach to large-scale text-based datasets using Large Language Models. Large text data sets, such as publications, websites, and other text-based media, inherit two distinct types of features: (1) the text itself, its information conveyed through semantics, and (2) its relationship to other texts through links, references, or shared attributes. While the latter can be described as a graph structure, enabling us to use tools and methods from graph theory as well as conventional classification methods, the former has newly found potential through the usage of LLM embedding models.
Demonstrating these possibilities and their practicability, we investigate the Web of Science dataset, containing ~56 million scientific publications through the lens of our proposed embedding method, revealing a self-structured landscape of texts. Further, we discuss strategies to combine these emerging methods with traditional graph-based approaches, potentially compensating each other's shortcomings
Tree inference with varifold distances
No full textIn this paper, we consider a tree inference problem motivated by the critical problem in single-cell genomics of reconstructing dynamic cellular processes from sequencing data. In particular, given a population of cells sampled from such a process, we are interested in the problem of ordering the cells according to their progression in the process. This is known as trajectory inference. If the process is differentiation, this amounts to reconstructing the corresponding differentiation tree. One way of doing this in practice is to estimate the shortest-path distance between nodes based on cell similarities observed in sequencing data. Recent sequencing techniques make it possible to measure two types of data: gene expression levels, and RNA velocity, a vector that predicts changes in gene expression. The data then consist of a discrete vector field on a (subset of a) Euclidean space of dimension equal to the number of genes under consideration. By integrating this velocity field, we trace the evolution of gene expression levels in each single cell from some initial stage to its current stage. Eventually, we assume that we have a faithful embedding of the differentiation tree in a Euclidean space, but which we only observe through the curves representing the paths from the root to the nodes. Using varifold distances between such curves, we define a similarity measure between nodes which we prove approximates the shortest-path distance in a tree that is isomorphic to the target tree
Flexible Pooling Pattern Design with Integer Programming
No full textSample pooling has the potential to significantly enhance large-scale screening procedures, especially in scenarios like the COVID-19 pandemic, where rapid and widespread PCR testing has been crucial. Efficient strategies are essential to increase the testing capacity, i.e., the number of tests that can be processed within a given timeframe. Non-adaptive pooling strategies can further streamline the testing process by reducing the required testing rounds. In contrast to adaptive strategies, where subsequent tests depend on prior results, non-adaptive pooling processes all samples in a single round, eliminating the need for sequential retesting and reducing delays. This paper presents a highly flexible method based on integer programming to design optimized pooling patterns suitable for various applications, including
medical diagnostics and quality control in industrial production. Using coronavirus
testing as a case study, we formulate and solve optimization and satisfiability models
that compute efficient pool designs. Our optimized pooling does not only increase
testing capacity, but also accelerates the testing process and reduces overall costs.
The proposed method is adaptable and can be seamlessly integrated into automated
testing systems
Investigating Endogenous Opioids Unravels the Mechanisms Behind Opioid-Induced Constipation, a Mathematical Modeling Approach
No full textEndogenous opioids, such as Endomorphin-2, are not typically associated with severe constipation, unlike pharmaceutical opioids, which induce opioid-induced constipation (OIC) by activating μ-opioid receptors in the gastrointestinal tract. In this study, we present a mathematical model, which integrates the serotonergic and opioid pathways, simulating the interaction between serotonin and opioid signaling within the enteric nervous system (ENS). The model explores the mechanisms underlying OIC, with a focus on the change in adenylyl cyclase (AC) activity, cAMP accumulation, and the distinct functionalities of Endomorphin-2 compared to commonly used pharmaceutical opioids. We study the effects of Morphine, Fentanyl, and Methadone and contrast them with Endomorphin-2. Our findings reveal that opioids do not perturb the signaling of serotonin, but only the activity of AC, suggesting that serotonin levels have no influence on improving opioid-induced constipation. Furthermore, this study reveals that the primary difference between endogenous and pharmaceutical opioids is their degradation rates. This finding shows that modulating opioid degradation rates significantly improves cAMP recovery. In conclusion, our insights steer towards exploring opioid degrading enzymes, localized to the gut, as a strategy for mitigating OIC
