Article Contents
Article Contents

Convexity and starshapedness of feasible sets in stationary flow networks

• * Corresponding author: Michael Schuster
The authors are supported by DFG grant CRC/Transregio 154
• In this paper, we consider a stationary model for the flow through a network. The flow is determined by the values at the boundary nodes of the network. We call these values the loads of the network. In the applications, the feasible loads must satisfy some box constraints. We analyze the structure of the set of feasible loads. Our analysis is motivated by gas pipeline flows, where the box constraints are pressure bounds.

We present sufficient conditions that imply that the feasible set is star-shaped with respect to special points. Under stronger conditions, we prove the convexity of the set of feasible loads. All the results are given for passive networks with and without compressor stations.

This analysis is motivated by the aim to use the spheric-radial decomposition for stochastic boundary data in this model. This paper can be used for simplifying the algorithmic use of the spheric-radial decomposition.

Mathematics Subject Classification: Primary: 90C15; Secondary: 93E20.

 Citation:

• Figure 1.  Example of differently structured graphs

Figure 2.  Example for illustrating the notation (graph numbered by breadth-first search)

Figure 3.  Example for illustrating the triple and quadruple indices on the path from $G_1$ to $G_5$

Figure 4.  Linear graph of example 1

Figure 5.  Feasible sets for different pressure bounds

Figure 6.  Linear graph of example 2

Figure 7.  Set $M_{a}$ for $(p^{+, \min})_{a} = [1, 1, 1, 1]^T$ and $(p^{+, \max})_{a} = [3, 3, 3, 3]^T$

Figure 8.  Set $M_{b}$ for $(p^{+, \min})_{b} = [2.5, 2, 1.5, 1]^T$ and $(p^{+, \max})_{b} = [3, 2.5, 2, 1.5]^T$

Figure 9.  Linear graph with one compressor edge of example 3

Figure 10.  Set $M_{a}$ for $(p^{+, \min})_{a} = [1, 1, 1, 1]^T$ and $(p^{+, \max})_{a} = [3, 3, 3, 3]^T$

Figure 11.  Set $M_{b}$ for $(p^{+, \min})_{b} = [2.5, 2, 1.5, 1]^T$ and $(p^{+, \max})_{b} = [3, 2.5, 2, 1.5]^T$

Figure 12.  Graph of example 2

Figure 13.  Feasible sets for different pressure bounds

Figure 14.  Graph of example 5

Figure 15.  Set $M_{a}$ for $(p^{+, \min})_{a} = [1, 1, 1, 1]^T$ and $(p^{+, \max})_{a} = [3, 2, 2, 2]^T$

Figure 16.  Set $M_{a}$ for $(p^{+, \min})_{b} = [2, 1, 1, 1]^T$ and $(p^{+, \max})_{b} = [3, 2, 2, 1.5]^T$

•  [1] M. K. Banda, M. Herty and A. Klar, Coupling conditions for gas networks governed by the isothermal Euler equations, Netw. Heterog. Media, 1 (2006), 295-314.  doi: 10.3934/nhm.2006.1.295. [2] M. K. Banda, M. Herty and A. Klar, Gas flow in pipeline networks, Netw. Heterog. Media, 1 (2006), 41-56.  doi: 10.3934/nhm.2006.1.41. [3] A. Bermúdez, J. González-Díaz, F. J. González-Diéguez, M. González-Rueda and M. P. Fernández de Córdoba, Simulation and optimization models of steady-state gas transmission networks, Energy Procedia, 64 (2015), 130-139. [4] R. M. Colombo and C. Mauri, Euler systems for compressible fluids at a junction, J. Hyperbolic Differ. Equ., 5 (2008), 547-568.  doi: 10.1142/S0219891608001593. [5] P. Domschke, B. Hiller, J. Lang and C. Tischendorf, Modellierung von Gasnetzwerken: Eine Übersicht, (2019), Preprint on Webpage http://tubiblio.ulb.tu-darmstadt.de/106763/. [6] M. H. Farshbaf-Shaker, R. Henrion and D. Hömberg, Properties of chance constraints in infinite dimensions with an application to PDE constrained optimization, Set-Valued Var. Anal., 26 (2018), 821-841.  doi: 10.1007/s11228-017-0452-5. [7] A. Genz and F. Bretz, Computation of Multivariate Normal and $t$ Probabilities, Lecture Notes in Statistics, 195. Springer, Dordrecht, 2009. doi: 10.1007/978-3-642-01689-9. [8] T. González Gradón, H. Heitsch and R. Henrion, A joint model of probabilistic/robust constraints for gas transport management in stationary networks, Comput. Manag. Sci., 14 (2017), 443-460.  doi: 10.1007/s10287-017-0284-7. [9] C. Gotzes, H. Heitsch, R. Henrion and R. Schultz, On the quantification of nomination feasibility in stationary gas networks with random load, Math. Methods Oper. Res., 84 (2016), 427-457.  doi: 10.1007/s00186-016-0564-y. [10] M. Gugat, F. M. Hante, M. Hirsch-Dick and G. Leugering, Stationary states in gas networks, Netw. Heterog. Media, 10 (2015), 295-320.  doi: 10.3934/nhm.2015.10.295. [11] M. Gugat, R. Schultz and D. Wintergerst, Networks of pipelines for gas with nonconstant compressibility factor: Stationary states, J. Comput. Appl. Math., 37 (2018), 1066-1097.  doi: 10.1007/s40314-016-0383-z. [12] M. Gugat and M. Schuster, Stationary gas networks with compressor control and random loads: Optimization with probabilistic constraints, Math. Probl. Eng., 2018 (2018), Art. ID 7984079, 17 pp. doi: 10.1155/2018/7984079. [13] M. Gugat and S. Ulbrich, The isothermal Euler equations for ideal gas with source term: Product solutions, flow reversal and no blow up, J. Math. Anal. Appl., 454 (2017), 439-452.  doi: 10.1016/j.jmaa.2017.04.064. [14] M. Gugat and D. Wintergerst, Transient flow in gas networks: Traveling waves, Int. J. Appl. Math. Comput. Sci., 28 (2018), 341-348.  doi: 10.2478/amcs-2018-0025. [15] H. Heitsch, On probabilistic capacity maximization in a stationary gas network, Optimization, 69 (2020), 575–604, Preprint on Webpage http://wias-berlin.de/publications/wias-publ/run.jsp?template=abstract&type=Preprint&year=2018&number=2540. doi: 10.1080/02331934.2019.1625353. [16] T. Koch, B. Hiller, M. E. Pfetsch and L. Schewe, Evaluating Gas Network Capacities, MOS-SIAM Series on Optimization, 21. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2015. doi: 978-1-611973-68-6. [17] A. Prékopa, Stochastic Programming, Mathematics and its Applications, 324. Kluwer Academic Publishers Group, Dordrecht, 1995. doi: 10.1007/978-94-017-3087-7. [18] D. Rose, M. Schmidt, M. C. Steinbach and B. M. Willert, Computational optimization of gas compressor stations: MINLP models versus continuous reformulations, Math. Methods Oper. Res., 83 (2016), 409-444.  doi: 10.1007/s00186-016-0533-5. [19] J. O. Royset and E. Polak, Extensions of stochastic optimization results to problems with system failure probability functions, J. Optim. Theory Appl., 133 (2007), 1-18.  doi: 10.1007/s10957-007-9178-0. [20] L. Schewe, M. Schmidt and J. Thürauf, Structural properties of feasible bookings in the European entry-exit gas market system, 4OR, (2019). doi: 10.1007/s10288-019-00411-3. [21] W. van Ackooij, I. Aleksovska and M. Munoz-Zuniga, (Sub-)Differentiability of probabilistic functions with elliptical distributions, Set-Valued Var. Anal., 26 (2018), 887-910.  doi: 10.1007/s11228-017-0454-3. [22] W. van Ackooij and R. Henrion, Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distribution, SIAM J. Optim., 24 (2014), 1864-1889.  doi: 10.1137/130922689. [23] D. Wintergerst, Application of chance constrained optimization to gas networks, (2019), Preprint on Webpage https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/start/5/rows/10/sortfield/score/sortorder/desc/searchtype/simple/query/wintergerst/docId/158.

Figures(16)