@book{KochHillerPfetschetal., author = {Koch, Thorsten and Hiller, Benjamin and Pfetsch, Marc and Schewe, Lars}, title = {Evaluating Gas Network Capacities}, publisher = {SIAM}, isbn = {978-1-611973-68-6}, pages = {xvi + 376 pages}, language = {en} } @misc{HillerSaitenmacherWalther, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61092}, abstract = {We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model.}, language = {en} } @inproceedings{HillerSaitenmacherWalther, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, series = {Proceedings of Operations Research 2016}, booktitle = {Proceedings of Operations Research 2016}, doi = {10.1007/978-3-319-55702-1_34}, pages = {251 -- 257}, abstract = {We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model.}, language = {en} } @masterthesis{Saitenmacher, type = {Bachelor Thesis}, author = {Saitenmacher, Ren{\´e}}, title = {Combinatorial Models of Compressor Stations in Gas Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63522}, abstract = {I consider models of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, my aim is to identify from a set of operation modes those that are infeasible or redundant. For this, I investigate optimization and network reduction based procedures. Ultimately, these procedures may be employed for data preprocessing in the context of gas network optimization.}, language = {en} } @article{SchmidtAssmannBurlacuetal., author = {Schmidt, Martin and Assmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc and Schewe, Lars and Schwarz, Robert and Sirvent, Matthias}, title = {GasLib - A Library of Gas Network Instances}, series = {Data}, volume = {2}, journal = {Data}, number = {4}, doi = {10.3390/data2040040}, language = {en} } @article{DomschkeGrossHanteetal., author = {Domschke, Pia and Groß, Martin and Hante, Falk M. and Hiller, Benjamin and Schewe, Lars and Schmidt, Martin}, title = {Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken}, series = {gwf - Gas+Energie}, volume = {156}, journal = {gwf - Gas+Energie}, number = {11}, pages = {880 -- 885}, language = {de} } @incollection{HillerHumpolaLehmannetal., author = {Hiller, Benjamin and Humpola, Jesco and Lehmann, Thomas and Lenz, Ralf and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Willert, Bernhard}, title = {Computational results for validation of nominations}, series = {Evaluating Gas Network Capacities}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, abstract = {The different approaches to solve the validation of nomination problem presented in the previous chapters are evaluated computationally in this chapter. Each approach is analyzed individually, as well as the complete solvers for these problems. We demonstrate that the presented approaches can successfully solve large-scale real-world instances.}, language = {en} } @incollection{HumpolaFuegenschuhHilleretal., author = {Humpola, Jesco and F{\"u}genschuh, Armin and Hiller, Benjamin and Koch, Thorsten and Lehmann, Thomas and Lenz, Ralf and Schwarz, Robert and Schweiger, Jonas}, title = {The Specialized MINLP Approach}, series = {Evaluating Gas Network Capacities}, volume = {SIAM-MOS series on Optimization}, booktitle = {Evaluating Gas Network Capacities}, isbn = {9781611973686}, abstract = {We propose an approach to solve the validation of nominations problem using mixed-integer nonlinear programming (MINLP) methods. Our approach handles both the discrete settings and the nonlinear aspects of gas physics. Our main contribution is an innovative coupling of mixed-integer (linear) programming (MILP) methods with nonlinear programming (NLP) that exploits the special structure of a suitable approximation of gas physics, resulting in a global optimization method for this type of problem.}, language = {en} } @incollection{GotzesHeineckeHilleretal., author = {Gotzes, Uwe and Heinecke, Nina and Hiller, Benjamin and R{\"o}vekamp, Jessica and Koch, Thorsten}, title = {Regulatory rules for gas markets in Germany and other European countries}, series = {Evaluating gas network capacities}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, isbn = {978-1-611973-68-6}, pages = {45 -- 64}, language = {en} } @incollection{HillerHaynHeitschetal., author = {Hiller, Benjamin and Hayn, Christine and Heitsch, Holger and Henrion, Ren{\´e} and Le{\"o}vey, Hernan and M{\"o}ller, Andris and R{\"o}misch, Werner}, title = {Methods for verifying booked capacities}, series = {Evaluating gas network capacities}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, pages = {291 -- 315}, language = {en} } @misc{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67438}, abstract = {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 transported 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.}, language = {en} } @article{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, series = {European Journal of Operational Research}, volume = {270}, journal = {European Journal of Operational Research}, number = {3}, pages = {797 -- 808}, abstract = {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.}, language = {en} } @misc{HillerWalther, author = {Hiller, Benjamin and Walther, Tom}, title = {Improving branching for disjunctive polyhedral models using approximate convex decompositions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67462}, abstract = {Disjunctive sets arise in a variety of optimization models and much esearch has been devoted to obtain strong relaxations for them. This paper focuses on the evaluation of the relaxation during the branch-and-bound search process. We argue that the branching possibilities (\ie binary variables) of the usual formulations are unsuitable to obtain strong bounds early in the search process as they do not capture the overall shape of the the entire disjunctive set. To analyze and exploit the shape of the disjunctive set we propose to compute a hierarchy of approximate convex decompositions and show how to extend the known formulations to obtain improved branching behavior.}, language = {en} } @misc{HillerSaitenmacherWalther, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68179}, abstract = {We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. This procedure is based on a nontrivial reduction of the graph representing the gas flow through the compressor station in an operation mode.}, language = {en} } @misc{WaltherHillerSaitenmacher, author = {Walther, Tom and Hiller, Benjamin and Saitenmacher, Ren{\´e}}, title = {Polyhedral 3D Models for compressors in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65864}, abstract = {Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.}, language = {en} } @misc{HillerKochScheweetal., author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61931}, abstract = {Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by 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 maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.}, language = {en} } @misc{HillerWalther, author = {Hiller, Benjamin and Walther, Tom}, title = {Modelling compressor stations in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-67443}, abstract = {Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.}, language = {en} } @article{CardereraPokuttaSchuetteetal., author = {Carderera, Alejandro and Pokutta, Sebastian and Sch{\"u}tte, Christof and Weiser, Martin}, title = {CINDy: Conditional gradient-based Identification of Non-linear Dynamics - Noise-robust recovery}, series = {Journal of Computational and Applied Mathematics}, journal = {Journal of Computational and Applied Mathematics}, abstract = {Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative algorithms, the new algorithm shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry.}, language = {en} } @misc{WitzigGamrathHiller, author = {Witzig, Jakob and Gamrath, Gerald and Hiller, Benjamin}, title = {Reoptimization Techniques in MIP Solvers}, issn = {1438-0064}, doi = {10.1007/978-3-319-20086-6_14}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54375}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @inproceedings{GamrathHillerWitzig, author = {Gamrath, Gerald and Hiller, Benjamin and Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, volume = {9125}, edition = {Experimental Algorithms, Lecture Notes in Computer Science}, publisher = {Springer}, isbn = {978-3-319-20086-6}, doi = {10.1007/978-3-319-20086-6_14}, pages = {181 -- 192}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @misc{AndersonHiller, author = {Anderson, Lovis and Hiller, Benjamin}, title = {A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69489}, abstract = {Optimization models often feature disjunctions of polytopes as submodels. Such a disjunctive set is initially (at best) relaxed to its convex hull, which is then refined by branching. To measure the error of the convex relaxation, the (relative) difference between the volume of the convex hull and the volume of the disjunctive set may be used. This requires a method to compute the volume of the disjunctive set. Naively, this can be done via inclusion/exclusion and leveraging the existing code for the volume of polytopes. However, this is often inefficient. We propose a revised variant of an old algorithm by Bieri and Nef (1983) for this purpose. The algorithm uses a sweep-plane to incrementally calculate the volume of the disjunctive set as a function of the offset parameter of the sweep-plane.}, language = {en} } @misc{Anderson, type = {Master Thesis}, author = {Anderson, Lovis}, title = {The Computation of the Volume of the Union of Polytopes via a Sweep-Plane Algorithm}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71829}, pages = {52}, abstract = {Das Thema dieser Arbeit ist ein Volumen-Algorithmus f{\"u}r die Vereinigung von Polytopen. Der Algorithmus basiert auf der Arbeit von Bieri und Nef. Er berechnet das Volumen der Vereinigung von Polytopen mit einem Sweep-Verfahren. Dabei wird eine Hyperebene im Raum verschoben und das Volumen auf der einen Seite der Hyperebene berechnet. Umso weiter die Hyperebene verschobe wird, desto gr{\"o}ßer ist auch der Halbraum. Unser Algorithmus berechnet das Volumen einer Vereinigung von Polytopen geschnitten mit dem Halbraum der Sweep-Ebene als eine Funktion abh{\"a}ngig von der Veschiebung. Ab einem gewissen Punkt liegt der K{\"o}rper dabei komplett im Halbraum der Sweep-Ebene und das Volumen bleibt konstant. Unser Algorithmus unterscheidet sich in zwei Punkten von dem Algorithmus von Bieri und Nef. Erstens funktioniert er nur auf der Vereinigung von Polytopen, wohingegen der Algorithmus von Bieri und Nef f{\"u}r Nef-Polyeder funktioniert. Diese sind eine Verallgemeinerung von Polyedern, die auch die Klasse der Vereinigung von Polytopen umfasst. F{\"u}r uns ist das allerdings kein Nachteil, da unsere Datens{\"a}tze zu Vereinigungen von Polytopen f{\"u}hren. Zweitens ist unser Algorithmus in zwei Teile aufgeteilt. Im ersten Teil wird eine Datenstruktur entwickelt, aus der im zweiten Teil zusammen mit einer Richtung die Sweep-Ebenen-Volumenfunktion berechnet wird. Der Großteil der Komplexit{\"a}t liegt im ersten Teil des Algorithmus. Das hat den Vorteil, dass wir die Volumenfunktionen f{\"u}r viele verschiedene Richtungen berechnen k{\"o}nnen. So k{\"o}nnen Einblicke in die Struktur des K{\"o}rpers gewonnen werden. Der Algorithmus beruht auf zwei verschiedenen Zerlegungsans{\"a}tzen. Zuerst k{\"o}nnen wir mit Hilfe von Anordnungen von Hyperebenen eine Vereinigung von Polytopen in ihre Zellen zerlegen. Dabei berufen wir uns auf die Arbeit von Gerstner und Holtz, in der das Konzept der Positionsvektoren eingef{\"u}hrt wird. Diese nutzen wir um die Ecken und ihre benachbarten Zellen zu bestimmen. So erhalten wir eine Zerlegung unserer Vereinigung in Zellen, deren paarweise Schnitte kein Volumen haben. Das zweite Zerlegungskonzept ist die konische Zerlegung, wie sie von Lawrence eingef{\"u}hrt wurde. Mit Hilfe dieser k{\"o}nnen wir die Indikatorfunktion eines Polytops als die Summe der Indikatorfunktionen seiner Vorw{\"a}rtskegel schreiben. Die Sweep-Ebenen Volumenfunktionen k{\"o}nnen dann leicht mit Hilfe einer altbekannten Formel f{\"u}r das Volumen von Simplices berechnet werden.}, language = {en} }