Combinatorial Switching for Routing Gas Flows
The transition towards a more reliable, efficient, safe and financeable energy supply is currently in the midst of public interest in Germany as well as in many other industrial nations. At the same time and in order to reduce the dependency on nuclear energy, climate and ecofriendly energy generation becomes more and more important. In this context, gas will play a significant role over the coming decades. However, there are many challenges with respect to transport, network technology, market regulatory conditions and the combination with other energy sources that need to be addressed. The SFB/TRR 154 project is trying to find answers to these challenges by means of mathematical modelling, simulation and optimization and to provide newlevel solutions.
The goal of subproject A04 is to develop algorithmic fundamentals for the efficient treatment of switching decisions in gas networks. In particular, this involves the modelling and algorithmics of the switching operations in compressor stations, since these pose a significant source of modelling and runtime complexity.
The set of feasible work points of a compressor station in general is nonconvex, in some circumstances even nonconnected, but can be well approximated by the union of convex polyhedra. Hence, the treatment of such structures in MIPs and MINLPs will be the main focus of research in this subproject. While being motivated by the optimization of gas networks, the methods to be developed will be relevant in a much broader field of vision.
Known techniques for modelling unions of polyhedra as the feasible set of a MIP rely on the description of the single polyhedra using inequalities. In contrast to this, another approach adapted to the geometric properties of the overall set can be considered. More precisely, the goal is to find and analyze a hierarchical description of a nonconvex set that provides an as good as possible polyhedral relaxation on each level. This hierarchy can then be used in the branchandbound procedure for solving MINLPs together with suitable branching decisions.
In the long term, this subproject of SFB/TRR 154 is aiming at the development of realtime capable methods for combinatorial decisions. Furthermore, since the transient control of gas networks requires the successive solving of many similar MIPs/MINLPs, reoptimization techniques come into view that use known information from previous optimization problems in order to reduce running time. For these, a detailed analysis of the problem structure and a deeper understanding of the complex MIP/MINLP solving process will be an essential topic of research.
Publications
2018 

Lovis Anderson, Benjamin Hiller  A SweepPlane Algorithm for the Computation of the Volume of a Union of Polytopes  ZIBReport 1837 
PDF
BibTeX URN 
Benjamin Hiller, Thorsten Koch, Lars Schewe, Robert Schwarz, Jonas Schweiger  A System to Evaluate Gas Network Capacities: Concepts and Implementation  European Journal of Operational Research, 270(3), pp. 797808, 2018 (preprint available as ZIBReport 1811) 
PDF (ZIBReport)
BibTeX 
Benjamin Hiller, René Saitenmacher, Tom Walther  Analysis of operating modes of complex compressor stations  ZIBReport 1765 
PDF
BibTeX URN 
Benjamin Hiller, Tom Walther  Improving branching for disjunctive polyhedral models using approximate convex decompositions  ZIBReport 1768 
PDF
BibTeX URN 
Benjamin Hiller, Tom Walther  Modelling compressor stations in gas networks  ZIBReport 1767 
PDF
BibTeX URN 
2017 

Benjamin Hiller, Thorsten Koch, Lars Schewe, Robert Schwarz, Jonas Schweiger  A System to Evaluate Gas Network Capacities: Concepts and Implementation  ZIBReport 1703 
PDF
BibTeX URN 
Benjamin Hiller, René Saitenmacher, Tom Walther  Analysis of operating modes of complex compressor stations  Proceedings of Operations Research 2016, pp. 251257, 2017 (preprint available as ZIBReport 1661) 
PDF (ZIBReport)
BibTeX DOI 
Martin Schmidt, Denis Assmann, Robert Burlacu, Jesco Humpola, Imke Joormann, Nikolaos Kanelakis, Thorsten Koch, Djamal Oucherif, Marc E. Pfetsch, Lars Schewe, Robert Schwarz, Matthias Sirvent  GasLib – A Library of Gas Network Instances  Optimization Online, 2017 
BibTeX

Tom Walther, Benjamin Hiller, René Saitenmacher  Polyhedral 3D Models for compressors in gas networks  ZIBReport 1766 
PDF
BibTeX URN 
2016 

René Saitenmacher  Combinatorial Models of Compressor Stations in Gas Networks  Bachelor thesis, Freie Universität Berlin, Ralf Borndörfer, Benjamin Hiller (Advisors), 2016 
PDF
BibTeX URN 
2015 

Benjamin Hiller, Jesco Humpola, Thomas Lehmann, Ralf Lenz, Antonio Morsi, Marc E. Pfetsch, Lars Schewe, Martin Schmidt, Robert Schwarz, Jonas Schweiger, Claudia Stangl, Bernhard M. Willert  Computational results for validation of nominations  Evaluating Gas Network Capacities, SIAM, 2015, isbn: 9781611973686 
BibTeX

Thorsten Koch, Benjamin Hiller, Marc Pfetsch, Lars Schewe  Evaluating Gas Network Capacities  SIAM, 2015, isbn: 9781611973686 
BibTeX

Pia Domschke, Martin Groß, Falk M. Hante, Benjamin Hiller, Lars Schewe, Martin Schmidt  Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken  gwf  Gas+Energie, 156(11), pp. 880885, 2015 
BibTeX

Benjamin Hiller, Christine Hayn, Holger Heitsch, René Henrion, Hernan Leövey, Andris Möller, Werner Römisch  Methods for verifying booked capacities  Evaluating gas network capacities, Society for Industrial and Applied Mathematics, pp. 291315, 2015 
BibTeX

Uwe Gotzes, Nina Heinecke, Benjamin Hiller, Jessica Rövekamp, Thorsten Koch  Regulatory rules for gas markets in Germany and other European countries  Evaluating gas network capacities, Society for Industrial and Applied Mathematics, pp. 4564, 2015, isbn: 9781611973686 
BibTeX

Gerald Gamrath, Benjamin Hiller, Jakob Witzig  Reoptimization Techniques in MIP Solvers  Springer, Experimental Algorithms, Lecture Notes in Computer Science, pp. 181192, 2015, isbn: 9783319200866 (preprint available as ZIBReport 1524) 
PDF (ZIBReport)
BibTeX DOI 
Jesco Humpola, Armin Fügenschuh, Benjamin Hiller, Thorsten Koch, Thomas Lehmann, Ralf Lenz, Robert Schwarz, Jonas Schweiger  The Specialized MINLP Approach  Evaluating Gas Network Capacities, SIAM, 2015, isbn: 9781611973686 
BibTeX
