@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} } @inproceedings{AndersonHiller, author = {Anderson, Lovis and Hiller, Benjamin}, title = {A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes}, series = {Operations Research Proceedings 2018}, volume = {Operations Research Proceedings}, booktitle = {Operations Research Proceedings 2018}, doi = {10.1007/978-3-030-18500-8_12}, 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. 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} } @article{AndersonTurnerKoch2022, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, series = {Mathematical Methods of Operations Research}, volume = {95}, journal = {Mathematical Methods of Operations Research}, publisher = {Springer Nature}, doi = {10.1007/s00186-022-00777-x}, pages = {503 -- 532}, year = {2022}, abstract = {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\%.}, language = {en} } @misc{HenningsAndersonHoppmannetal., author = {Hennings, Felix and Anderson, Lovis and Hoppmann, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73645}, abstract = {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.}, language = {en} } @misc{AndersonTurnerKoch, author = {Anderson, Lovis and Turner, Mark and Koch, Thorsten}, title = {Generative deep learning for decision making in gas networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81103}, abstract = {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\%.}, language = {en} } @misc{CaoAndersonBoehmeetal., author = {Cao, Karl-Kien and Anderson, Lovis and B{\"o}hme, Aileen and Breuer, Thomas and Buschmann, Jan and Fiand, Frederick and Frey, Ulrich and Fuchs, Benjamin and Kempe, Nils-Christian and von Krbek, Kai and Medjroubi, Wided and Riehm, Judith and Sasanpour, Shima and Simon, Sonja and Vanaret, Charlie and Wetzel, Manuel and Xiao, Mengzhu and Zittel, Janina}, title = {Evaluation of Uncertainties in Linear-Optimizing Energy System Models - Compendium}, series = {DLR-Forschungsbericht}, journal = {DLR-Forschungsbericht}, number = {DLR-FB-2023-15}, doi = {10.57676/w2rq-bj85}, pages = {95}, abstract = {F{\"u}r die Energiesystemforschung sind Software-Modelle ein Kernelement zur Analyse von Szenarien. Das Forschungsprojekt UNSEEN hatte das Ziel eine bisher unerreichte Anzahl an modellbasierten Energieszenarien zu berechnen, um Unsicherheiten - vor allem unter Nutzung linear optimierender Energiesystem-Modelle - besser bewerten zu k{\"o}nnen. Hierf{\"u}r wurden umfangreiche Parametervariationen auf Energieszenarien angewendet und das wesentliche methodische Hindernis in diesem Zusammenhang adressiert: die rechnerische Beherrschbarkeit der zu l{\"o}senden mathematischen Optimierungsprobleme. Im Vorl{\"a}uferprojekt BEAM-ME wurde mit der Entwicklung und Anwendung des Open-Source-L{\"o}sers PIPS-IPM++ die Grundlage f{\"u}r den Einsatz von High-Performance-Computing (HPC) zur L{\"o}sung dieser Modelle gelegt. In UNSEEN war dieser L{\"o}ser die zentrale Komponente eines Workflows, welcher zur Generierung, L{\"o}sung und multi-kriteriellen Bewertung von Energieszenarien auf dem Hochleistungscomputer JUWELS am Forschungszentrum J{\"u}lich implementiert wurde. Zur effizienten Generierung und Kommunikation von Modellinstanzen f{\"u}r Methoden der mathematischen Optimierung auf HPC wurde eine weitere Workflow-Komponente von der GAMS Software GmbH entwickelt: der Szenariogenerator. Bei der Weiterentwicklung von L{\"o}sungsalgorithmen f{\"u}r linear optimierende Energie-Systemmodelle standen gemischt-ganzzahlige Optimierungsprobleme im Fokus, welche f{\"u}r die Modellierung konkreter Infrastrukturen und Maßnahmen zur Umsetzung der Energiewende gel{\"o}st werden m{\"u}ssen. Die in diesem Zusammenhang stehenden Arbeiten zur Entwicklung von Algorithmen wurden von der Technischen Universit{\"a}t Berlin verantwortet. Bei Design und Implementierung dieser Methoden wurde sie vom Zuse Instituts Berlin unterst{\"u}tzt.}, language = {en} } @article{HenningsAndersonHoppmannBaumetal., author = {Hennings, Felix and Anderson, Lovis and Hoppmann-Baum, Kai and Turner, Mark and Koch, Thorsten}, title = {Controlling transient gas flow in real-world pipeline intersection areas}, series = {Optimization and Engineering}, volume = {22}, journal = {Optimization and Engineering}, edition = {2}, publisher = {Springer Nature}, doi = {https://doi.org/10.1007/s11081-020-09559-y}, pages = {687 -- 734}, abstract = {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.}, language = {en} }