@misc{BeckerHiller, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77684}, abstract = {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.}, language = {en} } @misc{BeckerHiller, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Improved optimization models for potential-driven network flow problems via ASTS orientations}, issn = {1438-0064}, doi = {10.12752/7534}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75347}, abstract = {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.}, language = {en} } @misc{LenzBecker, author = {Lenz, Ralf and Becker, Kai-Helge}, title = {Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches}, issn = {1438-0064}, doi = {10.1007/s00291-021-00648-7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69726}, abstract = {In commodity transport networks such as natural gas, hydrogen and water networks, flows arise from nonlinear potential differences between the nodes, which can be represented by so-called "potential-driven" network models. When operators of these networks face increasing demand or the need to handle more diverse transport situations, they regularly seek to expand the capacity of their network by building new pipelines parallel to existing ones ("looping"). The paper introduces a new mixed-integer non-linear programming (MINLP) model and a new non-linear programming (NLP) model and compares these with existing models for the looping problem and related problems in the literature, both theoretically and experimentally. On this basis, we give recommendations about the circumstances under which a certain model should be used. In particular, it turns out that one of our novel models outperforms the existing models. Moreover, the paper is the first to include the practically relevant option that a particular pipeline may be looped several times.}, language = {en} } @misc{BeckerHiller, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {ASTS Orientations on Undirected Graphs: Structural analysis and enumeration}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69632}, abstract = {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.}, language = {en} } @misc{HillerBecker, author = {Hiller, Benjamin and Becker, Kai-Helge}, title = {Improving relaxations for potential-driven network flow problems via acyclic flow orientations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69622}, abstract = {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.}, language = {en} }