@misc{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, issn = {1438-0064}, doi = {10.1109/IPDPS.2016.56}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56404}, abstract = {This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.}, language = {en} } @misc{FujiiItoKimetal., author = {Fujii, Koichi and Ito, Naoki and Kim, Sunyoung and Kojima, Masakazu and Shinano, Yuji and Toh, Kim-Chuan}, title = {Solving Challenging Large Scale QAPs}, issn = {1438-0064}, doi = {10.12752/8130}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81303}, abstract = {We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method efficiently implemented on a powerful computer system using the Ubiquity Generator(UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors' group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results. Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the first time.}, language = {en} } @misc{HillerWalther, author = {Hiller, Benjamin and Walther, Tom}, title = {Modelling compressor stations in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67443}, abstract = {Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.}, language = {en} } @misc{Shinano, author = {Shinano, Yuji}, title = {The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65545}, abstract = {Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.}, language = {en} } @misc{ShinanoRehfeldtKoch, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71118}, abstract = {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.}, language = {en} } @misc{BreuerBussieckCaoetal., author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Cebulla, Felix and Fiand, Frederik and Gils, Hans Christian and Gleixner, Ambros and Khabi, Dmitry and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_85}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66183}, abstract = {Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.}, language = {en} } @misc{BeckerHiller, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Improved optimization models for potential-driven network flow problems via ASTS orientations}, issn = {1438-0064}, doi = {10.12752/7534}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75347}, abstract = {The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks.}, language = {en} } @misc{Bushe, type = {Master Thesis}, author = {Bushe, Julian}, title = {Rolling Stock Rotation Optimization with Maintenance Paths}, abstract = {Die Planung vom Zuguml{\"a}ufen ist eine der wichtigsten Aufgaben f{\"u}r Eisenbahnun- ternehmen. Dabei spielt auch die Einhaltung von vorgegebenen Wartungsintervallen eine zentrale Rolle f{\"u}r die Sicherheit und Zuverl{\"a}ssigkeit der Schienenfahrzeuge. Wir zeigen, wie man dieses Umlaufplanungsproblem unter Beachtung von Wartungsbe- dingungen mathematisch formuliert, modelliert und l{\"o}st — sowohl in der Theorie als auch im Anwendungsfall mit Szenarien der DB Fernverkehr AG, einer Konzern- tochter der Deutschen Bahn f{\"u}r den Schienenpersonenfernverkehr. Markus Reuther hat sich in seiner Dissertation [11] mit diesem Problem besch{\"a}ftigt und es mit Hilfe eines passenden Hypergraphen als gemischt-ganzzahliges Programm modelliert. Neben der Modellierung pr{\"a}sentiert Reuther in seiner Arbeit neuartige algorithmische Ideen, darunter den sogenannten Coarse-to-Fine -Ansatz, bei dem zun{\"a}chst Teile des Problems auf einer weniger detaillierten ( coarse ) Ebene gel{\"o}st werden und diese L{\"o}sung dann verwendet wird, um auf effiziente Art und Weise eine L{\"o}sung f{\"u}r das urspr{\"u}ngliche Problem zu finden. Zur Wartungsplanung nutzt Reuther einen Fluss im Hypergraphen, der den Ressourcenverbrauch der Fahrzeuge modelliert. In der linearen Relaxierung des Modells f{\"u}hrt dies dazu, dass die Zahl der notwendigen Wartungen systematisch untersch{\"a}tzt wird. Dadurch bleibt in vielen F{\"a}llen eine große L{\"u}cke zwischen dem Zielfunktionswert einer optimalen L{\"o}sung des ganzzahligen Problems und der untere Schranke, die uns die lineare Relaxierung liefert. Wir nehmen uns in dieser Arbeit dieses Problems an. Wir entwickeln ein auf Pfaden basierendes ganzzahliges Modell f{\"u}r das Umlaufplanungsproblem und zeigen, dass die untere Schranke mindestens so scharf oder sch{\"a}rfer ist als die untere Schranke, die das Modell von Reuther liefert. Um das Modell zu l{\"o}sen, entwickeln wir einen Algorithmus, der Spaltengenerierung mit dem Coarse-to-Fine-Ansatz von Reuther verbindet. Weiterhin entwickeln wir eine Spaltenauswahlregel zur Beschleunigung des Algorithmus. Das Modell und alle in der Arbeit vorgestellten Algorithmen wur- den im Rahmen der Arbeit implementiert und mit Anwendungsszenarien der DB Fernverkehr AG getestet. Unsere Tests zeigen, dass unser Modell f{\"u}r fast alle Szena- rien deutlich sch{\"a}rfere untere Schranken liefert als das Modell von Reuther. In den getesteten Instanzen konnten wir durch die Verbesserung der unteren Schranke bis zu 99\% der Optimalit{\"a}tsl{\"u}cke schließen. In einem Drittel der F{\"a}lle konnten wir durch unseren Ansatz auch f{\"u}r das ganzzahlige Programm verbesserte Zielfunktionswerte erreichen}, language = {en} } @misc{Henning, type = {Master Thesis}, author = {Henning, Erin}, title = {Tropical Geometry Approach to Shortest Paths with Parameterized Arc Weights - A Case Study in Public Transportation Networks}, abstract = {In graphical representations of public transportation networks, there is often some degree of uncertainty in the arc values, due to delays or transfer times. This uncertainty can be expressed as a parameterized weight on the transfer arcs. Classical shortest path algorithms often have difficulty handling parameterized arc weights and a tropical geometry approach has been shown as a possible solution. The connection between the classical shortest path problem and tropical geometry is well establish: Tropically multiplying the n × n adjacency matrix of a graph with itself n - 1 times results in the so-called Kleene star, and is a matrix-form solution to the all-pairs shortest path problem. Michael Joswig and Benjamin Schr{\"o}ter showed in their paper The Tropical Geometry of Shortest Paths that the same method can be used to find the solution to the all-pairs shortest path problem even in the case of variable arc weights and they proposed an algorithm to solve the single-target shortest path problem in such a case. The solution takes the form of a polyhedral subdivision of the parameter space. As the number of variable arc weights grows, the time needed to execute an implementation of this algorithm grows exponentially. As the size of a public transportation network grows, the number of variable arc weights grows exponentially as well. However, it has been observed that in public transportation networks, there are usually only a few possible shortest routes. Geometrically, this means that there should be few polyhedra in the polyhedral subdivision. This algorithm is used on an example of a real-world public transportation network and an analysis of the polyhedral subdivision is made. Then a geometrical approach is used to analyze the impact of limiting the number of transfers, and thereby limiting the number of parameterized arcs used, as an estimation of the solution to the all-pairs shortest path problem}, language = {en} } @misc{Masing, type = {Master Thesis}, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, abstract = {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{\´i}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.}, language = {en} }