Dokument-ID Dokumenttyp Verfasser/Autoren Herausgeber Haupttitel Abstract Auflage Verlagsort Verlag Erscheinungsjahr Seitenzahl Schriftenreihe Titel Schriftenreihe Bandzahl ISBN Quelle der Hochschulschrift Konferenzname Quelle:Titel Quelle:Jahrgang Quelle:Heftnummer Quelle:Erste Seite Quelle:Letzte Seite URN DOI Abteilungen OPUS4-6719 Konferenzveröffentlichung Hoppmann, Kai; Schwarz, Robert Finding Maximum Minimum Cost Flows to Evaluate Gas Network Capacities In this article we consider the following problem arising in the context of scenario generation to evaluate the transport capacity of gas networks: In the Uncapacitated Maximum Minimum Cost Flow Problem (UMMCF) we are given a flow network where each arc has an associated nonnegative length and infinite capacity. Additionally, for each source and each sink a lower and an upper bound on its supply and demand are known, respectively. The goal is to find values for the supplies and demands respecting these bounds, such that the optimal value of the induced Minimum Cost Flow Problem is maximized, i.e., to determine a scenario with maximum transportmoment. In this article we propose two linear bilevel optimization models for UMMCF, introduce a greedy-style heuristic, and report on our first computational experiment. 2018 7 Operations Research Proceedings 2017 978-3-319-89919-0 339 346 10.1007/978-3-319-89920-6_46 Mathematical Optimization OPUS4-7363 misc Hoppmann, Kai; Hennings, Felix; Lenz, Ralf; Gotzes, Uwe; Heinecke, Nina; Spreckelsen, Klaus; Koch, Thorsten Optimal Operation of Transient Gas Transport Networks 2019 urn:nbn:de:0297-zib-73639 Mathematical Optimization OPUS4-8104 Wissenschaftlicher Artikel Gotzes, Uwe; Hoppmann-Baum, Kai Bounding the final rank during a round robin tournament with integer programming This article is mainly motivated by the urge to answer two kinds of questions regarding the Bundesliga, which is Germany's primary football (soccer) division having the highest average stadium attendance worldwide: "At any point in the season, what is the lowest final rank a certain team can achieve?" and "At any point in the season, what is the highest final rank a certain team can achieve?". Although we focus on the Bundesliga in particular, the integer programming formulations we introduce to answer these questions can easily be adapted to a variety of other league systems and tournaments. 2020 Operational Research 1866-1505 https://doi.org/10.1007/s12351-020-00546-w Mathematical Algorithmic Intelligence OPUS4-8152 Wissenschaftlicher Artikel Hoppmann-Baum, Kai; Hennings, Felix; Zittel, Janina; Gotzes, Uwe; Spreckelsen, Eva-Maria; Spreckelsen, Klaus; Koch, Thorsten An Optimization Approach for the Transient Control of Hydrogen Transport Networks 2021 Mathematical Methods of Operations Research Special Issue on Energy Networks Mathematical Optimization Methods OPUS4-8006 Teil eines Buches Hoppmann-Baum, Kai; Mexi, Gioni; Burdakov, Oleg; Casselgren, Carl Johan; Koch, Thorsten Hebrard, Emmanuel; Musliu, Nysret Minimum Cycle Partition with Length Requirements In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances. Cham Springer International Publishing 2020 10 Integration of Constraint Programming, Artificial Intelligence, and Operations Research 12296 978-3-030-58941-7 273 282 10.1007/978-3-030-58942-4_18 Mathematical Algorithmic Intelligence OPUS4-8008 Wissenschaftlicher Artikel Hoppmann-Baum, Kai; Hennings, Felix; Lenz, Ralf; Gotzes, Uwe; Heinecke, Nina; Spreckelsen, Klaus; Koch, Thorsten Optimal Operation of Transient Gas Transport Networks In this paper, we describe an algorithmic framework for the optimal operation of transient gas transport networks consisting of a hierarchical MILP formulation together with a sequential linear programming inspired post-processing routine. Its implementation is part of the KOMPASS decision support system, which is currently used in an industrial setting. Real-world gas transport networks are controlled by operating complex pipeline intersection areas, which comprise multiple compressor units, regulators, and valves. In the following, we introduce the concept of network stations to model them. Thereby, we represent the technical capabilities of a station by hand-tailored artificial arcs and add them to network. Furthermore, we choose from a predefined set of flow directions for each network station and time step, which determines where the gas enters and leaves the station. Additionally, we have to select a supported simple state, which consists of two subsets of artificial arcs: Arcs that must and arcs that cannot be used. The goal is to determine a stable control of the network satisfying all supplies and demands. The pipeline intersections, that are represented by the network stations, were initially built centuries ago. Subsequently, due to updates, changes, and extensions, they evolved into highly complex and involved topologies. To extract their basic properties and to model them using computer-readable and optimizable descriptions took several years of effort. To support the dispatchers in controlling the network, we need to compute a continuously updated list of recommended measures. Our motivation for the model presented here is to make fast decisions on important transient global control parameters, i.e., how to route the flow and where to compress the gas. Detailed continuous and discrete technical control measures realizing them, which take all hardware details into account, are determined in a subsequent step. In this paper, we present computational results from the KOMPASS project using detailed real-world data. 2021 46 Optimization and Engineering 22 735 781 10.1007/s11081-020-09584-x Mathematical Algorithmic Intelligence OPUS4-7990 misc Hoppmann-Baum, Kai; Hennings, Felix; Zittel, Janina; Gotzes, Uwe; Spreckelsen, Eva-Maria; Spreckelsen, Klaus; Koch, Thorsten From Natural Gas towards Hydrogen - A Feasibility Study on Current Transport Network Infrastructure and its Technical Control This study examines the usability of a real-world, large-scale natural gas transport infrastructure for hydrogen transport. We investigate whether a converted network can transport the amounts of hydrogen necessary to satisfy current energy demands. After introducing an optimization model for the robust transient control of hydrogen networks, we conduct computational experiments based on real-world demand scenarios. Using a representative network, we demonstrate that replacing each turbo compressor unit by four parallel hydrogen compressors, each of them comprising multiple serial compression stages, and imposing stricter rules regarding the balancing of in- and outflow suffices to realize transport in a majority of scenarios. However, due to the reduced linepack there is an increased need for technical and non-technical measures leading to a more dynamic network control. Furthermore, the amount of energy needed for compression increases by 364% on average. 2020 urn:nbn:de:0297-zib-79901 Mathematical Algorithmic Intelligence OPUS4-8048 misc Hoppmann-Baum, Kai; Mexi, Gioni; Burdakov, Oleg; Casselgren, Carl Johan; Koch, Thorsten Length-Constrained Cycle Partition with an Application to UAV Routing 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. 2020 urn:nbn:de:0297-zib-80489 Mathematical Algorithmic Intelligence OPUS4-7335 misc Hoppmann, Kai On the Complexity of the Maximum Minimum Cost Flow Problem Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity and an associated length, together with nonempty supply-intervals for the sources and nonempty demand-intervals for the sinks. The goal of the Maximum Minimum Cost Flow Problem (MMCF) is to find fixed supply and demand values within these intervals, such that the optimal objective value of the induced Minimum Cost Flow Problem (MCF) is maximized. In this paper, we show that MMCF is APX-hard and remains NP-hard in the uncapacitated case. 2019 urn:nbn:de:0297-zib-73359 Mathematical Optimization OPUS4-8234 Wissenschaftlicher Artikel Hoppmann-Baum, Kai On the Complexity of Computing Maximum and Minimum Min-Cost-Flows Consider a flow network, i.e., a directed graph where each arc has a nonnegative capacity value and an associated length, together with nonempty supply intervals for the sources and nonempty demand intervals for the sinks. The Maximum Min-Cost-Flow Problem (MaxMCF) is to find fixed supply and demand values within these intervals such that the optimal objective value of the induced Min-Cost-Flow Problem (MCF) is maximized. In this paper, we show that MaxMCF as well as its uncapacitated variant, the Maximum Transportation Problem (MaxTP), are NP-hard. Further, we prove that MaxMCF is APX-hard if a connectedness-condition regarding the sources and the sinks of the flow network is dropped. Finally, we show how the Minimum Min-Cost-Flow Problem (MinMCF) can be solved in polynomial time. 2021 Networks 10.1002/net.22060 Mathematical Optimization OPUS4-8283 misc Pedersen, Jaap; Hoppmann-Baum, Kai; Zittel, Janina; Koch, Thorsten Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid; Technical Report In the transition towards a pure hydrogen infrastructure, utilizing the existing natural gas infrastructure is a necessity. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length. 2021 urn:nbn:de:0297-zib-82838 Applied Algorithmic Intelligence Methods OPUS4-8356 Konferenzveröffentlichung Pedersen, Jaap; Hoppmann-Baum, Kai; Zittel, Janina; Koch, Thorsten Blending hydrogen into natural gas: An assessment of the capacity of the German gas grid In the transition towards a pure hydrogen infrastructure, repurposing the existing natural gas infrastructure is considered. In this study, the maximal technically feasible injection of hydrogen into the existing German natural gas transmission network is analysed with respect to regulatory limits regarding the gas quality. We propose a transient tracking model based on the general pooling problem including linepack. The analysis is conducted using real-world hourly gas flow data on a network of about 10,000 km length. 2022 5 Operations Research Proceedings 2021 182 187 https://doi.org/10.1007/978-3-031-08623-6_28 Mathematical Algorithmic Intelligence OPUS4-8616 Wissenschaftlicher Artikel Hoppmann-Baum, Kai; Burdakov, Oleg; Mexi, Gioni; Casselgren, Carl Johan; Koch, Thorsten Length-Constrained Cycle Partition with an Application to UAV Routing This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e., a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas. 2022 Optimization Methods and Software 10.1080/10556788.2022.2053972 Energy Network Optimization OPUS4-8684 misc Hennings, Felix; Hoppmann-Baum, Kai; Zittel, Janina Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics Optimizing the transient control of gas networks is a highly challenging task. The corresponding model incorporates the combinatorial complexity of determining the settings for the many active elements as well as the non-linear and non-convex nature of the physical and technical principles of gas transport. In this paper, we present the latest improvements of our ongoing work to solve this problem for real-world, large-scale problem instances: By adjusting our mixed-integer non-linear programming model regarding the gas compression capabilities in the network, we reflect the technical limits of the underlying units more accurately while maintaining a similar overall model size. In addition, we introduce a new algorithmic approach that is based on splitting the complexity of the problem by first finding assignments for discrete variables and then determining the continuous variables as locally optimal solution of the corresponding non-linear program. For the first task, we design multiple different heuristics based on concepts for general time-expanded optimization problems that find solutions by solving a sequence of sub-problems defined on reduced time horizons. To demonstrate the competitiveness of our approach, we test our algorithm on particularly challenging historic demand scenarios. The results show that high-quality solutions are obtained reliably within short solving times, making the algorithm well-suited to be applied at the core of time-critical industrial applications. 2022 urn:nbn:de:0297-zib-86842 Mathematical Algorithmic Intelligence OPUS4-8932 Dissertation Hoppmann-Baum, Kai Mathematical programming for stable control and safe operation of gas transport networks The fight against climate change makes extreme but inevitable changes in the energy sector necessary. These in turn lead to novel and complex challenges for the transmission system operators (TSOs) of gas transport networks. In this thesis, we consider four different planning problems emerging from real-world operations and present mathematical programming models and solution approaches for all of them. Due to regulatory requirements and side effects of renewable energy production, controlling today's gas networks with their involved topologies is becoming increasingly difficult. Based on the network station modeling concept for approximating the technical capabilities of complex subnetworks, e.g., compressor stations, we introduce a tri-level MIP model to determine important global control decisions. Its goal is to avoid changes in the network elements' settings while deviations from future inflow pressures as well as supplies and demands are minimized. A sequential linear programming inspired post-processing routine is run to derive physically accurate solutions w.r.t. the transient gas flow in pipelines. Computational experiments based on real-world data show that meaningful solutions are quickly and reliably determined. Therefore, the algorithmic approach is used within KOMPASS, a decision support system for the transient network control that we developed together with the Open Grid Europe GmbH (OGE), one of Europe's largest natural gas TSOs. Anticipating future use cases, we adapt the aforementioned algorithmic approach for hydrogen transport. We investigate whether the natural gas infrastructure can be repurposed and how the network control changes when energy-equivalent amounts of hydrogen are transported. Besides proving the need for purpose-built compressors, we observe that, due to the reduced linepack, the network control becomes more dynamic, compression energy increases by 440% on average, and stricter regulatory rules regarding the balancing of supply and demand become necessary. Extreme load flows expose the technical limits of gas networks and are therefore of great importance to the TSOs. In this context, we introduce the Maximum Transportation Problem and the Maximum Potential Transport Moment Problem to determine severe transport scenarios. Both can be modeled as linear bilevel programs where the leader selects supplies and demands, maximizing the follower's transport effort. To solve them, we identify solution-equivalent instances with acyclic networks, provide variable bounds regarding their KKT reformulations, apply the big-M technique, and solve the resulting MIPs. A case study shows that the obtained scenarios exceed the maximum severity values of a provided test set by at least 23%. OGE's transmission system is 11,540km long. Monitoring it is crucial for safe operations. To this end, we discuss the idea of using uncrewed aerial vehicles and introduce the Length-Constrained Cycle Partition Problem to optimize their routing. Its goal is to find a smallest cycle partition satisfying vertex-induced length requirements. Besides a greedy-style heuristic, we propose two MIP models. Combining them with symmetry-breaking constraints as well as valid inequalities and lower bounds from conflict hypergraphs yields a highly performant solution algorithm for this class of problems. TU Berlin 2022 10.14279/depositonce-15837 Energy Network Optimization OPUS4-7499 Wissenschaftlicher Artikel Hennings, Felix; Anderson, Lovis; Hoppmann-Baum, Kai; Turner, Mark; Koch, Thorsten Controlling transient gas flow in real-world pipeline intersection areas 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. 2 Springer Nature 2021 47 Optimization and Engineering 22 687 734 https://doi.org/10.1007/s11081-020-09559-y Mathematical Optimization OPUS4-7364 misc Hennings, Felix; Anderson, Lovis; Hoppmann, Kai; Turner, Mark; Koch, Thorsten Controlling transient gas flow in real-world pipeline intersection areas 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. 2019 urn:nbn:de:0297-zib-73645 Mathematical Optimization OPUS4-8103 misc Prause, Felix; Hoppmann-Baum, Kai; Defourny, Boris; Koch, Thorsten The Maximum Diversity Assortment Selection Problem 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. 2020 urn:nbn:de:0297-zib-81039 Mathematical Algorithmic Intelligence OPUS4-7463 misc Gotzes, Uwe; Hoppmann, Kai Bounds for the final ranks during a round robin tournament This article answers two kinds of questions regarding the Bundesliga which is Germany's primary football (soccer) competition having the highest average stadium attendance worldwide. First "At any point of the season, what final rank will a certain team definitely reach?" and second "At any point of the season, what final rank can a certain team at most reach?". Although we focus especially on the Bundesliga, the models that we use to answer the two questions can easily be adopted to league systems that are similar to that of the Bundesliga. 2019 Operational Research - An International Journal (ORIJ) urn:nbn:de:0297-zib-74638 https://doi.org/10.1007/s12351-020-00546-w Mathematical Optimization OPUS4-9471 Wissenschaftlicher Artikel Hennings, Felix; Hoppmann-Baum, Kai; Zittel, Janina Optimizing transient gas network control for challenging real-world instances using MIP-based heuristics 2024 Open Journal of Mathematical Optimization Applied Algorithmic Intelligence Methods OPUS4-8007 Wissenschaftlicher Artikel Prause, Felix; Hoppmann-Baum, Kai; Defourny, Boris; Koch, Thorsten The maximum diversity assortment selection problem In this article, we introduce the Maximum Diversity Assortment Selection Problem (MDASP), which is a generalization of the two-dimensional Knapsack Problem (2D-KP). Given a set of rectangles and a rectangular container, the goal of 2D-KP 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. MDASP is 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 the minimum or average normalized Hamming distance of all assortment pairs. MDASP was the topic of the 11th AIMMS-MOPTA Competition in 2019. The methods described in this article and the resulting 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 2D-KP literature. Mathematical Methods of Operations Research 2021 33 Mathematical Methods of Operations Research 93 521 554 https://doi.org/10.1007/s00186-021-00740-2 Applied Algorithmic Intelligence Methods