Publication Server of Zuse Institute Berlin (ZIB)
Not a member yet
6648 research outputs found
Sort by
A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network
No full textConsolidation 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
UmetaFlow: An untargeted metabolomics workflow for high-throughput data processing and analysis
No full textMetabolomics experiments generate highly complex datasets, which are time and work-intensive, sometimes even error-prone if inspected manually. Therefore, new methods for automated, fast, reproducible, and accurate data processing and dereplication are required. Here, we present UmetaFlow, a computational workflow for untargeted metabolomics that combines algorithms for data pre-processing, spectral matching, molecular formula and structural predictions, and an integration to the GNPS workflows Feature-Based Molecular Networking and Ion Identity Molecular Networking for downstream analysis. UmetaFlow is implemented as a Snakemake workflow, making it easy to use, scalable, and reproducible. For more interactive computing, visualization, as well as development, the workflow is also implemented in Jupyter notebooks using the Python programming language and a set of Python bindings to the OpenMS algorithms (pyOpenMS). Finally, UmetaFlow is also offered as a web-based Graphical User Interface for parameter optimization and processing of smaller-sized datasets. UmetaFlow was validated with in-house LC–MS/MS datasets of actinomycetes producing known secondary metabolites, as well as commercial standards, and it detected all expected features and accurately annotated 76% of the molecular formulas and 65% of the structures. As a more generic validation, the publicly available MTBLS733 and MTBLS736 datasets were used for benchmarking, and UmetaFlow detected more than 90% of all ground truth features and performed exceptionally well in quantification and discriminating marker selection
A Computational Study of Perspective Cuts
No full textThe benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time
Efficient Estimation of Transition Rates as Functions of pH
No full textExtracting the kinetic properties of a system whose dynamics depend on the pH of the environment with which it exchanges energy and atoms requires sampling the Grand Canonical Ensemble. As an alternative, we present a novel strategy that requires simulating only the most recurrent Canonical Ensembles that compose the Grand Canonical Ensemble. The simulations are used to estimate the Gran Canonical distribution for a specific pH value by reweighting and to construct the transition rate matrix by discretizing the Fokker-Planck equation by Square Root Approximation and robust Perron Cluster Cluster Analysis. As an application, we have studied the tripeptide Ala-Asp-Ala
Predicting Shape Development: A Riemannian Method
No full textPredicting the future development of an anatomical shape from a single baseline observation is a challenging task. But it can be essential for clinical decision-making. Research has shown that it should be tackled in curved shape spaces, as (e.g., disease-related) shape changes frequently expose nonlinear characteristics. We thus propose a novel prediction method that encodes the whole shape in a Riemannian shape space. It then learns a simple prediction technique founded on hierarchical statistical modeling of longitudinal training data. When applied to predict the future development of the shape of the right hippocampus under Alzheimer's disease and to human body motion, it outperforms deep learning-supported variants as well as state-of-the-art
Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates
No full textThe ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems.
Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear.
In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized.
Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic.
We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters
Efficient machine-learning approach to optimize trapped cold atom ensembles for quantum memory applications
No full textSupplementary code for the paper Modelling opinion dynamics under the impact of influencer and media strategies
No full textThis repository contains the Julia code accompanying the paper "Modelling opinion dynamics under the impact of influencer and media strategies", Scientific Reports, Vol.13, p. 19375, 2023
A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance
No full textWe present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles
and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse-
quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables
A computational status update for exact rational mixed integer programming
No full textThe last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours