Refine
Document Type
- Article (9)
- ZIB-Report (5)
- Book chapter (2)
- Book (1)
- In Proceedings (1)
Keywords
- Mixed Integer Programming (2)
- 2-dim Cutting Stock Problem (1)
- CO2 Transport (1)
- Combinatorial Optimization (1)
- Energiewende (1)
- Hydrogen Infrastructure (1)
- Hydrogen Transport (1)
- Maximum Diversity Problem (1)
- Network Design (1)
- Network Flows (1)
Institute
- Mathematical Algorithmic Intelligence (18) (remove)
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.
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.
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.
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.
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%.
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%.
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.
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.
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.
While energy-intensive industries like the steel industry plan to switch to renewable energy sources, other industries, such as the cement industry, have to rely on carbon capture storage and utilization technologies to reduce the inevitable carbon dioxide (CO2) emissions of their production processes. In this context, we investigate the problem of finding optimal pipeline diameters from a discrete set of diameters for a tree-shaped network transporting captured CO2 from multiple sources to a single sink.
The general problem of optimizing arc capacities in potential-based fluid networks is a challenging mixed-integer nonlinear program. Additionally, the behaviour of CO2 is highly sensitive and nonlinear regarding temperature and pressure changes. We propose an iterative algorithm splitting the problem into two parts: a) the pipe-sizing problem under a fixed supply scenario and temperature distribution and b) the thermophysical modelling including mixing effects, the Joule-Thomson effect, and heat exchange with the surrounding environment. We show the effectiveness of our approach by applying our algorithm to a real-world network planning problem for a CO2 network in Western Germany.
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.
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.