TY - GEN 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 N2 - 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. T3 - ZIB-Report - 17-03 KW - operations research in energy KW - gas network optimization KW - entry-exit model KW - freely allocable capacity KW - large-scale mixed-integer nonlinear programming Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61931 SN - 1438-0064 N1 - A revised and extended version is available as ZIB-Report 18-11. ER - TY - GEN A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups N2 - The task of an elevator control is to schedule the elevators of a group such that small waiting and travel times for the passengers are obtained. We present an exact reoptimization algorithm for this problem. A reoptimization algorithm computes a new schedule for the elevator group each time a new passenger arrives. Our algorithm uses column generation techniques and is, to the best of our knowledge, the first exact reoptimization algorithms for a group of passenger elevators. To solve the column generation problem, we propose a Branch & Bound method. T3 - ZIB-Report - 12-43 KW - elevator control, online optimization, reoptimization algorithms, column generation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16485 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations N2 - 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. T3 - ZIB-Report - 17-65 KW - bound tightening KW - flow patterns KW - model reformulation KW - multi-way compressor station Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68179 SN - 1438-0064 ER - TY - GEN A1 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - ASTS Orientations on Undirected Graphs: Structural analysis and enumeration N2 - All feasible flows in potential-driven networks induce an orientation on the undirected graph underlying the network. Clearly, these orientations must satisfy two conditions: they are acyclic and there are no "dead ends" in the network, i.e. each source requires outgoing flows, each sink requires incoming flows, and each transhipment vertex requires both an incoming and an outgoing flow. In this paper we will call orientations that satisfy these conditions acyclic source-transhipment-sink orientations (ASTS-orientation) and study their structure. In particular, we characterize graphs that allow for such an orientation, describe a way to enumerate all possible ASTS-orientations of a given graph, present an algorithm to simplify and decompose a graph before such an enumeration and shed light on the role of zero flows in the context of ASTS-orientations. T3 - ZIB-Report - 18-31 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69632 SN - 1438-0064 ER - TY - GEN A1 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited N2 - In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested. T3 - ZIB-Report - 20-05 KW - acyclic orientations KW - enumeration algorithm KW - multiple sources and sinks KW - bipolar orientations Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-77684 SN - 1438-0064 ER - TY - GEN A1 - Becker, Kai-Helge A1 - Hiller, Benjamin T1 - Improved optimization models for potential-driven network flow problems via ASTS orientations N2 - The class of potential-driven network flow problems provides important models for a range of infrastructure networks that lead to hard-to-solve MINLPs in real-world applications. On large-scale meshed networks the relaxations usually employed are rather weak due to cycles in the network. To address this situation, we introduce the concept of ASTS orientations, a generalization of bipolar orientations, as a combinatorial relaxation of feasible solutions of potential-driven flow problems, study their structure, and show how they can be used to strengthen existing relaxations and thus provide improved optimization models. Our computational results indicate that ASTS orientations can be used to derive much stronger bounds on the flow variables than existing bound tightening methods and to yield significant performance improvements for an existing state-of-the-art MILP model for large-scale gas networks. T3 - ZIB-Report - 19-58 KW - potential-driven network flows KW - mixed-integer nonlinear programming KW - ASTS orientations KW - bipolar orientations Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75347 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Walther, Tom T1 - Improving branching for disjunctive polyhedral models using approximate convex decompositions N2 - 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. T3 - ZIB-Report - 17-68 KW - approximate convex decomposition KW - branch-and-bound KW - convex hull reformulation KW - disjunctive set Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67462 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Becker, Kai-Helge T1 - Improving relaxations for potential-driven network flow problems via acyclic flow orientations N2 - The class of potential-driven network flow problems provides important models for a range of infrastructure networks. For real-world applications, they need to be combined with integer models for switching certain network elements, giving rise to hard-to-solve MINLPs. We observe that on large-scale real-world meshed networks the usually employed relaxations are rather weak due to cycles in the network. We propose acyclic flow orientations as a combinatorial relaxation of feasible solutions of potential-driven flow problems and show how they can be used to strengthen existing relaxations. First computational results indicate that the strengthend model is much tighter than the original relaxation, thus promising a computational advantage. T3 - ZIB-Report - 18-30 KW - potential-driven network flows KW - acyclic orientations KW - flow orientations KW - MINLPs Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69622 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Walther, Tom T1 - Modelling compressor stations in gas networks N2 - 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. T3 - ZIB-Report - 17-67 KW - MINLP model KW - compressor station KW - gas compressor modeling KW - nonlinear model KW - polyhedral model Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-67443 SN - 1438-0064 ER - TY - GEN A1 - Martin, Alexander A1 - Geißler, Björn A1 - Hayn, Christine A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Optimierung Technischer Kapazitäten in Gasnetzen N2 - Die mittel- und längerfristige Planung für den Gastransport hat sich durch Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazität und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze skizziert. T3 - ZIB-Report - 11-56 KW - Gasnetzplanung KW - Technische Kapazitäten KW - Nominierungsvalidierung KW - Buchungsvalidierung KW - Topologieplanung Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15121 SN - 1438-0064 ER -