TY - THES A1 - Jeschke, Björn-Marcel T1 - Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung N2 - In dieser Arbeit betrachten wir das Problem, für den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnhöfen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen“ Graphen modelliert werden. Es gibt zwei unterschiedliche Ansätze für dieses zeitabhängige Problem: Erstens können die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien“ dargestellt werden, das ist das zeit-expandierte Modell. Zweitens können die Gewichte der Kanten zeitabhängig sein, das ist das zeitabhängige Modell. Wir untersuchen in dieser Arbeit, wie der „klassische“ Dijkstra-Algorithmus und der A* Algorithmus mit einer geeigneten Heuristik im Vergleich abschneiden. Die gewählte Heuristik ist der Abstand zum Zielknoten, wenn die Abfahrtszeiten ignoriert werden. Nach unseren Untersuchungen zeigt sich, dass der A* Algorithmus dem Dijkstra-Algorithmus weit überlegen ist für genügend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gewählte Heuristik besonders gut ist für Start- und Zielknoten, welche unabhängig von ihrer Distanz nur 1–2 verschiedene mögliche kürzeste Pfade für alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht häufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus. Y1 - 2017 ER - TY - THES A1 - Euler, Ricardo T1 - The Bienstock Zuckerberg Algorithm for the Rolling Stock Rotation Problem N2 - The design of rolling stock rotations is an important task in large-scale railway planning. This so-called rolling stock rotation problem (RSRP) is usually tackled using an integer programming approach. Markus Reuther did so in his dissertation [15] for the ICE railway network of DB ("Deutsche Bahn"). Due to the size of the network and the complexity of further technical requirements, the resulting integer problems tend to become very large and computationally involved. In this thesis, we tackle the linear programming relaxation of the RSRP integer program. We will do so by applying a modified version of an algorithm recently proposed by Dan Bienstock and Mark Zuckerberg [2] for the precedence constrained production scheduling problem that arises in open pit mine scheduling. This problem contains a large number of "easy" constraints and a relatively small number of "hard" constraints. We will see that a similar problem structure can also be found in the RSRP. The Bienstock-Zuckerberg algorithm relies on applying Lagrangian relaxation to the hard constraints as well as on partitioning the variable set. We propose three different partition schemes which try to exploit the specific problem structure of the RSRP. Furthermore, we will discuss the influence of primal degeneracy on the algorithm's performance, as well as possible merits of perturbating the right-hand side of the constraint matrix. We provide computational results to assess the performance of those approaches. Y1 - 2018 ER - TY - THES A1 - Wirsching, Marie T1 - Der Einfluss von Langzahlarithmetik auf das Gewichtsraumpolyeder in mehrkriterieller Optimierung N2 - Die Arbeit befasst sich mit einem gewichtsraumbasierten Algorithmus, der ganzzahlige und lineare Optimierungsprobleme mit mehreren Zielfunktionen löst und die Menge der unterstützt nicht dominierten Punkte ermittelt. Die dabei erzeugten Gewichtsraumpolyeder sind das entscheidende Mittel, um die gesuchte Lösungsmenge zu bestimmen. Aus softwaretechnischer Sicht sind numerische Ungenauigkeiten potentielle Fehlerquellen, die sich negativ auf das Endergebnis auswirken. Aus diesem Grund untersuchen wir anhand von Zuweisungs- und Rucksackinstanzen mit 3 Zielfunktionen, inwieweit der Gebrauch von Langzahlarithmetik die Gewichtsraumpolyeder und die damit verbundene Menge der unterstützt nicht dominierten Punkte beeinflusst. Y1 - 2018 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Reduction-based exact solution of prize-collecting Steiner tree problems T3 - ZIB-Report - 18-55 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70958 SN - 1438-0064 ER - TY - GEN A1 - Shinano, Yuji A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores N2 - SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB. T3 - ZIB-Report - 18-58 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71118 SN - 1438-0064 ER - TY - GEN A1 - Serrano, Felipe T1 - Intersection cuts for factorable MINLP N2 - Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables. T3 - ZIB-Report - 18-59 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71105 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 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited N2 - In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested. T3 - ZIB-Report - 20-05 KW - acyclic orientations KW - enumeration algorithm KW - multiple sources and sinks KW - bipolar orientations Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-77684 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 - Georges, Alexander A1 - Gleixner, Ambros A1 - Gojic, Gorana A1 - Gottwald, Robert Lion A1 - Haley, David A1 - Hendel, Gregor A1 - Matejczyk, Bartlomiej T1 - Feature-Based Algorithm Selection for Mixed Integer Programming N2 - Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented. T3 - ZIB-Report - 18-17 KW - algorithm selection KW - mixed integer programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68362 SN - 1438-0064 ER - TY - GEN A1 - Schiewe, Philine A1 - Goerigk, Marc A1 - Lindner, Niels T1 - Introducing TimPassLib - A library for integrated periodic timetabling and passenger routing N2 - Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing. T3 - ZIB-Report - 23-06 KW - periodic timetabling KW - optimization in public transport KW - data sets KW - benchmarking Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89741 SN - 1438-0064 ER - TY - GEN A1 - Turner, Mark A1 - Berthold, Timo A1 - Besançon, Mathieu A1 - Koch, Thorsten T1 - Cutting Plane Selection with Analytic Centers and Multiregression N2 - Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method. T3 - ZIB-Report - 22-28 KW - cut selection KW - anlalytic center KW - mixed-integer programming Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89065 SN - 1438-0064 ER - TY - GEN A1 - Kempke, Nils-Christian A1 - Kunt, Tim A1 - Katamish, Bassel A1 - Vanaret, Charlie A1 - Sasanpour, Shima A1 - Clarner, Jan-Patrick A1 - Koch, Thorsten T1 - Developing heuristic solution techniques for large-scale unit commitment models N2 - Shifting towards renewable energy sources and reducing carbon emissions necessitate sophisticated energy system planning, optimization, and extension. Energy systems optimization models (ESOMs) often form the basis for political and operational decision-making. ESOMs are frequently formulated as linear (LPs) and mixed-integer linear (MIP) problems. MIPs allow continuous and discrete decision variables. Consequently, they are substantially more expressive than LPs but also more challenging to solve. The ever-growing size and complexity of ESOMs take a toll on the computational time of state-of-the-art commercial solvers. Indeed, for large-scale ESOMs, solving the LP relaxation -- the basis of modern MIP solution algorithms -- can be very costly. These time requirements can render ESOM MIPs impractical for real-world applications. This article considers a set of large-scale decarbonization-focused unit commitment models with expansion decisions based on the REMix framework (up to 83 million variables and 900,000 discrete decision variables). For these particular instances, the solution to the LP relaxation and the MIP optimum lie close. Based on this observation, we investigate the application of relaxation-enforced neighborhood search (RENS), machine learning guided rounding, and a fix-and-propagate (FP) heuristic as a standalone solution method. Our approach generated feasible solutions 20 to 100 times faster than GUROBI, achieving comparable solution quality with primal-dual gaps as low as 1% and up to 35%. This enabled us to solve numerous scenarios without lowering the quality of our models. For some instances that Gurobi could not solve within two days, our FP method provided feasible solutions in under one hour. T3 - ZIB-Report - 25-03 KW - Energy system optimization models KW - Unit commitment KW - Mixed-integer programming KW - Large-scale optimization KW - Primal heuristics Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99555 SN - 1438-0064 ER -