TY - CHAP A1 - Shinano, Yuji A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019 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 parallel 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 benchmark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been considerably 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. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-19212-9_35 VL - 11494 SP - 529 EP - 539 PB - Springer ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Hobbie, Hannes A1 - Schönheit, David A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Möst, Dominik T1 - A massively parallel interior-point solver for linear energy system models with block structure N2 - Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market clearing. It has been widely applied in the literature on energy system analyses during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models. T3 - ZIB-Report - 19-41 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74321 SN - 1438-0064 N1 - In the meantime, this report got published as a journal article: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/searchtype/authorsearch/author/Hannes+Hobbie/docId/8191/start/1/rows/10 Please use this journal reference when citing this work. ER - TY - GEN A1 - Gleixner, Ambros A1 - Kempke, Nils-Christian A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Uslu, Svenja T1 - First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method N2 - In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix. T3 - ZIB-Report - 19-39 KW - block structure KW - energy system models KW - interior-point method KW - high performance computing KW - linear programming KW - parallelization KW - presolving KW - preprocessing Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74084 SN - 1438-0064 ER - TY - JOUR A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Fiand, Frederik A1 - Cao, Karl-Kiên A1 - Gils, Hans Christian A1 - Wetzel, Manuel A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Khabi, Dmitry T1 - BEAM-ME: Ein interdisziplinärer Beitrag zur Erreichung der Klimaziele JF - OR-News : das Magazin der GOR Y1 - 2019 IS - 66 SP - 6 EP - 8 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming JF - Journal of Computational Mathematics N2 - The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP. Y1 - 2019 U6 - https://doi.org/10.4208/jcm.1905-m2019-0055 VL - 37 SP - 866 EP - 888 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem JF - SIAM Journal on Optimization N2 - Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced. Y1 - 2019 U6 - https://doi.org/10.1137/17M1145963 VL - 29 IS - 1 SP - 369 EP - 398 PB - Society for Industrial and Applied Mathematics ER - TY - GEN A1 - Behrens, Kathrin A1 - Bertelmann, Roland A1 - Boltze, Julia A1 - Ceynowa, Klaus A1 - Christof, Jürgen A1 - Dierkes, Thomas A1 - Goltz-Fellgiebel, Julia Alexandra A1 - Groß, Matthias A1 - Hammerl, Michaela A1 - Haoua, Marsa A1 - Heermann, Petra A1 - Hoffmann, Cornelia A1 - Höhnow, Tobias A1 - Koch, Thorsten A1 - Kuberek, Monika A1 - Pampel, Heinz A1 - Putnings, Markus A1 - Rusch, Beate A1 - Schäffler, Hildegard A1 - Schwidder, Jens A1 - Söllner, Konstanze A1 - Staub, Hedda A1 - Wannick, Eike T1 - DeepGreen - Open Access Transformation: Eine Handreichung für institutionelle Repositorien BT - Version 1.0 N2 - Mit dem DFG-geförderten Projekt DeepGreen soll eine automatisierte, rechtssichere Lösung entwickelt werden, um Artikeldaten von wissenschaftlichen Verlagen abzuholen und anschließend, nach Ablauf etwaiger lizenzrechtlicher Embargofristen, an berechtigte Repositorien zu verteilen und somit in den Open Access zu überführen. Dabei liegt der Fokus auf den DFG-geförderten und überregional verhandelten Allianz-Lizenzen, mit spezieller Open-Access-Komponente. Die vorliegende Handreichung richtet sich speziell an die Betreiber institutioneller Repositorien und stellt Empfehlungen und einen Workflow bereit, um eine erfolgreiche Veröffentlichung, der durch die DeepGreen-Datendrehscheibe zugeordneten Artikel, zu ermöglichen. Die Handreichung basiert auf den bisherigen Erfahrungen der DeepGreen-Projektbeteiligten. T3 - ZIB-Report - 19-31 KW - Open Access KW - Open-Access-Transformation Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74438 SN - 1438-0064 ER - TY - GEN A1 - Chen, Ying A1 - Koch, Thorsten A1 - Xu, Xiaofei T1 - Regularized partially functional autoregressive model with application to high-resolution natural gas forecasting in Germany N2 - We propose a partially functional autoregressive model with exogenous variables (pFAR) to describe the dynamic evolution of the serially correlated functional data. It provides a unit� ed framework to model both the temporal dependence on multiple lagged functional covariates and the causal relation with ultrahigh-dimensional exogenous scalar covariates. Estimation is conducted under a two-layer sparsity assumption, where only a few groups and elements are supposed to be active, yet without knowing their number and location in advance. We establish asymptotic properties of the estimator and investigate its unite sample performance along with simulation studies. We demonstrate the application of pFAR with the high-resolution natural gas flows in Germany, where the pFAR model provides insightful interpretation as well as good out-of-sample forecast accuracy. T3 - ZIB-Report - 19-34 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74880 SN - 1438-0064 ER - TY - JOUR 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 JF - Networks 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. Y1 - 2019 U6 - https://doi.org/10.1002/net.21857 VL - 73 SP - 206 EP - 233 PB - Wiley ET - 2 ER - TY - GEN A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas N2 - Compressor stations are the heart of every high-pressure gas transport network. Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network. Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner. As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area. Since the desired performance of the station changes over time, the configuration of the station has to adapt. Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario. This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge. By presenting extensive computational results on real world data we demonstrate the performance of our approach. T3 - ZIB-Report - 19-24 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73645 SN - 1438-0064 ER -