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 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c 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. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult. T3 - ZIB-Report - 23-27 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93072 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Implications, Conflicts, and Reductions for Steiner Trees JF - Mathematical Programming Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01757-5 VL - 197 SP - 903 EP - 966 PB - Springer ER - TY - THES A1 - Kunt, Tim T1 - The n-Queens Problem in Higher Dimensions N2 - How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We provide a comprehensive overview of theoretical results, bounds, solution methods, and the interconnectivity of the problem within topics of discrete optimization and combinatorics. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15-70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. We conclude with preliminary results on the number and density of the solutions. T3 - ZIB-Report - 24-05 KW - Integer Programming KW - Maximum Independent Set KW - n-Queens Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-96468 ER - TY - GEN A1 - Cao, Karl-Kien A1 - Anderson, Lovis A1 - Böhme, Aileen A1 - Breuer, Thomas A1 - Buschmann, Jan A1 - Fiand, Frederick A1 - Frey, Ulrich A1 - Fuchs, Benjamin A1 - Kempe, Nils-Christian A1 - von Krbek, Kai A1 - Medjroubi, Wided A1 - Riehm, Judith A1 - Sasanpour, Shima A1 - Simon, Sonja A1 - Vanaret, Charlie A1 - Wetzel, Manuel A1 - Xiao, Mengzhu A1 - Zittel, Janina T1 - Evaluation of Uncertainties in Linear-Optimizing Energy System Models - Compendium T2 - DLR-Forschungsbericht N2 - Für die Energiesystemforschung sind Software-Modelle ein Kernelement zur Analyse von Szenarien. Das Forschungsprojekt UNSEEN hatte das Ziel eine bisher unerreichte Anzahl an modellbasierten Energieszenarien zu berechnen, um Unsicherheiten – vor allem unter Nutzung linear optimierender Energiesystem-Modelle - besser bewerten zu können. Hierfür wurden umfangreiche Parametervariationen auf Energieszenarien angewendet und das wesentliche methodische Hindernis in diesem Zusammenhang adressiert: die rechnerische Beherrschbarkeit der zu lösenden mathematischen Optimierungsprobleme. Im Vorläuferprojekt BEAM-ME wurde mit der Entwicklung und Anwendung des Open-Source-Lösers PIPS-IPM++ die Grundlage für den Einsatz von High-Performance-Computing (HPC) zur Lösung dieser Modelle gelegt. In UNSEEN war dieser Löser die zentrale Komponente eines Workflows, welcher zur Generierung, Lösung und multi-kriteriellen Bewertung von Energieszenarien auf dem Hochleistungscomputer JUWELS am Forschungszentrum Jülich implementiert wurde. Zur effizienten Generierung und Kommunikation von Modellinstanzen für Methoden der mathematischen Optimierung auf HPC wurde eine weitere Workflow-Komponente von der GAMS Software GmbH entwickelt: der Szenariogenerator. Bei der Weiterentwicklung von Lösungsalgorithmen für linear optimierende Energie-Systemmodelle standen gemischt-ganzzahlige Optimierungsprobleme im Fokus, welche für die Modellierung konkreter Infrastrukturen und Maßnahmen zur Umsetzung der Energiewende gelöst werden müssen. Die in diesem Zusammenhang stehenden Arbeiten zur Entwicklung von Algorithmen wurden von der Technischen Universität Berlin verantwortet. Bei Design und Implementierung dieser Methoden wurde sie vom Zuse Instituts Berlin unterstützt. Y1 - 2023 U6 - https://doi.org/10.57676/w2rq-bj85 IS - DLR-FB-2023-15 ER - TY - JOUR A1 - Pedersen, Jaap A1 - Spreckelsen, Klaus A1 - Gotzes, Uwe A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Beimischung von Wasserstoff zum Erdgas: Eine Kapazitätsstudie des deutschen Gasnetzes JF - 3R – Fachzeitschrift für Rohrleitungssystem N2 - Die europäische Gasinfrastruktur wird disruptiv in ein zukünftiges dekarbonisiertes Energiesystem verändert; ein Prozess, der angesichts der jüngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, trägt zur Erhöhung der öffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Fachbeitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualität analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten genügend Kapazität bietet, um für einen großen Teil der bis 2030 geplanten Erzeugungskapazität für grünen Wasserstoff als garantierter Abnehmer zu dienen. Y1 - 2023 IS - 06/2023 SP - 70 EP - 75 ER - TY - JOUR A1 - Pedersen, Jaap A1 - Spreckelsen, Klaus A1 - Gotzes, Uwe A1 - Zittel, Janina A1 - Koch, Thorsten T1 - Beimischung von Wasserstoff zum Erdgas: Eine Kapazitätsstudie des deutschen Gasnetzes T1 - Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid JF - gwf Gas + Energie N2 - Die europaische Gasinfrastruktur wird disruptiv in ein zukunftiges dekarbonisiertes Energiesystem verändert; ein Prozess, der angesichts der jüngsten politischen Situation beschleunigt werden muss. Mit einem wachsenden Wasserstoffmarkt wird der pipelinebasierte Transport unter Nutzung der bestehenden Erdgasinfrastruktur wirtschaftlich sinnvoll, trägt zur Erhöhung der öffentlichen Akzeptanz bei und beschleunigt den Umstellungsprozess. In diesem Beitrag wird die maximal technisch machbare Einspeisung von Wasserstoff in das bestehende deutsche Erdgastransportnetz hinsichtlich regulatorischer Grenzwerte der Gasqualität analysiert. Die Analyse erfolgt auf Basis eines transienten Tracking-Modells, das auf dem allgemeinen Pooling-Problem einschließlich Linepack aufbaut. Es zeigt sich, dass das Gasnetz auch bei strengen Grenzwerten gen ̈ugend Kapazität bietet, um für einen großen Teil der bis 2030 geplanten Erzeugungskapazität für grünen Wasserstoff als garantierter Abnehmer zu dienen. N2 - The European gas infrastructure is being disruptively transformed into a future decarbonised energy system; a process that needs to be accelerated given the recent political situation. With a growing hydrogen market, pipeline-based transport using the existing natural gas infrastructure becomes economically viable, helps to increase public acceptance and accelerates the transition process. In this paper, the maximum technically feasible feed-in of hydrogen into the existing German natural gas transport network is analysed with regard to regulatory limits of gas quality. Analysis is based on a transient tracking model that builds on the general pooling problem including linepack. It is shown that even with strict limits, the gas grid offers sufficient capacity to serve as a guaranteed customer for a large part of the green hydrogen generation capacity planned until 2030. Y1 - 2023 PB - Vulkan Verlag ET - 06/2023 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - Faster exact solution of sparse MaxCut and QUBO problems JF - Mathematical Programming Computation N2 - The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality. Y1 - 2023 U6 - https://doi.org/10.1007/s12532-023-00236-6 VL - 15 SP - 445 EP - 470 ER - TY - JOUR A1 - Le, Thi Thai A1 - Koch, Thorsten T1 - Effect of inertia force on the interface stability of a tangential-velocity discontinuity in porous media JF - International Journal of Multiphase Flow N2 - The present study investigates the stability of a tangential-velocity discontinuity in porous media during the withdrawing and injecting processes of natural gases from and into an underground gas storage. The focus is placed on analyzing the impact of inertia forces on the interface stability using the Forchheimer equations. Other publications have relied primarily on Darcy's law to describe flow stability in porous media. However, Darcy's law only adequately describes flows in which viscous forces dominate over inertia forces. As the flow rate increases, the significance of inertia forces becomes more pronounced, and Darcy's law becomes insufficient for considering such flows. Our findings indicate that even a slight consideration of the inertia effect leads to permanent destabilization of the discontinuity interface, regardless of the fluid viscosity or the Mach number. In contrast, when the inertia effect is neglected, the interface is stabilized across the entire Mach number range if the fluid viscosity is strong enough. Y1 - 2023 U6 - https://doi.org/10.1016/j.ijmultiphaseflow.2023.104612 VL - 169 ER - TY - JOUR A1 - Chen, Ying A1 - Koch, Thorsten A1 - Zakiyeva, Nazgul A1 - Liu, Kailiang A1 - Xu, Zhitong A1 - Chen, Chun-houh A1 - Nakano, Junji A1 - Honda, Keisuke T1 - Article’s scientific prestige: Measuring the impact of individual articles in the web of science JF - Journal of Informetrics N2 - We performed a citation analysis on the Web of Science publications consisting of more than 63 million articles and 1.45 billion citations on 254 subjects from 1981 to 2020. We proposed the Article’s Scientific Prestige (ASP) metric and compared this metric to number of citations (#Cit) and journal grade in measuring the scientific impact of individual articles in the large-scale hierarchical and multi-disciplined citation network. In contrast to #Cit, ASP, that is computed based on the eigenvector centrality, considers both direct and indirect citations, and provides steady-state evaluation cross different disciplines. We found that ASP and #Cit are not aligned for most articles, with a growing mismatch amongst the less cited articles. While both metrics are reliable for evaluating the prestige of articles such as Nobel Prize winning articles, ASP tends to provide more persuasive rankings than #Cit when the articles are not highly cited. The journal grade, that is eventually determined by a few highly cited articles, is unable to properly reflect the scientific impact of individual articles. The number of references and coauthors are less relevant to scientific impact, but subjects do make a difference. Y1 - 2023 U6 - https://doi.org/10.1016/j.joi.2023.101379 VL - 17 IS - 1 SP - 101379 ER -