00.00.00 GENERAL
Refine
Year of publication
Document Type
- ZIB-Report (17)
- Bachelor's Thesis (1)
- Master's Thesis (1)
Keywords
Optimization models often feature disjunctions of polytopes as
submodels. Such a disjunctive set is initially (at best) relaxed to
its convex hull, which is then refined by branching.
To measure the error of the convex relaxation, the (relative)
difference between the volume of the convex hull and the volume of the
disjunctive set may be used. This requires a method to compute the
volume of the disjunctive set. Naively, this can be done via
inclusion/exclusion and leveraging the existing code for the volume
of polytopes. However, this is often inefficient.
We propose a revised variant of an old algorithm by Bieri and Nef
(1983) for this purpose. The algorithm uses a sweep-plane to
incrementally calculate the volume of the disjunctive set as a
function of the offset parameter of the sweep-plane.
大規模二次割当問題への挑戦
(2022)
Traditionally, Lagrangian fields such as finite-time Lyapunov exponents (FTLE)
are precomputed on a discrete grid and are ray casted afterwards. This, however,
introduces both grid discretization errors and sampling errors during ray marching.
In this work, we apply a progressive, view-dependent Monte Carlo-based approach
for the visualization of such Lagrangian fields in time-dependent flows. Our ap-
proach avoids grid discretization and ray marching errors completely, is consistent,
and has a low memory consumption. The system provides noisy previews that con-
verge over time to an accurate high-quality visualization. Compared to traditional
approaches, the proposed system avoids explicitly predefined fieldline seeding
structures, and uses a Monte Carlo sampling strategy named Woodcock tracking
to distribute samples along the view ray. An acceleration of this sampling strategy
requires local upper bounds for the FTLE values, which we progressively acquire
during the rendering. Our approach is tailored for high-quality visualizations of
complex FTLE fields and is guaranteed to faithfully represent detailed ridge surface
structures as indicators for Lagrangian coherent structures (LCS). We demonstrate
the effectiveness of our approach by using a set of analytic test cases and real-world numerical simulations.
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.
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.
Many scientific applications deal with data from a multitude of different sources, e.g., measurements, imaging and simulations. Each source provides an additional perspective on the phenomenon of interest, but also comes with specific limitations, e.g. regarding accuracy, spatial and temporal availability. Effectively combining and analyzing such multimodal and partially incomplete data of limited accuracy in an integrated way is challenging. In this work, we outline an approach for an integrated analysis and visualization of the atmospheric impact of volcano eruptions. The data sets comprise observation and imaging data from satellites as well as results from numerical particle simulations. To analyze the clouds from the volcano eruption in the spatiotemporal domain we apply topological methods. Extremal structures reveal structures in the data that support clustering and comparison. We further discuss the robustness of those methods with respect to different properties of the data and different parameter setups. Finally we outline open challenges for the effective integrated visualization using topological methods.
Lagrangian Coherent Structures (LCS) have become a widespread and powerful method to describe dynamic motion patterns in time-dependent flow fields. The standard way to extract LCS is to compute height ridges in the Finite Time Lyapunov Exponent (FTLE) field. In this work, we present an alternative method to approximate Lagrangian features for 2D unsteady flow fields that achieves subgrid accuracy without additional particle sampling. We obtain this by a geometric reconstruction of the flow map using additional material constraints for the available samples. In comparison to the standard method, this allows for a more accurate global approximation of LCS on sparse grids and for long integration intervals. The proposed algorithm works directly on a set of given particle trajectories and without additional flow map derivatives. We demonstrate its application for a set of computational fluid dynamic examples, as well as trajectories acquired by Lagrangian methods, and discuss its
benefits and limitations.
Bei der numerischen Lösung von Optimalsteuerungsproblemen mit
elliptischen partiellen Differentialgleichungen als Nebenbedingung
treten unvermeidlich Diskretisierungs- und Iterationsfehler auf.
Man ist aus Aufwandsgründen daran interessiert die dabei entstehenden
Fehler nicht sehr klein wählen zu müssen. In der Folge werden die linearisierten Nebenbedingungen in einem Composite-Step-Verfahren nicht exakt erfüllt. In dieser Arbeit wird der Einfluss dieser Ungenauigkeit auf das Konvergenzverhalten von Newton-Lagrange-Verfahren untersucht.
Dabei sollen mehrere einschlägige lokale Konvergenzresultate diskutiert werden.
Anschließend wird ein konkretes Composite-Step-Verfahren formuliert, in dem die Genauigkeit der
inneren Iterationsverfahren adaptiv gesteuert werden kann.
Am Ende der Arbeit wird an zwei Musterproblemen die hohe Übereinstimmung der analytischen
Voraussagen und der tatsächlichen Performanz der dargestellten Methoden demonstriert.
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.