Publication Server of Zuse Institute Berlin (ZIB)
Not a member yet
6648 research outputs found
Sort by
Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization
No full textThis article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary.
We compare the practical performance of the resulting algorithm with both puremethods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach, while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero, while maintaining the speed of the pure LP iterative refinement approach
Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization
No full textPrincipled Deep Neural Network Training Through Linear Programming
No full textDeep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident and multiple works in recent years have focused on this task. In this work, using a unified framework, we show that there exists a polyhedron that simultaneously encodes, in its facial structure, all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample size. Notably, the size of the polyhedral representation depends only linearly on the sample size, and a better dependency on several other network parameters is unlikely. Using this general result, we compute the size of the polyhedral encoding for commonly used neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal strong structure arising from these problems
Statistically optimal force aggregation for coarse-graining molecular dynamics
No full textMachine-learned coarse-grained (CG) models have the potential for simulating large molecular complexes beyond what is possible with atomistic molecular dynamics. However, training accurate CG models remains a challenge. A widely used methodology for learning bottom-up CG force fields maps forces from all-atom molecular dynamics to the CG representation and matches them with a CG force field on average. We show that there is flexibility in how to map all-atom forces to the CG representation and that the most commonly used mapping methods are statistically inefficient and potentially even incorrect in the presence of constraints in the all-atom simulation. We define an optimization statement for force mappings and demonstrate that substantially improved CG force fields can be learned from the same simulation data when using optimized force maps. The method is demonstrated on the miniproteins chignolin and tryptophan cage and published as open-source code
Machine learned coarse-grained protein force-fields: Are we there yet?
No full textThe successful recent application of machine learning methods to scientific problems includes the learning of flexible and accurate atomic-level force-fields for materials and biomolecules from quantum chemical data. In parallel, the machine learning of force-fields at coarser resolutions is rapidly gaining relevance as an efficient way to represent the higher-body interactions needed in coarse-grained force-fields to compensate for the omitted degrees of freedom. Coarse-grained models are important for the study of systems at time and length scales exceeding those of atomistic simulations. However, the development of transferable coarse-grained models via machine learning still presents significant challenges. Here, we discuss recent developments in this field and current efforts to address the remaining challenges
Evaluation of Uncertainties in Linear-Optimizing Energy System Models - Compendium
No full textFür die Energiesystemforschung sind Software-Modelle ein Kernelement zur Analyse von Szenarien. Das Forschungsprojekt UNSEEN hatte das Ziel eine bisher unerreichte Anzahl an modellbasierten Energieszenarien zu berechnen, um Unsicherheiten – vor allem unter Nutzung linear optimierender Energiesystem-Modelle - besser bewerten zu können. Hierfür wurden umfangreiche Parametervariationen auf Energieszenarien angewendet und das wesentliche methodische Hindernis in diesem Zusammenhang adressiert: die rechnerische Beherrschbarkeit der zu lösenden mathematischen Optimierungsprobleme. Im Vorläuferprojekt BEAM-ME wurde mit der Entwicklung und Anwendung des Open-Source-Lösers PIPS-IPM++ die Grundlage für den Einsatz von High-Performance-Computing (HPC) zur Lösung dieser Modelle gelegt. In UNSEEN war dieser Löser die zentrale Komponente eines Workflows, welcher zur Generierung, Lösung und multi-kriteriellen Bewertung von Energieszenarien auf dem Hochleistungscomputer JUWELS am Forschungszentrum Jülich implementiert wurde. Zur effizienten Generierung und Kommunikation von Modellinstanzen für Methoden der mathematischen Optimierung auf HPC wurde eine weitere Workflow-Komponente von der GAMS Software GmbH entwickelt: der Szenariogenerator. Bei der Weiterentwicklung von Lösungsalgorithmen für linear optimierende Energie-Systemmodelle standen gemischt-ganzzahlige Optimierungsprobleme im Fokus, welche für die Modellierung konkreter Infrastrukturen und Maßnahmen zur Umsetzung der Energiewende gelöst werden müssen. Die in diesem Zusammenhang stehenden Arbeiten zur Entwicklung von Algorithmen wurden von der Technischen Universität Berlin verantwortet. Bei Design und Implementierung dieser Methoden wurde sie vom Zuse Instituts Berlin unterstützt
Fast Floating-Point Filters for Robust Predicates
No full textGeometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests.
These algorithms have applications in scientific computing, geographic information systems and computer-aided design.
With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail.
This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations.
The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this.
We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions.
We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed.
We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations.
Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations
The Decision Theatre Triangle for societal challenges – an example case and research needs
No full textTackling societal challenges relating to sustainability requires both an understanding of the underlying complex socio-ecological systems and participation of scientists as well as relevant stakeholders, such as practice experts, decision makers, and citizens. This paper introduces the Decision Theatre Triangle, a method which combines empirical information, mathematical modelling and simulation, and a format for dialogue between scientists and stakeholders. While it builds on previous Decision Theatre work, the new structuring into these three elements emphasizes what is needed for setting up a Decision Theatre for a given challenge. Based on experience with a specific example – sustainable mobility in Germany – it is argued that agent-based models are particularly suitable for Decision Theatres and that the method is useful not only for decision support but also for science communication and co-creation of a deeper knowledge of the system under discussion. As a step towards facilitating a broader use of the Decision Theatre Triangle method, the paper then sketches research needs for each of its three elements, with a focus on mathematical modelling and simulation
Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
No full textNonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set