TY - THES A1 - Masing, Berenike T1 - Optimal Line Planning in the Parametric City N2 - One of the fundamental steps in the optimization of public transport is line planning. It involves determining lines and assigning frequencies of service such that costs are minimized while also maximizing passenger comfort and satisfying travel demands. We formulate the problem as a mixed integer linear program that considers all circuit-like lines in a graph and allows free passenger routing. Traveler and operator costs are included in a linear scalarization in the objective. We apply said programming problem to the Parametric City, which is a graph model introduced by Fielbaum, Jara-Díaz and Gschwender that exibly represents different cities. In his dissertation, Fielbaum solved the line planning problem for various parameter choices in the Parametric City. In a first step, we therefore review his results and make comparative computations. Unlike Fielbaum we arrive at the conclusion that the optimal line plan for this model indeed depends on the demand. Consequently, we analyze the line planning problem in-depth: We find equivalent, but easier to compute formulations and provide a lower bound by LP-relaxation, which we show to be equivalent to a multi-commodity flow problem. Further, we examine what impact symmetry has on the solutions. Supported both by computational results as well as by theoretical analysis, we reach the conclusion that symmetric line plans are optimal or near-optimal in the Parametric City. Restricting the model to symmetric line plans allows for a \kappa-factor approximation algorithm for the line planning problem in the Parametric City. Y1 - 2020 ER - TY - THES A1 - Lange, Johanna T1 - A Decomposition and Dualization Approach to the Periodic Event Scheduling Problem N2 - Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, für gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschränkungen, die zu erfüllen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrplänen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabläufen. Mathematisch können diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur Lösung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zunächst die notwendigen graphentheoretischen Grundlagen und das PESP eingeführt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Dafür ist eine weitere Nebenbedingung nötig. Im fünften Kapitel behandeln wir die Lösung des teildualisierten PESP. Eine Möglichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschränken. Eine weitere Möglichkeit ist ein Algorithmus, derähnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet. Y1 - 2021 ER - TY - THES A1 - Kühner, Arno T1 - Shortest Paths with Boolean Constraints N2 - For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen. Y1 - 2021 ER - TY - THES A1 - Bortoletto, Enrico T1 - The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm N2 - We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem. Y1 - 2021 ER - TY - THES A1 - Kraus, Luitgard T1 - A Label Setting Multiobjective Shortest Path FPTAS N2 - Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants. Y1 - 2021 ER - TY - THES A1 - Rahmati, Niloofar T1 - Resource Constrained APSP-Algorithm with Possible Reloading Stops Y1 - 2021 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 - Hosoda, Junko A1 - Maher, Stephen J. A1 - Shinano, Yuji A1 - Villumsen, Jonas Christoffer T1 - A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network N2 - 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. T3 - ZIB-Report - 23-02 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89700 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 - Sagnol, Guillaume T1 - Picos Documentation. Release 0.1.1. N2 - PICOS is a user friendly interface to several conic and integer programming solvers, very much like YALMIP under MATLAB. The main motivation for PICOS is to have the possibility to enter an optimization problem as a high level model, and to be able to solve it with several different solvers. Multidimensional and matrix variables are handled in a natural fashion, which makes it painless to formulate a SDP or a SOCP. This is very useful for educational purposes, and to quickly implement some models and test their validity on simple examples. Furthermore, with PICOS you can take advantage of the python programming language to read and write data, construct a list of constraints by using python list comprehensions, take slices of multidimensional variables, etc. T3 - ZIB-Report - 12-48 KW - mathematical programming KW - SDP KW - SOCP KW - python Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17396 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 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. T3 - ZIB-Report - 16-41 KW - Steiner tree problem KW - SCIP-Jack KW - Steiner tree variants KW - maximum-weight connected subgraph KW - prize-collecting Steiner tree Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60170 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack. T3 - ZIB-Report - 16-47 KW - Steiner tree problems KW - reduction techniques KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60420 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 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite N2 - SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. T3 - ZIB-Report - 16-64 KW - SCIP, Mathematical optimization, Python, Modeling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61348 SN - 1438-0064 ER -