6948
eng
reportzib
0
--
2018-07-17
--
A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes
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.
1438-0064
urn:nbn:de:0297-zib-69489
Lovis Anderson
Lovis Anderson
Benjamin Hiller
ZIB-Report
18-37
eng
uncontrolled
Disjunctive Programming
eng
uncontrolled
Volume Algorithm
eng
uncontrolled
Union of Polytopes
Mathematics of Computing
GENERAL
CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
TRR154-A04
MODAL-Gesamt
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/6948/ZR-18-37.pdf
7499
2021
eng
687
734
2
22
article
Springer Nature
0
2020-10-03
2021-06-01
--
Controlling transient gas flow in real-world pipeline intersection areas
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.
Optimization and Engineering
https://doi.org/10.1007/s11081-020-09559-y
yes
urn:nbn:de:0297-zib-73645
2020-09-04
Felix Hennings
Felix Hennings
Lovis Anderson
Kai Hoppmann-Baum
Mark Turner
Thorsten Koch
Mathematical Optimization
Hoppmann, Kai
Koch, Thorsten
MODAL-GasLab
Hennings, Felix
MODAL-Gesamt
Energy Network Optimization
Turner, Mark Ruben
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
7112
2019
eng
Operations Research Proceedings
conferenceobject
0
--
--
--
A Sweep-Plane Algorithm for the Computation of the Volume of a Union of Polytopes
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.
Operations Research Proceedings 2018
10.1007/978-3-030-18500-8_12
yes
2018-11-16
urn:nbn:de:0297-zib-69489
Lovis Anderson
Lovis Anderson
Benjamin Hiller
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
MODAL-Gesamt
7182
2018
eng
52
masterthesis
0
--
--
2018-01-15
The Computation of the Volume of the Union of Polytopes via a Sweep-Plane Algorithm
Das Thema dieser Arbeit ist ein Volumen-Algorithmus fü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öß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ängig von der Veschiebung. Ab einem gewissen Punkt liegt der Kö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ür Nef-Polyeder funktioniert. Diese sind eine Verallgemeinerung von Polyedern, die auch die Klasse der Vereinigung von Polytopen umfasst. Für uns ist das allerdings kein Nachteil, da unsere Datensätze zu Vereinigungen von Polytopen fü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ät liegt im ersten Teil des Algorithmus. Das hat den Vorteil, dass wir die Volumenfunktionen für viele verschiedene Richtungen berechnen können. So können Einblicke in die Struktur des Körpers gewonnen werden.
Der Algorithmus beruht auf zwei verschiedenen Zerlegungsansätzen. Zuerst kö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ü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ührt wurde. Mit Hilfe dieser können wir die Indikatorfunktion eines Polytops als die Summe der Indikatorfunktionen seiner Vorwärtskegel schreiben. Die Sweep-Ebenen Volumenfunktionen können dann leicht mit Hilfe einer altbekannten Formel für das Volumen von Simplices berechnet werden.
urn:nbn:de:0297-zib-71829
Thorsten Koch
Lovis Anderson
Lovis Anderson
Mathematics of Computing
CONVEX AND DISCRETE GEOMETRY
Mathematical Optimization
TRR154-A04
Technische Universität Berlin
https://opus4.kobv.de/opus4-zib/files/7182/master_thesis.pdf
8151
2022
2022
eng
503
532
95
article
Springer Nature
0
2022-04-19
2022-04-19
--
Generative deep learning for decision making in gas networks
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%.
Mathematical Methods of Operations Research
10.1007/s00186-022-00777-x
yes
publish
urn:nbn:de:0297-zib-81103
23/02/2022
Lovis Anderson
Lovis Anderson
Mark Turner
Thorsten Koch
Koch, Thorsten
MODAL-GasLab
MODAL-Gesamt
Turner, Mark Ruben
Mathematical Algorithmic Intelligence
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
UNSEEN
7364
eng
reportzib
0
--
2019-06-17
--
Controlling transient gas flow in real-world pipeline intersection areas
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.
1438-0064
urn:nbn:de:0297-zib-73645
no
Felix Hennings
Felix Hennings
Lovis Anderson
Kai Hoppmann
Mark Turner
Thorsten Koch
ZIB-Report
19-24
Mathematical Optimization
Hoppmann, Kai
Koch, Thorsten
MODAL-GasLab
Hennings, Felix
MODAL-Gesamt
Energy Network Optimization
Turner, Mark Ruben
https://opus4.kobv.de/opus4-zib/files/7364/ZR_19-24.pdf
https://opus4.kobv.de/opus4-zib/files/7364/ZR_19-24_v2.pdf
https://opus4.kobv.de/opus4-zib/files/7364/ZR_19-24_v3.pdf
8110
eng
reportzib
0
--
2020-12-18
--
Generative deep learning for decision making in gas networks
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%.
1438-0064
urn:nbn:de:0297-zib-81103
Lovis Anderson
Mark Turner
Mark Turner
Thorsten Koch
ZIB-Report
20-38
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Koch, Thorsten
MODAL-GasLab
MODAL-Gesamt
Turner, Mark Ruben
Mathematical Algorithmic Intelligence
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
UNSEEN
https://opus4.kobv.de/opus4-zib/files/8110/paper.pdf
https://opus4.kobv.de/opus4-zib/files/8110/ZIB-Report-20-38.pdf
9576
2023
eng
95
DLR-FB-2023-15
other
0
--
--
--
Evaluation of Uncertainties in Linear-Optimizing Energy System Models - Compendium
Fü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önnen. Hierfür wurden umfangreiche Parametervariationen auf Energieszenarien angewendet und das wesentliche methodische Hindernis in diesem Zusammenhang adressiert: die rechnerische Beherrschbarkeit der zu lösenden mathematischen Optimierungsprobleme. Im Vorläuferprojekt BEAM-ME wurde mit der Entwicklung und Anwendung des Open-Source-Lösers PIPS-IPM++ die Grundlage für den Einsatz von High-Performance-Computing (HPC) zur Lösung dieser Modelle gelegt. In UNSEEN war dieser Löser die zentrale Komponente eines Workflows, welcher zur Generierung, Lösung und multi-kriteriellen Bewertung von Energieszenarien auf dem Hochleistungscomputer JUWELS am Forschungszentrum Jülich implementiert wurde. Zur effizienten Generierung und Kommunikation von Modellinstanzen fü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ösungsalgorithmen für linear optimierende Energie-Systemmodelle standen gemischt-ganzzahlige Optimierungsprobleme im Fokus, welche für die Modellierung konkreter Infrastrukturen und Maßnahmen zur Umsetzung der Energiewende gelöst werden müssen. Die in diesem Zusammenhang stehenden Arbeiten zur Entwicklung von Algorithmen wurden von der Technischen Universität Berlin verantwortet. Bei Design und Implementierung dieser Methoden wurde sie vom Zuse Instituts Berlin unterstützt.
DLR-Forschungsbericht
10.57676/w2rq-bj85
no
publish
false
true
Karl-Kien Cao
Janina Zittel
Lovis Anderson
Aileen Böhme
Thomas Breuer
Jan Buschmann
Frederick Fiand
Ulrich Frey
Benjamin Fuchs
Nils-Christian Kempe
Kai von Krbek
Wided Medjroubi
Judith Riehm
Shima Sasanpour
Sonja Simon
Charlie Vanaret
Manuel Wetzel
Mengzhu Xiao
Janina Zittel
Zittel, Janina
Applied Algorithmic Intelligence Methods
Vanaret, Charlie William
UNSEEN