TY - GEN A1 - Gamrath, Gerald A1 - Anderson, Daniel A1 - Bestuzheva, Ksenia A1 - Chen, Wei-Kun A1 - Eifler, Leon A1 - Gasse, Maxime A1 - Gemander, Patrick A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Halbig, Katrin A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Le Bodic, Pierre A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Miltenberger, Matthias A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Tawfik, Christine A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 7.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP. T3 - ZIB-Report - 20-10 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78023 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - On the exact solution of prize-collecting Steiner tree problems T3 - ZIB-Report - 20-11 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78174 SN - 1438-0064 ER - TY - CHAP 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 T2 - Operations Research Proceedings 2019 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. 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 - 2020 U6 - https://doi.org/10.1007/978-3-030-48439-2_13 SP - 105 EP - 111 PB - Springer International Publishing ET - 1 ER - TY - JOUR A1 - Chen, Ying A1 - Xu, Xiuqin A1 - Koch, Thorsten T1 - Day-ahead high-resolution forecasting of natural gas demand and supply in Germany with a hybrid model JF - Applied Energy N2 - As the natural gas market is moving towards short-term planning, accurate and robust short-term forecasts of the demand and supply of natural gas is of fundamental importance for a stable energy supply, a natural gas control schedule, and transport operation on a daily basis. We propose a hybrid forecast model, Functional AutoRegressive and Convolutional Neural Network model, based on state-of-the-art statistical modeling and artificial neural networks. We conduct short-term forecasting of the hourly natural gas flows of 92 distribution nodes in the German high-pressure gas pipeline network, showing that the proposed model provides nice and stable accuracy for different types of nodes. It outperforms all the alternative models, with an improved relative accuracy up to twofold for plant nodes and up to fourfold for municipal nodes. For the border nodes with rather flat gas flows, it has an accuracy that is comparable to the best performing alternative model. KW - Natural gas flow forecasting KW - Neural network KW - Hybrid model KW - Functional autoregressive Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1016/j.apenergy.2019.114486 VL - 262 IS - 114486 ER - TY - GEN A1 - Prause, Felix A1 - Hoppmann-Baum, Kai A1 - Defourny, Boris A1 - Koch, Thorsten T1 - The Maximum Diversity Assortment Selection Problem N2 - In this paper, we introduce the Maximum Diversity Assortment Selection Problem (MADASS), which is a generalization of the 2-dimensional Cutting Stock Problem (2CSP). Given a set of rectangles and a rectangular container, the goal of 2CSP is to determine a subset of rectangles that can be placed in the container without overlapping, i.e., a feasible assortment, such that a maximum area is covered. In MADASS, we need to determine a set of feasible assortments, each of them covering a certain minimum threshold of the container, such that the diversity among them is maximized. Thereby, diversity is defined as minimum or average normalized Hamming-Distance of all assortment pairs. The MADASS Problem was used in the 11th AIMMS-MOPTA Competition in 2019. The methods we describe in this article and the computational results won the contest. In the following, we give a definition of the problem, introduce a mathematical model and solution approaches, determine upper bounds on the diversity, and conclude with computational experiments conducted on test instances derived from the 2CSP literature. T3 - ZIB-Report - 20-34 KW - Combinatorial Optimization KW - Mixed Integer Programming KW - 2-dim Cutting Stock Problem KW - Maximum Diversity Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81039 SN - 1438-0064 ER - TY - GEN A1 - Anderson, Lovis A1 - Turner, Mark A1 - Koch, Thorsten T1 - Generative deep learning for decision making in gas networks N2 - A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. With the trained network we produce a feasible solution in 2.5s, use it as a warm-start solution, and thereby decrease global optimal solution solve time by 60.5%. T3 - ZIB-Report - 20-38 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81103 SN - 1438-0064 ER - TY - GEN A1 - Hoppmann-Baum, Kai A1 - Mexi, Gioni A1 - Burdakov, Oleg A1 - Casselgren, Carl Johan A1 - Koch, Thorsten T1 - Length-Constrained Cycle Partition with an Application to UAV Routing N2 - In this article, we discuss the Length-Constrained Cycle Partition Problem (LCCP). Besides edge weights, the undirected graph in LCCP features an individual critical weight value for each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is a feasible solution if the length of each cycle is not greater than the critical weight of each of the vertices in the cycle. The goal is to find a feasible partition with the minimum number of cycles. In this article, we discuss theoretical properties, preprocessing techniques, and two mixed-integer programming models (MIP) for LCCP both inspired by formulations for the closely related Travelling Salesperson Problem (TSP). Further, we introduce conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a report on computational experiments conducted on (A)TSPLIB-based instances. As an example, we use a routing problem in which a fleet of uncrewed aerial vehicles (UAVs) patrols a set of areas. T3 - ZIB-Report - 20-30 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-80489 SN - 1438-0064 ER - TY - JOUR A1 - Koch, Thorsten A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger T1 - Capacity Evaluation for Large-Scale Gas Networks JF - German Success Stories in Industrial Mathematics Y1 - 2020 SN - 978-3-030-81454-0 U6 - https://doi.org/10.1007/978-3-030-81455-7 VL - 35 SP - 23 EP - 28 ER - TY - JOUR A1 - Chen, Ying A1 - Zakiyeva, Nazgul A1 - Zhu, Bangzhu A1 - Koch, Thorsten T1 - Modeling and Forecasting the Dynamics of the Natural Gas Transmission Network in Germany with the Demand and Supply Balance Constraint JF - Applied Energy Y1 - 2020 U6 - https://doi.org/10.1016/j.apenergy.2020.115597 N1 - https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3646636 IS - 278 ER - TY - JOUR A1 - Koch, Thorsten A1 - Chen, Ying A1 - Lim, Kian Guan A1 - Xu, Xiaofei A1 - Zakiyeva, Nazgul T1 - A review study of functional autoregressive models with application to energy forecasting JF - WIREs Computational Statistics Y1 - 2020 U6 - https://doi.org/10.1002/wics.1525 N1 - https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=7693&context=lkcsb_research ER - TY - CHAP A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - An exact high performance solver for Steiner tree problems in graphs and related problems T2 - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 Y1 - 2020 PB - Springer ER -