TY - CHAP A1 - Péron, Martin A1 - Bartlett, Peter L. A1 - Becker, Kai-Helge A1 - Helmstedt, Kate A1 - Chadès, Iadine T1 - Two Approximate Dynamic Programming Algorithms for Managing Complete SIS Networks T2 - COMPASS '18 Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies N2 - Inspired by the problem of best managing the invasive mosquito Aedes albopictus across the 17 Torres Straits islands of Australia, we aim at solving a Markov decision process on large Susceptible-Infected-Susceptible (SIS) networks that are highly connected. While dynamic programming approaches can solve sequential decision-making problems on sparsely connected networks, these approaches are intractable for highly connected networks. Inspired by our case study, we focus on problems where the probability of nodes changing state is low and propose two approximate dynamic programming approaches. The first approach is a modified version of value iteration where only those future states that are similar to the current state are accounted for. The second approach models the state space as continuous instead of binary, with an on-line algorithm that takes advantage of Bellman's adapted equation. We evaluate the resulting policies through simulations and provide a priority order to manage the 17 infested Torres Strait islands. Both algorithms show promise, with the continuous state approach being able to scale up to high dimensionality (50 nodes). This work provides a successful example of how AI algorithms can be designed to tackle challenging computational sustainability problems. Y1 - 2018 U6 - https://doi.org/10.1145/3209811.3209814 PB - ACM 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 - Lenz, Ralf A1 - Becker, Kai-Helge T1 - Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches N2 - 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. T3 - ZIB-Report - 18-44 KW - OR in energy KW - Network expansion KW - MINLP Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69726 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 - 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 - JOUR A1 - Lenz, Ralf A1 - Becker, Kai-Helge T1 - Optimization of Capacity Expansion in Potential-driven Networks including Multiple Looping - A comparison of modelling approaches JF - OR Spectrum N2 - 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. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.1007/s00291-021-00648-7 VL - 44 SP - 179 EP - 224 ER -