TY - THES A1 - Gutsche, Philipp T1 - Convergence Study of the Fourier Modal Method for Nano-optical Scattering Problems in Comparison with the Finite Element Method N2 - Nano-optical scattering problems play an important role in our modern, technologically driven society. Computers, smartphones and all kinds of electronic devices are manufactured by the semiconductor industry which relies on production using photomasks as well as optical process control. The digital world, e.g. the world wide web, is based on optical interconnects and so-called quantum computers based on optics are supposed to be next generation computers. Moreover, global economic progress demands new and sustainable energy resources and one option is to make use of the power stored in optical radiation from the sun. Additionally, understanding fundamental physics such as the optical properties of asymmetric, or chiral, structures could promote future innovations in engineering. In order to understand and manipulate these kinds of processes, physics provides a well established model: the so-called Maxwell’s equations. Stated by James Clerk Maxwell in 1862, this description of the interaction of light and matter still provides a profound basis for the analysis of electromagnetic phenomena. However, real world problems cannot be calculated using simple mathematics. Rather, computer simulations are needed to obtain solutions of the physical model. Finding suitable methods to solve these problems opens up a wide variety of possibilities. On the one hand, there are methods which require long computing times. On the other hand, some algorithms depend on high memory usage. That is why the field of numerics deals with the question which method is optimally suited for specific problems. The aim of this work is to investigate the applicability of the so-called Fourier Modal Method (FMM) to nano-optical scattering problems in general. Since simple analytical solutions are non-existent for most recent physical problems, we use the Finite Element Method (FEM) to double-check performance of the FMM. Mathematics provide reliable procedures to control the errors of numerics using the FEM. Yet up to now it has not been possible to rigorously classify the quality of the Fourier Modal Method’s results. It is not fully understood whether the process of investing more and more computing resources yields more accurate results. So, we have to ask ourselves: does the numerical method invariably converge? In spite of this uncertainty when using the FMM, it is a well established method dating back to the 1980s. This numerical method has recently been used to optimize performance of solar cells [19] as well as to improve the optical properties of so-called single-photon sources [41] which are essential for quantum cryptography. The latter is a promising candidate to increase digital security and revolutionise cryptography techniques. Furthermore, with the help of the Fourier Modal Method an important issue in optics has been partly resolved: angular filtering of light was made possible by using a mirror which becomes transparent at a certain viewing angle [77]. In addition, an improved numerical technique to design so-called Photonic Crystal waveguides based on the FMM was developed recently [15]. Photonic Crystals are used in the fields of optical bio-sensing and for the construction of novel semiconductor devices. Moreover, approaches to link the FMM and the FEM try to combine advantages of both methods to obtain fast and accurate results [81]. These ideas are closely linked to the well-known concept of Domain Decomposition within the FEM [88]. Here, one possibility to couple domains is to use the scattering matrix formalism as it is done in the FMM. In the scope of this convergence study, we state Maxwell’s equations, particularly for periodic geometries. We describe two physical phenomena of nano-optics, namely chirality and opto-electrical coupling, and define the errors of our simulations. Afterwards, the two investigated methods are analysed with respect to their general properties and a way to unify modelling physics when using both algorithms is presented. With the help of various numerical experiments, we explore convergence characteristics of the FMM and draw conclusions about the ability of this approach to provide accurate results and, consequently, its potential for research on technological innovations. KW - Nano-optics KW - Fourier Modal Method (FMM) KW - Rigorous Coupled Wave Analysis (RCWA) KW - Finite Element Method (FEM) Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56084 ER - TY - GEN A1 - Rössig, Ansgar T1 - Verification of Neural Networks T3 - ZIB-Report - 19-40 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74174 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Becker, Kai-Helge T1 - Improving relaxations for potential-driven network flow problems via acyclic flow orientations N2 - The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network. We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage. T3 - ZIB-Report - 18-30 KW - potential-driven network flows KW - acyclic orientations KW - flow orientations KW - MINLPs Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69622 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Vertex Covering with Capacitated Trees N2 - The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature. T3 - ZIB-Report - 21-14 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82616 SN - 1438-0064 ER - TY - THES A1 - Mattrisch, Lisa T1 - Optimization of a Master Surgery Schedule N2 - During the past years hospitals saw themselves confronted with increasing economical pressure (WB06, p. V). Therefore, optimizing the general operational procedures has gained in importance. The revenue of a hospital depends on the kinds and quantity of treatments performed and on the effcient use and utilization of the corresponding resources. About 25 − 50% of the treatment costs of a patient needing surgery incurs in the operating rooms (WB06, p. 58). Hence skillful management of the operating rooms can have a large impact on the overall revenue of a hospital. Belien and Demeulemeester (BD07) describe the planning of operating room (OR) schedules as a multi-stage process. In the first stage OR time is allocated to the hospitals specialties and capacities and resources are adjusted. In the second stage a master surgery schedule (MSS) is developed, that is a timetable for D days that specifies the amount of OR time assigned to the specialties on every individual day. After D days this schedule will be repeated without any changes. Hence, developing an MSS is a long-term problem. Finally, specialties will schedule specific surgeries within their assigned OR time. In this work we will focus on the development of the MSS that maximizes the revenue of the hospital. Our main focus will be to ensure that the capacities of the downstream resources, i.e. the bed capacities in the ICU and ward, will not be exceeded. Additionally, we hope that our formulation of the problem will lead to a leveled bed demand without significant peaks. We will incorporate the uncertainty of patient demand and case mix in our model. There have been several approaches on this subject, for example in (Fü15) and (BD07) and this work is in part in� uenced by these advances. KW - Master Surgery Scheduling KW - Conic Programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69996 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Finding Minimum Balanced Separators - an Exact Approach T2 - Operations Research Proceedings 2021 N2 - Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances. T3 - ZIB-Report - 21-25 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83138 SN - 1438-0064 SP - 154 EP - 159 ER - TY - GEN A1 - Lehmann, Felix T1 - Inexaktheit in Newton-Lagrange-Verfahren für Optimierungsprobleme mit Elliptischen PDGL-Nebenbedingungen N2 - 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. T3 - ZIB-Report - 13-37 KW - optimal control KW - PDE KW - inexact Newton Lagrange KW - adaptive Newton Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41972 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - Determining all integer vertices of the PESP polytope by flipping arcs N2 - We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib. T3 - ZIB-Report - 20-19 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Mixed Integer Programming Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78793 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Egerer, Ascan A1 - Karbstein, Marika A1 - Messerschmidt, Ralf A1 - Perez, Marc A1 - Pfisterer, Steven A1 - Strauß, Petra T1 - Kombilösung: Optimierung des Liniennetzes in Karlsruhe N2 - Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung. T3 - ZIB-Report - 18-45 KW - ÖPNV KW - Linienplanung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69677 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - New Perspectives on PESP: T-Partitions and Separators N2 - In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time. T3 - ZIB-Report - 19-35 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Graph Partitioning KW - Graph Separators KW - Balanced Cuts Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73853 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian A1 - Masing, Berenike T1 - Forward Cycle Bases and Periodic Timetabling N2 - Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds. T3 - ZIB-Report - 21-18 KW - Periodic Timetabling KW - Cycle Bases KW - Mixed Integer Programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82756 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Maristany de las Casas, Pedro A1 - Schiewe, Philine T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data N2 - We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport. T3 - ZIB-Report - 21-17 KW - Preprocessing Shortest Path Problems KW - Interval Data KW - Graph Algorithms Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82716 SN - 1438-0064 ER - TY - GEN A1 - Müller, Benjamin A1 - Muñoz, Gonzalo A1 - Gasse, Maxime A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Serrano, Felipe T1 - On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming N2 - The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments. T3 - ZIB-Report - 19-55 KW - surrogate relaxation KW - MINLP KW - nonconvex optimization Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75179 SN - 1438-0064 ER - TY - GEN A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Gleixner, Ambros T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms N2 - One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly. T3 - ZIB-Report - 19-15 KW - mixed-integer quadratically constrained programs KW - nonconvex KW - global optimization KW - separation KW - propagation KW - projection KW - bilinear terms Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72759 SN - 1438-0064 ER - TY - GEN A1 - Winkelmann, Stefanie T1 - Markov Control with Rare State Observation: Average Optimality N2 - This paper investigates the criterion of long-term average costs for a Markov decision process (MDP) which is not permanently observable. Each observation of the process produces a fixed amount of \textit{information costs} which enter the considered performance criterion and preclude from arbitrarily frequent state testing. Choosing the \textit{rare} observation times is part of the control procedure. In contrast to the theory of partially observable Markov decision processes, we consider an arbitrary continuous-time Markov process on a finite state space without further restrictions on the dynamics or the type of interaction. Based on the original Markov control theory, we redefine the control model and the average cost criterion for the setting of information costs. We analyze the constant of average costs for the case of ergodic dynamics and present an optimality equation which characterizes the optimal choice of control actions and observation times. For this purpose, we construct an equivalent freely observable MDP and translate the well-known results from the original theory to the new setting. T3 - ZIB-Report - 16-59 KW - Markov decision process KW - partial observability KW - average optimality KW - information costs Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60981 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem N2 - We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems. T3 - ZIB-Report - 14-26 KW - column generation KW - coarse-to-fine approach KW - multi-layer approach KW - rolling stock rotation problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51009 SN - 1438-0064 ER - TY - GEN A1 - Reuther, Markus A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Integrated Optimization of Rolling Stock Rotations for Intercity Railways N2 - This paper provides a highly integrated solution approach for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a generic hypergraph based mixed integer programming model and an integrated algorithm for the considered rolling stock rotation planning problem. The new developed approach is able to handle a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects. By the integration of this large bundle of technical railway aspects, we show that our approach has the power to produce implementable rolling stock rotations for our industrial cooperation partner DB Fernverkehr. This is the first time that the rolling stock rotations at DB Fernverkehr could be optimized by an automated system utilizing advanced mathematical programming techniques. T3 - ZIB-Report - 12-39 KW - Mixed Integer Programming KW - Railway Optimization KW - Rolling Stock Rostering Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16424 SN - 1438-0064 ER - TY - GEN A1 - Szabó, Jácint T1 - The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula N2 - In this paper we give an analytical description on the structure of solutions to the gas nomination validation problem in gas transportation networks. These networks are assumed to contain no active devices, only certain hypothetical pipelines, where the flow of gas is modeled by a generalized version of the quadratic Weymouth's equation. The purpose of considering generalized flow formulas is to be able to adapt our results to various gas network optimization problems involving gas flow formulas beyond Weymouth's equation. Such formulas can appear in leaves of branch and bound trees, or they can stem from discretization and linearization carried out at active devices. We call a balanced supply-demand vector a nomination, and the passive nomination validation problem is to decide whether there exist pressures at the nodes generating a given nomination. We prove that in our setup the pressure square vectors generating a given nomination form a one-dimensional connected and continuous curve in the pressure square space, and this curve is a line for the classical Weymouth's equation. We also present a visual approach for the easy comprehension of how this solution curve arises; we give a short investigation of the set of feasible nominations; and finally we give a proof that the nomination validation problem in gas networks with active devices is NP-complete. T3 - ZIB-Report - 11-44 KW - pressure drop equation KW - gas networks KW - generalized flow formula Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15151 SN - 1438-0064 ER - TY - GEN A1 - Hammerschmidt, Martin A1 - Herrmann, Sven A1 - Pomplun, Jan A1 - Burger, Sven A1 - Schmidt, Frank T1 - Model order reduction for the time-harmonic Maxwell equation applied to complex nanostructures T2 - Proc. SPIE N2 - Fields such as optical metrology and computational lithography require fast and efficient methods for solving the time-harmonic Maxwell’s equation. Highly accurate geometrical modeling and numerical accuracy atcomputational costs are a prerequisite for any simulation study of complex nano-structured photonic devices. We present a reduced basis method (RBM) for the time-harmonic electromagnetic scattering problem based on the hp-adaptive finite element solver JCMsuite capable of handling geometric and non-geometric parameter dependencies allowing for online evaluations in milliseconds. We apply the RBM to compute light-scatteringoptical wavelengths off periodic arrays of fin field-effect transistors (FinFETs) where geometrical properties such as the width and height of the fin and gate can vary in a large range. T3 - ZIB-Report - 16-05 KW - reduced basis method KW - finite element method KW - rigorous optical modeling KW - reduced order models KW - electromagnetic field solver Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57239 SN - 1438-0064 VL - 9742 SP - 97420M ER - TY - GEN A1 - Hammerschmidt, Martin A1 - Barth, Carlo A1 - Pomplun, Jan A1 - Burger, Sven A1 - Becker, Christiane A1 - Schmidt, Frank T1 - Reconstruction of photonic crystal geometries using a reduced basis method for nonlinear outputs N2 - Maxwell solvers based on the hp-adaptive finite element method allow for accurate geometrical modeling and high numerical accuracy. These features are indispensable for the optimization of optical properties or reconstruction of parameters through inverse processes. High computational complexity prohibits the evaluation of the solution for many parameters. We present a reduced basis method (RBM) for the time-harmonic electromagnetic scattering problem allowing to compute solutions for a parameter configuration orders of magnitude faster. The RBM allows to evaluate linear and nonlinear outputs of interest like Fourier transform or the enhancement of the electromagnetic field in milliseconds. We apply the RBM to compute light-scattering off two dimensional photonic crystal structures made of silicon and reconstruct geometrical parameters. T3 - ZIB-Report - 16-06 KW - finite element method KW - rigorous optical modeling KW - photonic crystals KW - reduced basis method KW - parameter estimation KW - optical metrology Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57249 SN - 1438-0064 ER - TY - THES A1 - Schlechte, Thomas T1 - Railway Track Allocation: Models and Algorithms N2 - This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. The opening chapter gives a comprehensive overview on railway planning problems. This provides insights into the regulatory and technical framework, it discusses the interaction of several planning steps, and identifies optimization potentials in railway transportation. The remainder of the thesis is comprised of two major parts. The first part is concerned with modeling railway systems to allow for resource and capacity analysis. Railway capacity has basically two dimensions, a space dimension which are the physical infrastructure elements as well as a time dimension that refers to the train movements, i.e., occupation or blocking times, on the physical infrastructure. Railway safety systems operate on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through. Two trains reserving the same block of the infrastructure within the same point in time is called block conflict. Therefore, models for railway capacity involve the definition and calculation of reasonable running and associated reservation and blocking times to allow for a conflict free allocation. In the second and main part of the thesis, the optimal track allocation problem for macroscopic models of the railway system is considered. The literature for related problems is surveyed. A graph-theoretic model for the track allocation problem is developed. In that model optimal track allocations correspond to conflict-free paths in special time-expanded graphs. Furthermore, we made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. Finally, we go back to practice and present in the last chapter several case studies using the tools netcast and tsopt. We provide a computational comparison of our new models and standard packing models used in the literature. Our computational experience indicates that our approach, i.e., ``configuration models'', outperforms other models. Moreover, the rapid branching heuristic and the bundle method enable us to produce high quality solutions for very large scale instances, which has not been possible before. In addition, we present results for a theoretical and rather visionary auction framework for track allocation. We discuss several auction design questions and analyze experiments of various auction simulations. The highlights are results for the Simplon corridor in Switzerland. We optimized the train traffic through this tunnel using our models and software tools. To the best knowledge of the author and confirmed by several railway practitioners this was the first time that fully automatically produced track allocations on a macroscopic scale fulfill the requirements of the originating microscopic model, withstand the evaluation in the microscopic simulation tool OpenTrack, and exploit the infrastructure capacity. This documents the success of our approach in practice and the usefulness and applicability of mathematical optimization to railway track allocation. KW - railway track allocation KW - large-scale integer programming KW - network aggregation KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-34272 UR - http://opus.kobv.de/tuberlin/volltexte/2012/3427/pdf/schlechte_thomas.pdf SN - 978-3-8381-3222-8 PB - Südwestdeutscher Verlag für Hochschulschriften CY - Saarbrücken, Germany ER - TY - GEN A1 - Grötschel, Martin A1 - Stephan, Rüdiger T1 - Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming N2 - In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004. T3 - ZIB-Report - 11-54 KW - hop constraints KW - chains KW - dynamic programming KW - facets Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14914 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin T1 - Einblicke in die Diskrete Mathematik N2 - „Diskrete Mathematik, was ist das?“, ist eine typische Frage von Lehrern mit traditioneller Mathematikausbildung, denn dort kam und kommt diskrete Mathematik kaum vor. Die etwas Aufgeschlosseneren fragen: „Wenn (schon wieder) etwas Neues unterrichtet werden soll, was soll denn dann im Lehrplan gestrichen werden?“ Auf die zweite Frage wird hier nicht eingegangen. Das Ziel dieses Aufsatzes ist es, in diskrete Mathematik einzuführen, Interesse an diesem Fachgebiet zu wecken und dazu anzuregen, dieses auch im Schulunterricht (ein wenig) zu berücksichtigen. Die Schüler und Schülerinnen werden dafür dankbar sein – eine Erfahrung, die in vielen Unterrichtsreihen gemacht wurde. T3 - ZIB-Report - 12-01 KW - diskrete Mathematik Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14399 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update N2 - Contemporary supercomputers can easily provide years of CPU time per wall-clock hour. One challenge of today's software development is how to harness this wast computing power in order to solve really hard mixed integer programming instances. In 2010, two out of six open MIPLIB2003 instances could be solved by ParaSCIP in more than ten consecutive runs, restarting from checkpointing files. The contribution of this paper is threefold: For the first time, we present computational results of single runs for those two instances. Secondly, we provide new improved upper and lower bounds for all of the remaining four open MIPLIB2003 instances. Finally, we explain which new developments led to these results and discuss the current progress of ParaSCIP. Experiments were conducted on HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores. T3 - ZIB-Report - 13-66 KW - Mixed Integer Programming KW - MIPLIB2003 KW - ParaSCIP KW - Ubiquity Generator Framework KW - Supercomputer Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42888 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Probabilistic alternatives for competitive analysis N2 - In the last 20 years competitive analysis has become the main tool for analyzing the quality of online algorithms. Despite of this, competitive analysis has also been criticized: It sometimes cannot discriminate between algorithms that exhibit significantly different empirical behavior, or it even favors an algorithm that is worse from an empirical point of view. Therefore, there have been several approaches to circumvent these drawbacks. In this survey, we discuss probabilistic alternatives for competitive analysis. T3 - ZIB-Report - 11-55 KW - online algorithms KW - probabilistic analysis KW - competitive analysis KW - survey Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15131 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem N2 - We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997). T3 - ZIB-Report - 17-79 KW - Scheduling KW - Mixed-Integer Programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68485 SN - 1438-0064waoa ER - TY - GEN A1 - Tesch, Alexander T1 - Improving Energetic Propagations for Cumulative Scheduling N2 - We consider the Cumulative Scheduling Problem (CuSP) in which a set of $n$ jobs must be scheduled according to release dates, due dates and cumulative resource constraints. In constraint programming, the CuSP is modeled as the cumulative constraint. Among the most common propagation algorithms for the CuSP there is energetic reasoning (Baptiste et al., 1999) with a complexity of O(n^3) and edge-finding (Vilim, 2009) with O(kn log n) where k <= n is the number of different resource demands. We consider the complete versions of the propagators that perform all deductions in one call of the algorithm. In this paper, we introduce the energetic edge-finding rule that is a generalization of both energetic reasoning and edge-finding. Our main result is a complete energetic edge-finding algorithm with a complexity of O(n^2 log n) which improves upon the complexity of energetic reasoning. Moreover, we show that a relaxation of energetic edge-finding with a complexity of O(n^2) subsumes edge-finding while performing stronger propagations from energetic reasoning. A further result shows that energetic edge-finding reaches its fixpoint in strongly polynomial time. Our main insight is that energetic schedules can be interpreted as a single machine scheduling problem from which we deduce a monotonicity property that is exploited in the algorithms. Hence, our algorithms improve upon the strength and the complexity of energetic reasoning and edge-finding whose complexity status seemed widely untouchable for the last decades. T3 - ZIB-Report - 18-29 KW - Cumulative Scheduling KW - Constraint Programming KW - Propagation Algorithm Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69331 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - On the semidefinite representations of real functions applied to symmetric matrices N2 - We present a new semidefinite representation for the trace of a real function f applied to symmetric matrices, when a semidefinite representation of the convex function f is known. Our construction is intuitive, and yields a representation that is more compact than the previously known one. We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices that for a rational number p in the interval (0,1], the matrix X raised to the exponent p is the largest element of a set represented by linear matrix inequalities. We give numerical results for a problem inspired from the theory of experimental designs, which show that the new semidefinite programming formulation yields a speed-up factor in the order of 10. T3 - ZIB-Report - 12-50 KW - semidefinite representability KW - optimal experimental designs KW - SDP KW - matrix geometric mean Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17511 SN - 1438-0064 VL - 439 SP - 2829 EP - 2843 ER - TY - GEN A1 - Sagnol, Guillaume T1 - A Class of Semidefinite Programs with rank-one solutions N2 - We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite matrix of rank at most $r$, where $r$ is the rank of the matrix involved in the objective function of the SDP. The optimization problems of this class are semidefinite packing problems, which are the SDP analogs to vector packing problems. Of particular interest is the case in which our result guarantees the existence of a solution of rank one: we show that the computation of this solution actually reduces to a Second Order Cone Program (SOCP). We point out an application in statistics, in the optimal design of experiments. T3 - ZIB-Report - 11-51 KW - SDP KW - Semidefinite Packing Problem KW - rank 1-solution KW - Low-rank solutions KW - SOCP KW - Optimal Experimental Design KW - Multiresponse experiments Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14933 SN - 1438-0064 ER - TY - GEN A1 - Scheumann, Rene A1 - Fügenschuh, Armin A1 - Schenker, Sebastian A1 - Vierhaus, Ingmar A1 - Borndörfer, Ralf A1 - Finkbeiner, Matthias T1 - Global Manufacturing: How to Use Mathematical Optimisation Methods to Transform to Sustainable Value Creation N2 - It is clear that a transformation to sustainable value creation is needed, because business as usual is not an option for preserving competitive advantages of leading industries. What does that mean? This contribution proposes possible approaches for a shift in existing manufacturing paradigms. In a first step, sustainability aspects from the German Sustainability Strategy and from the tools of life cycle sustainability assessment are chosen to match areas of a value creation process. Within these aspects are indicators, which can be measured within a manufacturing process. Once these data are obtained they can be used to set up a mathematical linear pulse model of manufacturing in order to analyse the evolution of the system over time, that is the transition process, by using a system dynamics approach. An increase of technology development by a factor of 2 leads to an increase of manufacturing but also to an increase of climate change. Compensation measures need to be taken. This can be done by e.g. taking money from the GDP (as an indicator of the aspect ``macroeconomic performance''). The value of the arc from that building block towards climate change must then be increased by a factor of 10. The choice of independent and representative indicators or aspects shall be validated and double-checked for their significance with the help of multi-criteria mixed-integer programming optimisation methods. T3 - ZIB-Report - 12-28 KW - Multi-Criteria Optimisation KW - Sustainability Indicator KW - System Dynamics KW - Value Creation Process Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15703 SN - 1438-0064 ER - TY - GEN A1 - Schlechte, Thomas T1 - Railway Track Allocation N2 - This article gives an overview of the results of the author's PhD thesis. The thesis deals with the mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. We made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. T3 - ZIB-Report - 12-38 KW - large-scale integer programming KW - network aggregation KW - configuration models KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16402 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - The Three Phases of MIP Solving N2 - Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points. T3 - ZIB-Report - 16-78 KW - optimization software KW - mixed-integer programming KW - branch-and-bound KW - adaptive search behavior KW - optimality prediction Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61607 SN - 1438-0064 ER - TY - GEN A1 - Fujii, Koichi A1 - Ito, Naoki A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Shinano, Yuji A1 - Toh, Kim-Chuan T1 - 大規模二次割当問題への挑戦 T2 - 統計数理研究所共同研究リポート 453 最適化:モデリングとアルゴリズム33 2022年3月 「大規模二次割当問題への挑戦」 p.84-p.92 N2 - 二次割当問題は線形緩和が弱いことが知られ,強化のため多様な緩和手法が考案されているが,その一つである二重非負値計画緩和( DNN 緩和)及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し,それらに基づく分枝限定法の実装及び数値実験結果について報告する. T2 - Solving Large Scale QAPs with DNN-based Branch-and-bound : a progress report T3 - ZIB-Report - 22-11 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-86779 SN - 1438-0064 ER - TY - THES A1 - Lubkoll, Lars T1 - Optimal Control in Implant Shape Design KW - optimal control Y1 - 2011 ER - TY - GEN A1 - Tunga, Burcu A1 - Weber, Marcus T1 - Free Energy Calculation Using Mayer Cluster Expansion and Fluctuation Free Integration N2 - This work aims to develop a new algorithm to calculate the free energy of water molecules by using a deterministic way. For this purpose, we assume a closed system confined to a physical volume, having water molecules in gas phase. To calculate the free energy of this sytem we utilized Mayer cluster expansion and the fluctuation free integration method. T3 - ZIB-Report - 12-35 Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16031 SN - 1438-0064 ER - TY - THES A1 - Lehmann, Felix T1 - Inexaktheit in Newton-Lagrange-Verfahren für Optimierungsprobleme mit Elliptischen PDGL-Nebenbedingungen N2 - 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. KW - PDE KW - adaptive Newton KW - inexact Newton-Lagrange Y1 - 2013 UR - urn:nbn:de:0297-zib-41972 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints T3 - ZIB-Report - 21-34 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84427 SN - 1438-0064 ER - TY - THES A1 - Buwaya, Julia T1 - Optimizing control in a transportation network when users may choose their OD-path N2 - This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time. KW - Optimization KW - Transportation Network KW - Game Theory KW - Stackelberg Equilibrium KW - Mixed Integer Programming KW - Security Game KW - Linear Programming KW - Nash Equilibrium Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42330 ER - TY - GEN A1 - Harrod, Steven A1 - Schlechte, Thomas T1 - A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations N2 - Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall. T3 - ZIB-Report - 13-18 KW - Railway Scheduling KW - Train Timetabling KW - Track Allocation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17946 SN - 1438-0064 ER - TY - GEN A1 - Fügenschuh, Armin A1 - Grösser, Stefan N. A1 - Vierhaus, Ingmar T1 - A Global Approach to the Control of an Industry Structure System Dynamics Model N2 - We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps. T3 - ZIB-Report - 13-67 KW - System Dynamics; Mixed-Integer Nonlinear Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42932 SN - 1438-0064 ER - TY - GEN A1 - Raack, Christian A1 - Raymond, Annie A1 - Werner, Axel A1 - Schlechte, Thomas T1 - Integer Programming and Sports Rankings N2 - Sports rankings are obtained by applying a system of rules to evaluate the performance of the participants in a competition. We consider rankings that result from assigning an ordinal rank to each competitor according to their performance. We develop an integer programming model for rankings that allows us to calculate the number of points needed to guarantee a team the ith position, as well as the minimum number of points that could yield the ith place. The model is very general and can thus be applied to many types of sports. We discuss examples coming from football (soccer), ice hockey, and Formula~1. We answer various questions and debunk a few myths along the way. Are 40 points enough to avoid relegation in the Bundesliga? Do 95 points guarantee the participation of a team in the NHL playoffs? Moreover, in the season restructuration currently under consideration in the NHL, will it be easier or harder to access the playoffs? Is it possible to win the Formula~1 World Championship without winning at least one race or without even climbing once on the podium? Finally, we observe that the optimal solutions of the aforementioned model are associated to extreme situations which are unlikely to happen. Thus, to get closer to realistic scenarios, we enhance the model by adding some constraints inferred from the results of the previous years. T3 - ZIB-Report - 13-19 KW - sport ranking KW - integer programming Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18068 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - Müller, Benjamin A1 - Weltge, Stefan T1 - Three Enhancements for Optimization-Based Bound Tightening N2 - Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT. T3 - ZIB-Report - 15-16 KW - MINLP KW - optimization-based bound tightening KW - optimality-based bound tightening KW - OBBT KW - propagation KW - bound tightening Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57803 SN - 1438-0064 ER - TY - GEN A1 - Munguia, Lluis-Miquel A1 - Oxberry, Geoffrey A1 - Rajan, Deepak A1 - Shinano, Yuji T1 - Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs N2 - 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. T3 - ZIB-Report - 17-58 KW - PIPS-SBB, UG, Parallel Branch and Bound Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65517 SN - 1438-0064 IS - ZIB-Report 17-58 ER - TY - GEN A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance 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.The converted BQOP is much simpler than the original QAP tai256c and it also inherits some of the symmetry properties. However, it is still very difficult to solve. We present an efficient branch and bound method for improving the lower bound effectively. A new lower bound with 1.36% gap is also provided. T3 - ZIB-Report - 22-18 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88086 SN - 1438-0064 ER - TY - GEN A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed domain propagation N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. T3 - ZIB-Report - 16-71 KW - mixed integer programming KW - parallelization KW - domain propagation KW - portfolio solvers Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61380 SN - 1438-0064 ER - TY - GEN A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Hasenfelder, Richard A1 - Radons, Manuel T1 - Piecewise linear secant approximation via Algorithmic Piecewise Differentiation N2 - It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x − x̌|| ||x − x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton’s method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. T3 - ZIB-Report - 16-54 KW - Automatic differentiation KW - Computational graph KW - Lipschitz continuity KW - Generalized Hermite interpolation KW - ADOL-C Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61642 SN - 1438-0064 ER - TY - GEN A1 - Fackeldey, Konstantin A1 - Röblitz, Susanna A1 - Scharkoi, Olga A1 - Weber, Marcus T1 - Soft Versus Hard Metastable Conformations in Molecular Simulations N2 - Particle methods have become indispensible in conformation dynamics to compute transition rates in protein folding, binding processes and molecular design, to mention a few. Conformation dynamics requires at a decomposition of a molecule's position space into metastable conformations. In this paper, we show how this decomposition can be obtained via the design of either ``soft'' or ``hard'' molecular conformations. We show, that the soft approach results in a larger metastabilitiy of the decomposition and is thus more advantegous. This is illustrated by a simulation of Alanine Dipeptide. T3 - ZIB-Report - 11-27 KW - Proteins, Conformation Space, Meshfree Methods Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13189 ER - TY - GEN A1 - Anderson, Lovis A1 - Hiller, Benjamin T1 - A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes N2 - 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. T3 - ZIB-Report - 18-37 KW - Disjunctive Programming KW - Volume Algorithm KW - Union of Polytopes Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69489 SN - 1438-0064 ER - TY - THES A1 - Anderson, Lovis T1 - The Computation of the Volume of the Union of Polytopes via a Sweep-Plane Algorithm N2 - Das Thema dieser Arbeit ist ein Volumen-Algorithmus für die Vereinigung von Polytopen. Der Algorithmus basiert auf der Arbeit von Bieri und Nef. Er berechnet das Volumen der Vereinigung von Polytopen mit einem Sweep-Verfahren. Dabei wird eine Hyperebene im Raum verschoben und das Volumen auf der einen Seite der Hyperebene berechnet. Umso weiter die Hyperebene verschobe wird, desto größer ist auch der Halbraum. Unser Algorithmus berechnet das Volumen einer Vereinigung von Polytopen geschnitten mit dem Halbraum der Sweep-Ebene als eine Funktion abhängig von der Veschiebung. Ab einem gewissen Punkt liegt der Körper dabei komplett im Halbraum der Sweep-Ebene und das Volumen bleibt konstant. Unser Algorithmus unterscheidet sich in zwei Punkten von dem Algorithmus von Bieri und Nef. Erstens funktioniert er nur auf der Vereinigung von Polytopen, wohingegen der Algorithmus von Bieri und Nef für Nef-Polyeder funktioniert. Diese sind eine Verallgemeinerung von Polyedern, die auch die Klasse der Vereinigung von Polytopen umfasst. Für uns ist das allerdings kein Nachteil, da unsere Datensätze zu Vereinigungen von Polytopen führen. Zweitens ist unser Algorithmus in zwei Teile aufgeteilt. Im ersten Teil wird eine Datenstruktur entwickelt, aus der im zweiten Teil zusammen mit einer Richtung die Sweep-Ebenen-Volumenfunktion berechnet wird. Der Großteil der Komplexität liegt im ersten Teil des Algorithmus. Das hat den Vorteil, dass wir die Volumenfunktionen für viele verschiedene Richtungen berechnen können. So können Einblicke in die Struktur des Körpers gewonnen werden. Der Algorithmus beruht auf zwei verschiedenen Zerlegungsansätzen. Zuerst können wir mit Hilfe von Anordnungen von Hyperebenen eine Vereinigung von Polytopen in ihre Zellen zerlegen. Dabei berufen wir uns auf die Arbeit von Gerstner und Holtz, in der das Konzept der Positionsvektoren eingeführt wird. Diese nutzen wir um die Ecken und ihre benachbarten Zellen zu bestimmen. So erhalten wir eine Zerlegung unserer Vereinigung in Zellen, deren paarweise Schnitte kein Volumen haben. Das zweite Zerlegungskonzept ist die konische Zerlegung, wie sie von Lawrence eingeführt wurde. Mit Hilfe dieser können wir die Indikatorfunktion eines Polytops als die Summe der Indikatorfunktionen seiner Vorwärtskegel schreiben. Die Sweep-Ebenen Volumenfunktionen können dann leicht mit Hilfe einer altbekannten Formel für das Volumen von Simplices berechnet werden. Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71829 ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Ebert, Patricia T1 - Forward and Line-Based Cycle Bases for Periodic Timetabling N2 - 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. T3 - ZIB-Report - 23-05 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89731 SN - 1438-0064 ER - TY - THES A1 - Miltenberger, Matthias T1 - Linear Programming in MILP Solving - A Computational Perspective N2 - Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly. This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP's programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub. KW - linear programming KW - mixed-integer programming KW - optimization KW - simplex KW - SCIP Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91873 UR - https://www.dr.hut-verlag.de/9783843953238.html SN - 9783843953238 PB - Verlag Dr. Hut GmbH ER - TY - GEN A1 - Lie, Han Cheng A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - A square root approximation of transition rates for a Markov State Model N2 - Trajectory- or mesh-based methods for analyzing the dynamical behavior of large molecules tend to be impractical due to the curse of dimensionality - their computational cost increases exponentially with the size of the molecule. We propose a method to break the curse by a novel square root approximation of transition rates, Monte Carlo quadrature and a discretization approach based on solving linear programs. With randomly sampled points on the molecular energy landscape and randomly generated discretizations of the molecular configuration space as our initial data, we construct a matrix describing the transition rates between adjacent discretization regions. This transition rate matrix yields a Markov State Model of the molecular dynamics. We use Perron cluster analysis and coarse-graining techniques in order to identify metastable sets in configuration space and approximate the transition rates between the metastable sets. Application of our method to a simple energy landscape on a two-dimensional configuration space provides proof of concept and an example for which we compare the performance of different discretizations. We show that the computational cost of our method grows only polynomially with the size of the molecule. However, finding discretizations of higher-dimensional configuration spaces in which metastable sets can be identified remains a challenge. T3 - ZIB-Report - 13-43 KW - Markov State Models KW - Markov chains KW - meshfree methods KW - metastability KW - Voronoi KW - linear programming Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42195 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika A1 - Lindner, Niels T1 - Separation of Cycle Inequalities in Periodic Timetabling N2 - Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem. T3 - ZIB-Report - 18-16 KW - Periodic timetabling KW - Cycle inequality KW - Change-cycle inequality Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69746 SN - 1438-0064 ER - TY - GEN A1 - Tateiwa, Nariaki A1 - Shinano, Yuji A1 - Yasuda, Masaya A1 - Kaji, Shizuo A1 - Yamamura, Keiichiro A1 - Fujisawa, Katsuki T1 - Massively parallel sharing lattice basis reduction N2 - 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. T3 - ZIB-Report - 21-38 KW - Discrete optimization KW - Lattice problem KW - Lattice-based cryptography KW - Shortest vector problem KW - Parallel algorithms KW - Ubiquity Generator Framework Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85209 SN - 1438-0064 N1 - under review ER - TY - GEN A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c N2 - 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. T3 - ZIB-Report - 23-27 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93072 SN - 1438-0064 ER -