TY - JOUR A1 - Lenz, Ralf A1 - Becker, Kai-Helge T1 - Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches JF - OR Spectrum N2 - In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping"). The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally. On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models. Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1007/s00291-021-00648-7 VL - 44 SP - 179 EP - 224 ER - TY - JOUR A1 - Hoppmann-Baum, Kai T1 - On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows JF - Networks N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1002/net.22060 ER - TY - JOUR A1 - Anderson, Lovis A1 - Turner, Mark A1 - Koch, Thorsten T1 - Generative deep learning for decision making in gas networks JF - Mathematical Methods of Operations Research 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%. Y1 - 2022 U6 - https://doi.org/10.1007/s00186-022-00777-x VL - 95 SP - 503 EP - 532 PB - Springer Nature ER - TY - JOUR A1 - Hennings, Felix A1 - Anderson, Lovis A1 - Hoppmann-Baum, Kai A1 - Turner, Mark A1 - Koch, Thorsten T1 - Controlling transient gas flow in real-world pipeline intersection areas JF - Optimization and Engineering 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. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s11081-020-09559-y VL - 22 SP - 687 EP - 734 PB - Springer Nature ET - 2 ER - TY - JOUR A1 - Rössig, Ansgar A1 - Petkovic, Milena T1 - Advances in Verification of ReLU Neural Networks JF - Journal of Global Optimization N2 - We consider the problem of verifying linear properties of neural networks. Despite their success in many classification and prediction tasks, neural networks may return unexpected results for certain inputs. This is highly problematic with respect to the application of neural networks for safety-critical tasks, e.g. in autonomous driving. We provide an overview of algorithmic approaches that aim to provide formal guarantees on the behavior of neural networks. Moreover, we present new theoretical results with respect to the approximation of ReLU neural networks. On the other hand, we implement a solver for verification of ReLU neural networks which combines mixed integer programming (MIP) with specialized branching and approximation techniques. To evaluate its performance, we conduct an extensive computational study. For that we use test instances based on the ACAS Xu System and the MNIST handwritten digit data set. Our solver is publicly available and able to solve the verification problem for instances which do not have independent bounds for each input neuron. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-020-00949-1 PB - Springer ER - TY - JOUR A1 - Gotzes, Uwe T1 - Ein neuer Ansatz zur Optimierung des Bilanzausgleichs in einem Gasmarktgebiet JF - Zeitschrift für Energiewirtschaft N2 - Im BDEW/VKU/GEODE-Leitfaden Krisenvorsorge Gas ist zu lesen, dass als oberster Grundsatz zur Vermeidung von Versorgungsengpässen in Gasversorgungssystemen gilt, möglichst laufend einen Bilanzausgleich in allen Teilen des Netzes zu erreichen. Wir entwickeln Modelle zur Optimierung des laufenden Bilanzausgleichs. Als Gasversorgungssystem betrachten wir modellhaft die Fernleitungsnetze eines Marktgebiets. Als Teile des Gasversorgungssystems fassen wir vereinfachend die jeweiligen Netze der Fernleitungsnetzbetreiber auf. Die Optimierung erfolgt in zwei Schritten. Im ersten Schritt wird der optimale Einsatz netzbezogener Maßnahmen ermittelt. Beispiele für netzbezogene Maßnahmen sind die Nutzung von Netzpuffer und Mengenverlagerungen mit anderen Infrastrukturbetreibern. Falls sich die Bilanzen durch netzbezogene Maßnahmen nicht vollständig ausgleichen lassen, werden Fehlmengen angesetzt, die so gleichmäßig wie möglich auf die Teile des Netzes verteilt werden. Im zweiten Schritt werden die verbliebenen Fehlmengen, welche in der Regel durch marktbezogene Maßnahmen bereinigt werden, regulierungskonform auf möglichst große Teile des Gasversorgungssystems verteilt. Im Ergebnis erhalten wir ein transparentes, gerechtes, flexibel parametrier- und erweiterbares Verfahren, welches zyklisch im Dispatchingprozess eingesetzt werden kann, um die Integrität der Netze zu unterstützen. Dies wird an Beispielen verdeutlicht. Y1 - 2019 U6 - https://doi.org/10.1007/s12398-019-00257-6 ER - TY - JOUR A1 - Chen, Ying A1 - Chua, Wee Song A1 - Koch, Thorsten T1 - Forecasting day-ahead high-resolution natural-gas demand and supply in Germany JF - Applied Energy N2 - Forecasting natural gas demand and supply is essential for an efficient operation of the German gas distribution system and a basis for the operational decisions of the transmission system operators. The German gas market is moving towards more short-term planning, in particular, day-ahead contracts. This increases the difficulty that the operators in the dispatching centre are facing, as well as the necessity of accurate forecasts. This paper presents a novel predictive model that provides day-ahead forecasts of the high resolution gas flow by developing a Functional AutoRegressive model with eXogenous variables (FARX). The predictive model allows the dynamic patterns of hourly gas flows to be described in a wide range of historical profiles, while also taking the relevant determinants data into account. By taking into account a richer set of information, FARX provides stronger performance in real data analysis, with both accuracy and high computational efficiency. Compared to several alternative models in out-of-sample forecasts, the proposed model can improve forecast accuracy by at least 12% and up to 5-fold for one node, 3% to 2-fold and 2-fold to 4-fold for the other two nodes. The results show that lagged 1-day gas flow and nominations are important predictors, and with their presence in the forecast model, temperature becomes insignificant for short-term predictions. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1016/j.apenergy.2018.06.137 IS - Volume 228 SP - 1091 EP - 1110 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 - JOUR A1 - Streubel, Tom A1 - Tischendorf, Caren A1 - Griewank, Andreas T1 - Piecewise Polynomial Taylor Expansions - The Generalization of Faà di Bruno's Formula JF - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 N2 - We present an extension of Taylor's Theorem for the piecewise polynomial expansion of non-smooth evaluation procedures involving absolute value operations. Evaluation procedures are computer programs of mathematical functions in closed form expression and allow a different treatment of smooth operations or calls to the absolute value function. The well known classical Theorem of Taylor defines polynomial approximations of sufficiently smooth functions and is widely used for the derivation and analysis of numerical integrators for systems of ordinary differential- or differential-algebraic equations, for the construction of solvers for continuous non-linear optimization of finite dimensional objective functions and for root solving of non-linear systems of equations. The long term goal is the stabilization and acceleration of already known methods and the derivation of new methods by incorporating piecewise polynomial Taylor expansions. The herein provided proof of the higher order approximation quality of the new generalized expansions is constructive and allows efficiently designed algorithms for the execution and computation of the piecewise polynomial expansions. As a demonstration towards the ultimate goal we will derive a prototype of a {\$}{\$}k{\$}{\$}k-step method on the basis of polynomial interpolation and the proposed generalized expansions. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-55240-4_3 IS - Modeling, Simulation and Optimization of Complex Processes HPSC 2018 SP - 63 EP - 82 PB - Springer International Publishing ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Hennings, Felix A1 - Zittel, Janina A1 - Gotzes, Uwe A1 - Spreckelsen, Eva-Maria A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - An Optimization Approach for the Transient Control of Hydrogen Transport Networks JF - Mathematical Methods of Operations Research Y1 - 2021 IS - Special Issue on Energy Networks ER - TY - JOUR A1 - Gotzes, Uwe A1 - Hoppmann-Baum, Kai T1 - Bounding the final rank during a round robin tournament with integer programming JF - Operational Research N2 - 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. Y1 - 2020 U6 - https://doi.org/https://doi.org/10.1007/s12351-020-00546-w VL - 1866-1505 ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Hennings, Felix A1 - Lenz, Ralf A1 - Gotzes, Uwe A1 - Heinecke, Nina A1 - Spreckelsen, Klaus A1 - Koch, Thorsten T1 - Optimal Operation of Transient Gas Transport Networks JF - Optimization and Engineering N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/s11081-020-09584-x VL - 22 SP - 735 EP - 781 ER - TY - JOUR A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Tischendorf, Caren T1 - On the abs-polynomial expansion of piecewise smooth functions JF - Optimization Methods and Software N2 - Tom Streubel has observed that for functions in abs-normal form, generalized Taylor expansions of arbitrary order $\bar d-1$ can be generated by algorithmic piecewise differentiation. Abs-normal form means that the real or vector valued function is defined by an evaluation procedure that involves the absolute value function $|...|$ apart from arithmetic operations and $\bar d$ times continuously differentiable univariate intrinsic functions. The additive terms in Streubel's expansion are abs-polynomial, i.e. involve neither divisions nor intrinsics. When and where no absolute values occur, Moore's recurrences can be used to propagate univariate Taylor polynomials through the evaluation procedure with a computational effort of $\mathcal O({\bar d}^2)$, provided all univariate intrinsics are defined as solutions of linear ODEs. This regularity assumption holds for all standard intrinsics, but for irregular elementaries one has to resort to Faa di Bruno's formula, which has exponential complexity in $\bar d$. As already conjectured we show that the Moore recurrences can be adapted for regular intrinsics to the abs-normal case. Finally, we observe that where the intrinsics are real analytic the expansions can be extended to infinite series that converge absolutely on spherical domains. Y1 - 2020 U6 - https://doi.org/10.1080/10556788.2020.1817448 PB - Taylor & Francis ER - TY - JOUR A1 - Prause, Felix A1 - Hoppmann-Baum, Kai A1 - Defourny, Boris A1 - Koch, Thorsten T1 - The maximum diversity assortment selection problem JF - Mathematical Methods of Operations Research N2 - 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. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1007/s00186-021-00740-2 VL - 93 SP - 521 EP - 554 PB - Mathematical Methods of Operations Research ER - TY - JOUR A1 - Hoppmann-Baum, Kai A1 - Burdakov, Oleg A1 - Mexi, Gioni A1 - Casselgren, Carl Johan A1 - Koch, Thorsten T1 - Length-Constrained Cycle Partition with an Application to UAV Routing JF - Optimization Methods and Software N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1080/10556788.2022.2053972 ER - TY - JOUR A1 - Dell’Amico, M. A1 - Hadjidimitriou, Natalia Selini A1 - Koch, Thorsten A1 - Petkovic, Milena T1 - Forecasting Natural Gas Flows in Large Networks JF - Machine Learning, Optimization, and Big Data. MOD 2017. N2 - Natural gas is the cleanest fossil fuel since it emits the lowest amount of other remains after being burned. Over the years, natural gas usage has increased significantly. Accurate forecasting is crucial for maintaining gas supplies, transportation and network stability. This paper presents two methodologies to identify the optimal configuration o parameters of a Neural Network (NN) to forecast the next 24 h of gas flow for each node of a large gas network. In particular the first one applies a Design Of Experiments (DOE) to obtain a quick initial solution. An orthogonal design, consisting of 18 experiments selected among a total of 4.374 combinations of seven parameters (training algorithm, transfer function, regularization, learning rate, lags, and epochs), is used. The best result is selected as initial solution of an extended experiment for which the Simulated Annealing is run to find the optimal design among 89.100 possible combinations of parameters. The second technique is based on the application of Genetic Algorithm for the selection of the optimal parameters of a recurrent neural network for time series forecast. GA was applied with binary representation of potential solutions, where subsets of bits in the bit string represent different values for several parameters of the recurrent neural network. We tested these methods on three municipal nodes, using one year and half of hourly gas flow to train the network and 60 days for testing. Our results clearly show that the presented methodologies bring promising results in terms of optimal configuration of parameters and forecast error. Y1 - 2018 U6 - https://doi.org/https://doi.org/10.1007/978-3-319-72926-8_14 VL - Lecture Notes in Computer Science IS - vol 10710 SP - 158 EP - 171 ER - TY - JOUR A1 - Gotzes, Uwe A1 - Gotzes, Claudia T1 - The Jeep Problem: A Flexible MIP Formulation JF - Journal of Nepal Mathematical Society N2 - This article deals with the Jeep Problem (also known as Desert Crossing Problem), which reads as follows: An unlimited supply of fuel is available at one edge of a desert, but there is no source on the desert itself. A vehicle can carry enough fuel to go a certain distance, and it can built up its own refuelling stations. What is the minimum amount of fuel the vehicle will require in order to cross the desert? Under these mild conditions this question is answered since the 1940s. But what is the answer if the caches are restricted to certain areas or if the fuel consumption does not depend linearly on the distance travelled? To answer these and similar questions we develop and solve a flexible mixed-integer programming (MIP) model for the classical problem and enhance it with new further aspects of practical relevance. Y1 - 2018 SN - 2616-0161 VL - 1 SP - 11 EP - 17 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, René A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Mirkov, Radoslava A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets JF - Energy Systems N2 - The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor were united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations. Y1 - 2013 U6 - https://doi.org/10.1007/s12667-013-0099-8 VL - 5 IS - 3 SP - 449 EP - 473 PB - Springer Berlin Heidelberg CY - Berlin ER - TY - JOUR A1 - Humpola, Jesco A1 - Fügenschuh, Armin A1 - Koch, Thorsten T1 - Valid inequalities for the topology optimization problem in gas network design JF - OR Spectrum N2 - One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euro per km extending the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. Unfortunately, current mathematical methods are not capable of solving the arising network design problems due to their size and complexity. In this article, we will show how to apply optimization methods that can converge to a proven global optimal solution. By introducing a new class of valid inequalities that improve the relaxation of our mixed-integer nonlinear programming model, we are able to speed up the necessary computations substantially. Y1 - 2016 U6 - https://doi.org/https://doi.org/10.1007/s00291-015-0390-2 VL - 38 IS - 3 SP - 597 EP - 631 PB - Springer CY - Berlin Heidelberg ER - TY - JOUR A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Oucherif, Djamal A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schwarz, Robert T1 - GasLib - A Library of Gas Network Instances JF - Optimization Online N2 - The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57950 ER - TY - JOUR A1 - Domschke, Pia A1 - Groß, Martin A1 - Hante, Falk M. A1 - Hiller, Benjamin A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken JF - gwf - Gas+Energie Y1 - 2015 VL - 156 IS - 11 SP - 880 EP - 885 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions JF - Mathematical Programming Computation N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. Y1 - 2017 U6 - https://doi.org/10.1007/s12532-016-0114-x VL - 9 IS - 2 SP - 231 EP - 296 ER - TY - JOUR A1 - Griewank, Andreas A1 - Hasenfelder, Richard A1 - Radons, Manuel A1 - Lehmann, Lutz A1 - Streubel, Tom T1 - Integrating Lipschitzian dynamical systems using piecewise algorithmic differentiation JF - Optimization Methods and Software N2 - In this article we analyse a generalized trapezoidal rule for initial value problems with piecewise smooth right-hand side F : IR^n -> IR^n based on a generalization of algorithmic differentiation. When applied to such a problem, the classical trapezoidal rule suffers from a loss of accuracy if the solution trajectory intersects a nondifferentiability of F. The advantage of the proposed generalized trapezoidal rule is threefold: Firstly, we can achieve a higher convergence order than with the classical method. Moreover, the method is energy preserving for piecewise linear Hamiltonian systems. Finally, in analogy to the classical case we derive a third-order interpolation polynomial for the numerical trajectory. In the smooth case, the generalized rule reduces to the classical one. Hence, it is a proper extension of the classical theory. An error estimator is given and numerical results are presented. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1378653 VL - 33 SP - 1089 EP - 1107 PB - Taylor & Francis ER - TY - JOUR A1 - Griewank, Andreas A1 - Streubel, Tom A1 - Lehmann, Lutz A1 - Radons, Manuel A1 - Hasenfelder, Richard T1 - Piecewise linear secant approximation via algorithmic piecewise differentiation JF - Optimization Methods and Software N2 - It is shown how piecewise differentiable functions F : IR^n -> IR^m that are defined by evaluation programmes can be approximated locally by a piecewise linear model based on a pair of sample points \check x and \hat x. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - \check x||*||x - \hat x||). As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equalling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods. Y1 - 2017 U6 - https://doi.org/10.1080/10556788.2017.1387256 VL - 33 IS - 4-6 SP - 1108 EP - 1126 PB - Taylor & Francis ER - TY - JOUR A1 - Schweiger, Jonas A1 - Liers, Frauke T1 - A Decomposition Approach for Optimal Gas Network Extension with a Finite Set of Demand Scenarios JF - Optimization and Engineering N2 - Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on a single bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. In this work, we formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition in order to solve the arising challenging optimization tasks. In fact, each subproblem consists of a mixed-integer nonlinear optimization problem (MINLP). Valid bounds on the objective value are derived even without solving the subproblems to optimality. Furthermore, we develop heuristics that prove capable of improving the initial solutions substantially. Results of computational experiments on realistic network topologies are presented. It turns out that our method is able to solve these challenging instances to optimality within a reasonable amount of time. Y1 - 2018 VL - 19 IS - 2 SP - 297 EP - 326 PB - Springer ER - TY - JOUR A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Schweiger, Jonas T1 - A System to Evaluate Gas Network Capacities: Concepts and Implementation JF - European Journal of Operational Research N2 - In 2005 the European Union liberalized the gas market with a disruptive change and decoupled trading of natural gas from its transport. The gas is now trans- ported by independent so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer the maximum possible capacities at each entry and exit such that any resulting gas flow can be realized by the network. The revenue from selling these capacities more than one billion Euro in Germany alone, but overestimating the capacity might compromise the security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This is a report on a large project in mathematical optimization, set out to develop a new toolset for evaluating gas network capacities. The goals and the challenges as they occurred in the project are described, as well as the developments and design decisions taken to meet the requirements. Y1 - 2018 VL - 270 IS - 3 SP - 797 EP - 808 ER - TY - JOUR A1 - Humpola, Jesco A1 - Fügenschuh, Armin T1 - Convex reformulations for solving a nonlinear network design problem JF - Computational Optimization and Applications N2 - We consider a nonlinear nonconvex network design problem that arises, for example, in natural gas or water transmission networks. Given is such a network with active and passive components, that is, valves, compressors, control valves (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes in the network. The active elements are associated with costs when used. Besides flow conservation constraints in the nodes, the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is to compute a cost minimal setting of the active components and numerical values for the flow and node potentials. We examine different (convex) relaxations for a subproblem of the design problem and benefit from them within a branch-and-bound approach. We compare different approaches based on nonlinear optimization numerically on a set of test instances. Y1 - 2015 U6 - https://doi.org/10.1007/s10589-015-9756-2 VL - 62 IS - 3 SP - 717 EP - 759 PB - Springer US ER - TY - JOUR A1 - Humpola, Jesco A1 - Serrano, Felipe T1 - Sufficient pruning conditions for MINLP in gas network design JF - EURO Journal on Computational Optimization N2 - One-quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology optimization problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. We offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations. Y1 - 2017 U6 - https://doi.org/10.1007/s13675-016-0077-8 VL - 5 IS - 1-2 SP - 239 EP - 261 PB - Springer Berlin Heidelberg ER - TY - JOUR A1 - Schmidt, Martin A1 - Assmann, Denis A1 - Burlacu, Robert A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Kanelakis, Nikolaos A1 - Koch, Thorsten A1 - Oucherif, Djamal A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Sirvent, Matthias T1 - GasLib – A Library of Gas Network Instances JF - Data Y1 - 2017 U6 - https://doi.org/10.3390/data2040040 VL - 2 IS - 4 ER - TY - JOUR A1 - Humpola, Jesco A1 - Lehmann, Thomas A1 - Fügenschuh, Armin T1 - A primal heuristic for optimizing the topology of gas networks based on dual information JF - EURO Journal on Computational Optimization N2 - We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP. Y1 - 2015 U6 - https://doi.org/10.1007/s13675-014-0029-0 VL - 3 IS - 1 SP - 53 EP - 78 ER - TY - JOUR A1 - Kickhöfer, Benjamin A1 - Kern, Julia T1 - Pricing local emission exposure of road traffic: An agent-based approach JF - Transportation Research Part D: Transport and Environment N2 - This paper proposes a new approach to iteratively calculate local air pollution exposure tolls in large-scale urban settings by taking the exposure times and locations of individuals into consideration. It explicitly avoids detailed air pollution concentration calculations and is therefore characterized by little data requirements, reasonable computation times for iterative calculations, and open-source compatibility. In a first step, the paper shows how to derive time-dependent vehicle-specific exposure tolls in an agent-based model. It closes the circle from the polluting entity, to the receiving entity, to damage costs, to tolls, and back to the behavioral change of the polluting entity. In a second step, the approach is applied to a large-scale real-world scenario of the Munich metropolitan area in Germany. Changes in emission levels, exposure costs, and user benefits are calculated. These figures are compared to a flat emission toll, and to a regulatory measure (a speed reduction in the inner city), respectively. The results indicate that the flat emission toll reduces overall emissions more significantly than the exposure toll, but its exposure cost reductions are rather small. For the exposure toll, overall emissions increase for freight traffic which implies a potential conflict between pricing schemes to optimize local emission exposure and others to abate climate change. Regarding the mitigation of exposure costs caused by urban travelers, the regulatory measure is found to be an effective strategy, but it implies losses in user benefits. Y1 - 2015 U6 - https://doi.org/10.1016/j.trd.2015.04.019 VL - 37 SP - 14 EP - 28 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in presolving for mixed integer programming JF - Mathematical Programming Computation N2 - This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems. Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0083-5 VL - 7 IS - 4 SP - 367 EP - 398 ER -