Martine Labbé
email: martine.labbe@ulb.ac.

Fränk Plein
email: frank.plein@ulb.ac.be

Martin Schmidt
email: martin.schmidt@uni-trier.de

Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results

Keywords: Mathematics Subject Classification. 90B10, 90C30, 90C35, 90C39, 90C90 Gas networks, Booking, Nomination, Computational complexity, Trees, Dynamic programming

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

As a result of the liberalisation of the European gas market [START_REF] Hewicker | The New Entry-Exit Model in the EU and Its Consequences for Gas Supply Companies[END_REF], the so-called entry-exit market system has been introduced [30][31][32]. In order to decouple trading and transport, the entry-exit market organisation specifies certain types of capacity right contracts. At the core of these contracts are the so-called bookings and nominations. In this market system, the transportation system operator (TSO) is obliged to offer the maximum amount of capacity at every node of its network, which is an upper bound on the bookable capacity. Gas traders then sign a longterm booking contract with the TSO in which they obtain rights for maximum supplies or withdrawals at certain entry and exit nodes of the network. On a day-ahead basis, the entry and exit customers nominate the amount of gas to be supplied to or withdrawn from the network the next day. Due to the European regulation, the TSO must be able to transport every nomination that is compliant with a previously signed booking. A booking is therefore said to be feasible if and only if all booking-compliant nominations, i.e., infinitely many, can be transported through the network. To determine the maximum amount of capacity available at all nodes of the network, the TSO in particular needs to verify the feasibility of all possibly resulting bookings. This verification leads to very challenging mathematical problems. A mathematical model of the European entry-exit gas market system taking all these aspects into account is presented in [START_REF] Grimm | A Multilevel Model of the European Entry-Exit Gas Market[END_REF]. The authors' approach has a strong economic focus, whereas we put more emphasis on physical and technical aspects of feasible bookings.

On the one hand, a lot of research has been carried out in the last decades on applying mathematical optimisation in the gas sector. Mostly, this research considered the question of verifying the feasibility of a nomination or its cost-optimal transport. For instance, in [START_REF] De | The Gas Transmission Problem Solved by an Extension of the Simplex Algorithm[END_REF] the authors consider the latter problem with an application to the Belgian gas network before the European liberalisation process. As a follow-up, their techniques are updated in [START_REF] Bakhouya | The Gas Transmission Problem When the Merchant and the Transport Functions Are Disconnected[END_REF] to reflect the market situation after the liberalisation. The authors of [START_REF] De | The Gas Transmission Problem Solved by an Extension of the Simplex Algorithm[END_REF] propose an extension of the simplex algorithm for the case in which gas physics are approximated with piecewise-linear functions -an approach that has been also used in, e.g., [START_REF] Domschke | Combination of Nonlinear and Linear Optimization of Transient Gas Networks[END_REF][START_REF] Martin | Mixed Integer Models for the Stationary Case of Gas Network Optimization[END_REF]. As an extension, piecewise-linear relaxations have been applied in many other articles like [START_REF] Geißler | Towards Globally Optimal Solutions for MINLPs by Discretization Techniques with Applications in Gas Network Optimization[END_REF][START_REF] Geißler | The MILPrelaxation approach[END_REF][START_REF] Geißler | A New Algorithm for MINLP Applied to Gas Transport Energy Cost Minimization[END_REF][START_REF] Geißler | Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods[END_REF][START_REF] Geißler | Solving power-constrained gas transportation problems using an MIP-based alternating direction method[END_REF]. A collection of solution techniques for checking the feasibility of a nomination has been discussed in the recent book [START_REF] Koch | Evaluating Gas Network Capacities[END_REF]. Besides piecewise linearisation techniques, there (and in related work) the authors also consider NLP [START_REF] Schmidt | Chapter 10: The Precise NLP Model[END_REF][START_REF] Schmidt | High Detail Stationary Optimization Models for Gas Networks[END_REF][START_REF] Schmidt | High Detail Stationary Optimization Models for Gas Networks: Validation and Results[END_REF] and MPEC approaches [START_REF] Baumrucker | MPEC strategies for cost optimization of pipeline operations[END_REF][START_REF] Rose | Computational Optimization of Gas Compressor Stations: MINLP Models versus Continuous Reformulations[END_REF][START_REF] Schmidt | A Generic Interior-Point Framework for Nonsmooth and Complementarity Constrained Nonlinear Optimization[END_REF][START_REF] Schmidt | A Primal Heuristic for Nonsmooth Mixed Integer Nonlinear Optimization[END_REF][START_REF] Schmidt | An MPEC based heuristic[END_REF]. In [START_REF] Bermúdez | Simulation and Optimization Models of Steady-State Gas Transmission Networks[END_REF], simulation and optimisation techniques are combined to determine the configuration of steady-state gas flow networks. For further details on gas transport literature, we refer the reader to the recent survey [START_REF] Roger | Optimization Problems in Natural Gas Transportation Systems: A State-of-the-Art Review[END_REF] and the references therein.

On the other hand, there is much less mathematical literature on bookings. The problem of verifying the feasibility of a set of bookings is harder, because by definition the verification of feasible nominations has to be solved as a sub-problem. An additional difficulty is the robust nature of bookings: To certify the feasibility of a set of bookings, we need to verify that infinitely many nominations can be transported through the network. First attempts to study feasible bookings are proposed in [START_REF] Fügenschuh | Mathematical Optimization for Challenging Network Planning Problems in Unbundled Liberalized Gas Markets[END_REF][START_REF] Koch | Evaluating Gas Network Capacities[END_REF][START_REF] Martin | Optimierung Technischer Kapazitäten in Gasnetzen[END_REF][START_REF] Willert | Validation of Nominations in Gas Networks and Properties of Technical Capacities[END_REF]. Given a single entry node and several exit nodes, in [START_REF] Gotzes | On the Quantification of Nomination Feasibility in Stationary Gas Networks with Random Load[END_REF] the authors quantify the probability of booking-compliant nominations under the assumption that the exit loads follow a joint Gaussian distribution. They propose methods to validate bookings with respect to the most likely nominations. The complexity of verifying the feasibility of bookings has also been studied in the PhD thesis [START_REF] Hayn | Computing Maximal Entry and Exit Capacities of Transportation Networks-Complexity Analysis and a Discrete Relaxation Applied to Gas Transmission Systems[END_REF]. It is shown that the problem is coNP-complete on general networks if flows are modelled using the classical linear flow model. Furthermore, the author gives upper complexity bounds when the considered physical model is given by a potential-based flow. Structural properties like (non)convexity etc. of the sets of feasible nominations and bookings are established in [START_REF] Schewe | Structural Properties of Feasible Bookings in the European Entry-Exit Gas Market System[END_REF]. Finally, an algorithm for solving the problem of robust discrete arc sizing is presented in [START_REF] Robinius | Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks[END_REF]. Verifying the feasibility of bookings on a tree can be seen as a special case of this problem. Nonetheless, we will see that our tailored solution approach outperforms their algorithm, which applies to a more general setting. The problem of verifying the feasibility of a given set of bookings with a linear flow model is considered in [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF], where the problem is called the reservation-allocation problem.

In this paper, we study the complexity of verifying the feasibility of given bookings. Due to the mathematical difficulty of this problem, we do not take into account any controllable elements and thus consider networks constituted of pipes only. Furthermore, we choose a rather abstract physics model by considering a steadystate potential-based flow model. These models have been introduced in [START_REF] Birkhoff | Non-Linear Network Problems[END_REF] and can, besides gas flow, also be applied to model water or power transport networks [START_REF] Groß | Algorithmic Results for Potential-Based Flows: Easy and Hard Cases[END_REF][START_REF] Schewe | The Impact of Potential-Based Physics Models on Pricing in Energy Networks[END_REF]. They are governed by Kirchhoff's first law and a special variant of the second law [START_REF] Kirchhoff | Ueber Die Auflösung Der Gleichungen, Auf Welche Man Bei Der Untersuchung Der Linearen Vertheilung Galvanischer Ströme Geführt Wird[END_REF]. More precisely, mass is conserved at every node of the network and the flow on an arc is linked to potentials at the incident nodes through so-called potential functions. A key property of potential-based flow networks without controllable elements is the uniqueness of flows for given supplies and withdrawals. This result has been established in early works for fluid flow networks in [START_REF] Maugis | Étude de réseaux de transport et de distribution de fluide[END_REF] and more generally for potential-based flows in [START_REF] Roger | Preprocessing on Natural Gas Transmission Networks[END_REF][START_REF] Roger | A Reduction Technique for Natural Gas Transmission Network Optimization Problems[END_REF]. It marks the key difference compared to classical linear flow models.

Our contribution is the following. We prove a characterisation of feasible bookings on general potential-based flow networks with arc capacities and potential bounds. This result is based on an extension of a characterisation of feasible nominations presented in [START_REF] Gotzes | On the Quantification of Nomination Feasibility in Stationary Gas Networks with Random Load[END_REF]. As a consequence of the characterisation of feasible bookings, we are able to derive that verifying the feasibility of bookings is in coNP in general, but can be solved in polynomial time on networks with linear potential functions. Furthermore, we present a dynamic programming approach with which we can also verify in polynomial time the feasibility of bookings on tree-shaped networks with nonlinear potential functions. It turns out that the hardness of the problem thus strongly depends on the underlying flow model -i.e., the potential functions -and the network structure. We therefore conclude this paper with an overview of known complexity results for different variants of the problem and present a list of open problems.

The remainder of this paper is structured as follows. In Section 2, we introduce general notations and definitions. Section 3 establishes a characterisation of feasible bookings on general potential-based flow networks. We study the special cases of networks with linear potential functions in Section 4 and tree-shaped networks with general nonlinear potential functions in Section 5. It turns out that the hardness of verifying the feasibility of bookings strongly depends on the underlying physical flow model as well as the network structure. Thus, in the final Section 6, we give an overview of known complexity results for different combinations of these aspects. Finally, we list open problems for which the hardness is not yet known.

Main Definitions and Notation

The structure of a potential network is given by a directed and connected graph G = (V, A). The set of nodes V = V + ∪ V -∪ V 0 is composed of the set V + of entry nodes (sources, where gas is supplied), the set V -of exit nodes (sinks, where gas is withdrawn), and the set V 0 of inner nodes. The set of arcs A consists, in the scope of this work, only of so-called passive elements, i.e., pipes. Thus, we do not take into account any controllable elements like compressor stations or valves. For details on modelling compressor stations or other active network elements see, e.g., [START_REF] Rose | Computational Optimization of Gas Compressor Stations: MINLP Models versus Continuous Reformulations[END_REF][START_REF] Schmidt | Chapter 10: The Precise NLP Model[END_REF] and the references therein. A network constituted of only pipes is called passive.

For a node v ∈ V , let δ in (v) and δ out (v) be the sets of arcs entering or leaving node v. Similarly, let V in (v) and V out (v) be the sets of backward and forward neighbours of v. We denote by M ∈ R V ×A the node-arc incidence matrix of the network G. For any node u ∈ V and arc a ∈ A, the corresponding entry is defined by

m ua =      +1, if a = (u, v), -1, if a = (v, u), 0,
otherwise. Figure 1 shows an example of a small network, where we indicate entry and exit nodes by dashed arcs, and its corresponding incidence matrix M.

     1 0 0 1 0 0 -1 1 -1 0 0 0 0 -1 0 0 1 0 0 0 1 0 0 -1 0 0 0 -1 -1 1       Figure 1.
0 ≤ π - v ≤ π v ≤ π + v ≤ ∞.
Further, let us denote the flow on arc a ∈ A by q a . For an arc a = (u, v), we interpret q a > 0 as flow in the direction of the arc, i.e., from u to v, and q a < 0 as flow in the opposite direction. Additionally, the flow on every arc a has to satisfy given arc capacities -∞ ≤ q - a ≤ q a ≤ q + a ≤ ∞. Note that, both potential bounds and flow capacities can be infinite, such that this general setting can be easily applied to the case of unbounded potentials or uncapacitated flows.

Moreover, we are given a potential function for every arc a ∈ A that is determined by technical properties of the pipe it represents. This potential function links the flow on an arc with the potentials on its endpoints. It can be defined as follows; see, e.g., [START_REF] Groß | Algorithmic Results for Potential-Based Flows: Easy and Hard Cases[END_REF]. Definition 1 (Potential functions). The potential function of an arc a ∈ A is a function Φ a : R → R that satisfies the following properties:

(i) Φ a is continuous, (ii) Φ a is strictly increasing, and (iii) Φ a is odd, i.e., Φ a (-x) = -Φ a (x).

For the case of steady-state network flow models, flows and potentials are governed by Kirchhoff's first law and a special variant of the second law [START_REF] Kirchhoff | Ueber Die Auflösung Der Gleichungen, Auf Welche Man Bei Der Untersuchung Der Linearen Vertheilung Galvanischer Ströme Geführt Wird[END_REF]. First, we have flow conservation on every node v with respect to (w.r.t.) a given supply or demand q n v :

a∈δ out (v) q a - a∈δ in (v) q a = q n v for all v ∈ V.
Second, the flow on arc a = (u, v) is determined by the potential function of a depending on the potentials of its incident nodes u and v:

π u -π v = Φ a (q a ) for all a = (u, v) ∈ A.
Definition 2 (Feasible potentials and flows). Given supply or demand q n v for every node v, potentials π v for every node v and flows q a for every arc a are feasible if and only if they satisfy

a∈δ out (v) q a - a∈δ in (v) q a = q n v for all v ∈ V, (1a)
π u -π v = Φ a (q a ) for all a ∈ A, a = (u, v), (1b)
π v ∈ π - v , π + v for all v ∈ V, (1c)
q a ∈ q - a , q + a for all a ∈ A. (1d)
System (1) can be rewritten in matrix notation using the node-arc incidence matrix M. We introduce the notation q := (q a ) a∈A to denote the vector of all arc flows. Other quantities are collected in vectors in a similar way. We then obtain

Mq = q n , (2a)
M π = Φ(q), (2b)
π ∈ π -, π + , (2c)
q ∈ q -, q + . (

Example 3. We consider three examples for which steady-state physical flows can be approximated using a potential-based flow model. (i) Gas transport networks: The physical nature of gas flow is governed by partial differential equations; see e.g., [START_REF] Falk | Challenges in Optimal Control Problems for Gas and Fluid Flow in Networks of Pipes and Canals: From Modeling to Industrial Applications[END_REF]. If one models stationary gas flows, these relations can be approximated by an algebraic equation coupling the mass flow on the arc and the difference of squared pressures at its incident nodes; see, e.g., Chapter [START_REF] Fügenschuh | Chapter 2: Physical and Technical Fundamentals of Gas Networks[END_REF] in the book [START_REF] Koch | Evaluating Gas Network Capacities[END_REF]. More precisely, for an arc a = (u, v), it holds that

exp(δh u )p 2 u -exp(δh v )p 2 v = Λ a exp(δh v ) -exp(δh u ) δ(h v -h u ) |q a |q a ,
where δ > 0, p u is the pressure at node u and h u is its altitude. The factor Λ a is the so-called pressure loss factor of the pipe a, which is determined by several technical factors such as the length of the pipe, its diameter, and the roughness of the pipe's inner wall. The modelling as a potential-based flow (2) follows from identifying for any node v and any pipe a = (u, v)

π v := exp(δh v )p 2 v , Φ a (q a ) := Λ a exp(δh v ) -exp(δh u ) δ(h v -h u ) |q a |q a .
For pipes without altitude difference the above model simplifies to

p 2 u -p 2 v = Λ a |q a |q a , i.e., we have potentials π v = p 2
v and the potential functions is given by Φ a (q a ) = Λ a |q a |q a .

(ii) Water transport networks: Hydraulic heads in water networks can also be interpreted as potentials. The head-loss model is then a special-case of (2)

with, for any pipe a, Φ a (q a ) := β a sign(q a )|q a | 1.852 , where β a > 0 is a pipe-specific constant. For more details on the modelling of water transport networks we refer to [START_REF] Larock | Hydraulics of Pipeline Systems[END_REF]. (iii) Lossless DC power flow networks: Lossless DC power flows can be modelled as a potential-based flow (2) with linear potential functions. Given a line a and its susceptance B a , the potential function is defined as

Φ a (q a ) := 1 B a q a .
In this case, the potentials correspond to phase angles. We refer the interested reader to [START_REF] Kirschen | Transmission Networks and Electricity Markets[END_REF] and the references therein for an insight to some important power flow problems. Lastly, we note that AC power flows are not captured within our framework.

Nominations and Bookings in the European

Entry-Exit Gas Market System. In the following, we briefly sketch the notions of nominations and bookings in the European entry-exit gas market system. For more details we refer the interested reader to [START_REF] Grimm | A Multilevel Model of the European Entry-Exit Gas Market[END_REF] and the references therein. In this system, the TSO signs a contract with every supply and demand customer. This contract specifies the maximum amount of flow that the customer is allowed to inject to (at entry nodes v ∈ V + ) or withdraw from (at exit nodes v ∈ V -) the network. These capacity right contracts are called bookings. Furthermore, the booking at transition nodes v ∈ V 0 is always assumed to be zero. We denote by q b ∈ R V ≥0 the vector of all bookings in the network.

On a day-ahead basis, the customers have to commit for a nomination for the next day. That is, they nominate the actual amount of flow to be injected or withdrawn at the next day. We denote by q n ∈ R V the vector of all nominations. We are interested in the nominations that comply with the booking q b . This is formalised in the following definition.

Definition 4 (Booking-compliant nominations). For a given booking q b ∈ R V ≥0 , a nomination vector q n ∈ R V is called booking-compliant if and only if it satisfies

q n v ∈ 0, q b v for all v ∈ V + , (3a)
q n v ∈ -q b v , 0 for all v ∈ V -, (3b)
q n v = 0 for all v ∈ V 0 , (3c)
v∈V

q n v = 0. (3d)
We denote by Q n (q b ) the polytope of booking-compliant nominations w.r.t. the booking q b , as defined by System (3).

We now give the definition of a feasible nomination.

Definition 5 (Feasible nominations). A given nomination q n ∈ Q n (q b ) is feasible, if and only if there are potentials π ∈ R V ≥0 and flows q ∈ R A that satisfy System (2).

A key aspect of the European entry-exit gas market system is that the TSO has to guarantee the feasibility of every booking-compliant nomination. We thus define a feasible booking as follows.

Definition 6 (Feasible bookings). A booking q

b ∈ R V ≥0 is feasible if and only if every booking-compliant nomination q n ∈ Q n (q b ) is feasible.
Note that, even though we have shown several examples of potential-based flow networks in Example 3, the described notions of nominations and bookings are only used in gas transport networks. These gas networks and the underlying market system in Europe is our motivation for the analyses in this paper.

Characterisation of Feasible Bookings

In this section, we present a characterisation of feasible bookings, based on an extension of the characterisation of feasible nominations given in Theorem 1 of [START_REF] Gotzes | On the Quantification of Nomination Feasibility in Stationary Gas Networks with Random Load[END_REF].

It is well-known that rank(M) = |V | -1 holds for connected graphs. Moreover, by choosing a reference node 0 ∈ V and a spanning tree T of G, we can decompose the incidence matrix M. Let B := A(T ) be the arcs of T and N := A(G) \ A(T ) the remaining arcs. By reordering the arcs of the graph, we obtain

M = m 0B m 0N M B M N , where m 0 = m 0B m 0N ∈ R {0}×B
is the row vector corresponding to the reference node 0. The sub-matrix M B ∈ R (V \{0})×B , corresponding to arcs in B after deleting the row m 0 , is invertible. We call B the basis arcs of G and N the non-basis arcs. As noted above, |V | -1 rows of M are linearly independent. More precisely, it holds that

m 0B m 0N = -e M B M N , (4)
where e ∈ R V \{0} is the vector of all ones.

We introduce the notation x0 to denote a vector x of node quantities without the component corresponding to the reference node 0. Using this notation, we can rewrite Constraints (2a) and (2b) as

M B q B + M N q N = qn 0 , m 0B π 0 + M B π0 = Φ B (q B ), m 0N π 0 + M N π0 = Φ N (q N ).
Consequently, by using (4) we obtain

q B = M -1 B (q n 0 -M N q N ), (5a)
π0 = π 0 e + M - B Φ B M -1 B (q n 0 -M N q N ) , (5b)
Φ N (q N ) = M N M - B Φ B M -1 B (q n 0 -M N q N ) . (5c)
Constraint (5a) determines the flow on basis arcs corresponding to the spanning tree T as a function of the nomination and the flows on the non-basis arcs. Constraint (5b) yields the potential at every non-reference node as a function of the potential at the reference node 0. We introduce the function

g : R V × R N → R V with g(q n , q N ) := 0 M - B Φ B M -1 B (q n 0 -M N q N )
.

It represents the potential change caused by flow from the reference node 0 to any other node. This potential change depends both on the nomination q n and the non-basis flows q N . For the ease of presentation, we also introduce a function for the potential change between an arbitrary pair of nodes w 1 , w 2 ∈ V via

∆g w1w2 : R V × R N → R
with ∆g w1w2 (q n , q N ) := g w1 (q n , q N ) -g w2 (q n , q N ). (6) Finally, Constraint (5c) ensures that the potential change between any pair of nodes is the same along all flow paths connecting the two nodes.

To verify the feasibility of the nomination q n , it remains to find non-basis flows q N satisfying Constraint (5c) as well as a reference node potential π 0 such that all additional bounds are satisfied: First, the potentials as determined by Constraint (5b) need to satisfy (2c). Second, both the basis flows q B given by Constraint (5a) and the non-basis flows q N need to satisfy the arc capacities (2d).

We can now give an extension of Theorem 1 in [START_REF] Gotzes | On the Quantification of Nomination Feasibility in Stationary Gas Networks with Random Load[END_REF] in which arc capacities have not been considered. We present the result in a slightly different way that will be useful for establishing the characterisation of feasible bookings.

Theorem 7. Let G = (V, A) be a network with given potential bounds 0 ≤ π - v ≤ π + v ≤ ∞ for every node v ∈ V and arc capacities -∞ ≤ q - a ≤ q + a ≤ ∞ for every arc a ∈ A. Then, a nomination q n ∈ Q n (q b
) is feasible if and only if there exist non-basis flows q N that satisfy Constraint (5c) and

∆g w1w2 (q n , q N ) ≤ π + w1 -π - w2 for all w 1 , w 2 ∈ V, (7a)
q - a ≤ M -1 B (q n 0 -M N q N ) a ≤ q + a for all a ∈ B, (7b)
q - a ≤ q a ≤ q + a for all a ∈ N. (7c)
Proof. By the previous discussion, System [START_REF] Baumrucker | MPEC strategies for cost optimization of pipeline operations[END_REF] is equivalent to (5c) and

q a = M -1 B (q n 0 -M N q N ) a
for all a ∈ B, q a ∈ q - a , q + a for all a ∈ A,

π v = π 0 + g v (q n , q N ) for all v ∈ V, π v ∈ π - v , π + v for all v ∈ V.
For a fixed nomination q n and non-basis flows q N , a reference potential π 0 has to be determined such that

π 0 ∈ π - v -g v (q n , q N ), π + v -g v (q n , q N ) for all v ∈ V, (8)
because this implies that all potentials-as given by (5b)-satisfy the bounds (2c). Using Fourier-Motzkin elimination, we eliminate the reference potential π 0 from (8). Hence, we rewrite (8) equivalently by imposing π - w2 -g w2 (q n , q N ) ≤ π + w1 -g w1 (q n , q N ) for all w 1 , w 2 ∈ V. We conclude the proof using [START_REF] De | The Gas Transmission Problem Solved by an Extension of the Simplex Algorithm[END_REF].

The latter result can be interpreted as follows. A given nomination q n ∈ Q n (q b ) is feasible if and only if we can determine non-basis flows q N that satisfy the Constraint (5c) and Constraints [START_REF] Domschke | Combination of Nonlinear and Linear Optimization of Transient Gas Networks[END_REF]. As soon as q N is determined in this way, all flows and potentials are completely determined and satisfy their capacities and potential bounds, respectively. We will now see that it is always possible to determine unique non-basis flows q N that satisfy Constraint (5c). It then needs to be checked if the other constraints are satisfied by this unique flow solution.

To prove this claim, we make use of Theorems 3 and 4 in [START_REF] Roger | Preprocessing on Natural Gas Transmission Networks[END_REF]. They state that if C and D are orthogonal matrices, i.e., CD = DC = 0, and c is a given vector of supplies and demands, the system Cq = c, DΦ (q) = 0, admits a unique solution q ∈ R A . As a direct corollary of this result, we obtain that flows are uniquely determined by the nomination. Lemma 8. For every nomination q n ∈ Q n (q b ), the system formed by Constraints (5a) and (5c) admits a unique solution q ∈ R A .

Proof. Using the results of [START_REF] Roger | Preprocessing on Natural Gas Transmission Networks[END_REF], it is sufficient to observe that the system can be rewritten as

M B M N q = qn 0 , -M N M - B Id Φ(q) = 0,
where Id ∈ R N ×N denotes the identity matrix. Furthermore,

M B M N -M -1 B M N Id = -M N M - B Id M B M N = 0.
Example 9. The zero-nomination q n = 0 is booking-compliant for any booking q b and should therefore always be feasible. The unique flows associated with q n is given by Lemma 8 and we have q = 0. It follows that g(0, 0) = 0. We can rewrite Constraints (7) yielding

π + w1 ≥ π - w2 , for all w 1 , w 2 ∈ V, q - a ≤ 0 ≤ q + a ,
for all a ∈ A.

The zero-flow can then be realised by setting the potentials of all the nodes to a value

π ∈ v∈V [π - v , π + v ].
Hence, this is a necessary condition for a booking to be feasible. However, we will see that we do not need this additional assumption, since the infeasibility of the zero-nomination is automatically detected by the characterisation of feasible bookings that follows.

We can now give a characterisation of feasible bookings, based on Theorem 7 and Lemma 8.

Theorem 10. Let G = (V, A) be a network with given potential bounds 0 ≤ π - v ≤ π + v ≤ ∞ for every node v ∈ V and arc capacities -∞ ≤ q - a ≤ q + a ≤ ∞ for every arc a ∈ A. Then, a booking q b ∈ R V ≥0 is feasible if and only if it holds that ∆g * w1w2 ≤ π + w1 -π - w2 for all w 1 , w 2 ∈ V, (9a)
q - a ≤ q Ba ≤ q Ba ≤ q + a for all a ∈ B, (9b)
q - a ≤ q N a ≤ q N a ≤ q + a for all a ∈ N, (9c)
with ∆g * w1w2 := max q n ,q N ∆g w1w2 (q n , q N ) (10a) s.t. (5c) and q n ∈ Q n (q b ),

q Ba := max q n ,q N M -1 B (q n 0 -M N q N ) a (10b)
s.t. (5c) and q n ∈ Q n (q b ),

q Ba := min

q n ,q N M -1 B (q n 0 -M N q N ) a (10c)
s.t. (5c) and q n ∈ Q n (q b ),

q N a := max q n ,q N q a (10d) s.t. (5c) and q n ∈ Q n (q b ),
q N a := min q n ,q N q a (10e) s.t. (5c) and q n ∈ Q n (q b ).

Proof. First, assume by contradiction, that one of the constraints in ( 9) is violated. Without loss of generality, we consider the case in detail where there exists a pair

w 1 , w 2 ∈ V such that ∆g * w1w1 > π + w1 -π - w2 .
The other cases can be handled similarly. It follows that there is a nomination q n ∈ Q n (q b ) and non-basis flows q N satisfying Constraint (5c) with ∆g w1w2 (q n , q N ) > π + w1 -π - w2 . However, by Lemma 8, q N is the unique solution of Constraint (5c). As a consequence of Theorem 7, since q N does not satisfy Constraints [START_REF] Domschke | Combination of Nonlinear and Linear Optimization of Transient Gas Networks[END_REF], the booking-compliant nomination q n is infeasible. It follows that the booking q b is also infeasible.

Conversely, assume that q b ∈ R V ≥0 satisfies Constraints [START_REF] Fügenschuh | Chapter 2: Physical and Technical Fundamentals of Gas Networks[END_REF]. Let q n ∈ Q n (q b ) be any booking-compliant nomination. By Lemma 8, there are unique non-basis flows q N satisfying Constraint (5c). Furthermore, we have

∆g w1w2 (q n , q N ) ≤ ∆g * w1w2 ≤ π + w1 -π - w2 for all w 1 , w 2 ∈ V, q - a ≤ q Ba ≤ M -1 B (q n 0 -M N q N ) a ≤ q Ba ≤ q + a for all a ∈ B, q - a ≤ q N a ≤ q a ≤ q N a ≤ q + a for all a ∈ N.
It follows from Theorem 7 that the nomination q n is feasible.

Note that the existence and uniqueness of non-basis flows q N that satisfy Constraint (5c) is crucial for proving the previous theorem. In the first part of the proof, without uniqueness, we cannot be sure that there might not exist another solution q N that could satisfy all the constraints.

The interpretation of this result is similar to Theorem 7. For every constraint in [START_REF] Domschke | Combination of Nonlinear and Linear Optimization of Transient Gas Networks[END_REF], we determine a nomination that yields the largest violation, if any. We call these nominations stressful nominations in the following. In particular, we determine nominations that yield either large potential changes, or small and large arc flows. In order to certify the feasibility of the booking q b , it remains to check whether the network state corresponding to every stressful nomination does not violate any potential bounds or flow capacities. Note, however, that in general it is non-trivial to determine stressful nominations since the optimisation problems [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF] are both nonlinear and nonconvex problems.

Nonetheless, we can derive a first complexity result from Theorem 10.

Corollary 11. Verifying the feasibility of a booking q b ∈ R V ≥0 is in coNP.

Proof. A certificate for the infeasibility of booking q b is given by a nomination q n ∈ Q n (q b ) and its corresponding non-basis flows q N . The size of this certificate is bounded in the input size of the instance. Further, it can be verified that it is a valid certificate. We need to verify that Constraint (5c) holds. It then suffices to compute the objective values of Problems [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF] corresponding to (q n , q N ) and check that there is a violated constraint in [START_REF] Fügenschuh | Chapter 2: Physical and Technical Fundamentals of Gas Networks[END_REF]. This verification can be achieved in polynomial time and is sufficient to show infeasibility of the booking q b , since a stressful nomination yields larger (respectively smaller) objective values in Problems [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF].

As a final remark, observe that since the zero-nomination is always bookingcompliant, we obtain the necessary conditions of Example 9 as a consequence of Theorem 10, because

0 ≤ ∆g * w1w2 for all w 1 , w 2 ∈ V, q a ≤ 0 ≤ q a
for all a ∈ A, holds.

General Networks with Linear Potential Functions

In this section, we study the special case of verifying the feasibility of a booking q b ∈ R V ≥0 on a network with linear potential functions. We thus assume potential functions of the form Φ a (x) := φ a x for every arc a ∈ A. Here, φ a is a given constant. The time-complexity of this problem is obtained as a direct consequence of Theorem 10.

Theorem 12. The feasibility of a booking q b ∈ R V ≥0 can be verified in polynomial time on general networks with linear potential functions.

Proof. Note that the set of booking-compliant nominations Q n (q b ) is a polytope. Since all potential functions Φ are linear, the potential change function ∆g and Constraint (5c) are also linear. It follows that the problems [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF] are linear optimisation problems. To check whether q b is feasible, we need to solve O(|V |

2 ) linear programs and check the corresponding inequalities, which yields a polynomial time algorithm. This result represents an interesting consequence of the characterisation of feasible bookings given by Theorem 10. It has been shown in Section 3.2.3 of [START_REF] Hayn | Computing Maximal Entry and Exit Capacities of Transportation Networks-Complexity Analysis and a Discrete Relaxation Applied to Gas Transmission Systems[END_REF] that verifying the feasibility of a booking on a general network is coNP-complete, if the underlying linear transport model is given by Constraints (2a) and (2d). In the more general setting that we consider here, the author also shows in Section 3.3.2 the existence of an algorithm solving the problem with a time complexity of (4

|V | + 3 |A| + 2) κ with κ := (|V | + |A| + 1)(|V | + 1)
. By Theorem 12, we significantly improve this result by showing that on general networks the problem of verifying the feasibility of a booking is in P, when considering a potential-based flow with linear potential functions. The additional structure obtained by potential laws leads to existence and uniqueness of flows for every nomination, as we have shown in Lemma 8. This property is crucial for the proof of Theorem 10, which then leads to the final result in Theorem 12.

Tree-Shaped Networks with Nonlinear Potential Functions

In this section, we consider the special case of tree-shaped networks and nonlinear potential functions on every arc. For the remainder of this section, we therefore assume that T is a tree. In this situation, we can compute the matrix operations from Section 3 in a combinatorial way and show that the optimisation problems in (10) can be solved by dynamic programming in polynomial time. As a consequence of Theorem 10, this approach yields a closed form of the characterisation of feasible bookings on trees.

Let us first introduce some notation. The reference node 0 will be considered as the root of T . For the ease of presentation, we w.l.o.g. assume that all arcs in T are oriented away from 0, i.e., we consider rooted out-trees. Figure 2 shows an example of such a rooted out-tree. Further, we denote by L and I the set of leaves and interior nodes of T , respectively. For some v ∈ V , we denote by T (v) the sub-tree of T rooted in v. Thus, we have T = T (0).

Since we are considering trees, we have

A = B, N = ∅, M = m 0B M B .
There are no non-basis arcs and all flows are basis flows, i.e., q = q B . Furthermore, with N = ∅, the dependence on non-basis flows q N in System (5) vanishes. We can thus rewrite this system as

q = M -1 B qn 0 , (11a)
π = π 0 e + g(q n ), (11b)
where we redefine the potential change function

g : R V → R V as g(q n ) := 0 M - B Φ B M -1 B qn 0 .
As we have discussed in Section 3, g v (q n ) is the potential change caused by the flow, arising from nomination q n , between the root node 0 and an arbitrary node v. Since there is a unique path between every pair of nodes in trees, Constraint (5c) does not apply. Recall that it guaranteed that the potential changes between pairs of nodes are the same for any flow path. In contrast to general networks and System (5), all flows and potentials on trees are completely determined by the nomination q n and the reference potential π 0 through System [START_REF] Geißler | Towards Globally Optimal Solutions for MINLPs by Discretization Techniques with Applications in Gas Network Optimization[END_REF] and does no longer depend on any non-basis flows q N . The flow on a given arc a = (u, v) is determined by the nomination corresponding to the sub-tree of T rooted in v. It is not hard to observe that, by flow conservation (1a), any flow reaching the sub-tree has to pass through a. Therefore, the flows determined by Constraint (11a) can be obtained as given in the following lemma.

Lemma 13. Let q n ∈ Q n (q b ) be a booking-compliant nomination. For any v ∈ V \ {0}, let δ in (v) = {a}, and the flow on arc a is given by

q a = - w∈V (T (v)) q n w . ( 12
)
Proof. Take v ∈ L. Since v is a leaf, a is the only arc incident to v and V (T (v)) = {v}.

Therefore, the flow conservation on v reduces to q a = -q n v . Next, we consider v ∈ V \ {0}. By induction, we assume that the statement holds for every w ∈ V out (v). Using flow conservation on v, we obtain

w∈V out (v)
q vw -q a = q n v .

By using the induction hypothesis, we then get

q a = -q n v + w∈V out (v) q vw = -q n v + w∈V out (v)   - u∈V (T (w)) q n u   = - u∈V (T (v))
q n u .

We can solve Constraint (11b) in a similar way, thus obtaining all potentials w.r.t. the reference potential. For u, v ∈ V , we define P (u, v) ⊆ A to be the set of arcs corresponding to the unique undirected path between u and v in T . The potential π w on every node w can be computed uniquely by propagation of the root node potential π 0 along the unique path P (0, w). Lemma 14. Let q n ∈ Q n (q b ) be a booking-compliant nomination. For any node w ∈ V , its potential π w is given by

π w = π 0 + (u,v)∈P (0,w) Φ uv   l∈V (T (v)) q n l   ,
where π 0 is the potential on the root node 0.

Proof. The statement clearly holds for w = 0. Thus, take w ∈ V out (0). Constraint (1b) for the arc (0, w) is equivalent to

π w = π 0 -Φ 0w (q 0w ).
Recall that the potential function is odd. Using [START_REF] Geißler | The MILPrelaxation approach[END_REF], we obtain the desired base case.

Next, take an arbitrary node w ∈ V \ {0}. By induction, we assume that the statement holds for v ∈ V in (w). Constraint (1b) corresponding to arc (v, w) can be transformed yielding

π w = π v -Φ vw (q vw ) = π v + Φ vw   l∈V (T (w)) q n l   ,
where the second equality again follows from [START_REF] Geißler | The MILPrelaxation approach[END_REF]. Applying the induction hypothesis, we get

π w = π 0 + (c,d)∈P (0,v) Φ cd   l∈V (T (v)) q n l   + Φ vw   l∈V (T (w)) q n l   ,
which gives the desired result since P (0, w) = P (0, v) ∪ {(v, w)} holds.

As a consequence of the last lemma, the potential change from the root node 0 to any other node w is given by

g w (q n ) = (u,v)∈P (0,w) Φ uv   l∈V (T (v))
q n l   with the usual rule that the sum over an empty set evaluates to zero, i.e., g 0 = 0.

For the special case of trees, we can reformulate Theorems 7 and 10. As discussed, Constraint (5c) does not apply for trees and further simplifications arise from Lemmas 13 and 14 as well as the fact that all arcs are basis arcs, i.e., B = A and N = ∅.

Corollary 15. Let T = (V, A) be a tree with given potential bounds

0 ≤ π - v ≤ π + v ≤ ∞ for every node v ∈ V and arc capacities -∞ ≤ q - a ≤ q + a ≤ ∞ for every arc a ∈ A. Then, a nomination q n ∈ Q n (q b ) is feasible if and only if ∆g w1w2 (q n ) ≤ π + w1 -π - w2 for all w 1 , w 2 ∈ V, q - uv ≤ - l∈V (T (v))
q n l ≤ q + uv for all (u, v) ∈ A.

Corollary 16. Let T = (V, A) be a tree with given potential bounds

0 ≤ π - v ≤ π + v ≤ ∞ for every node v ∈ V and arc capacities -∞ ≤ q - a ≤ q + a ≤ ∞ for every arc a ∈ A. Then, a booking q b ∈ R V ≥0 is feasible if and only if it holds that ∆g * w1w2 ≤ π + w1 -π - w2 for all w 1 , w 2 ∈ V, q - uv ≤ q uv ≤ q uv ≤ q + uv for all (u, v) ∈ A, with ∆g * w1w2 := max q n ∈Q n (q b ) ∆g w1w2 (q n ), (13a)
q uv := max

q n ∈Q n (q b ) - l∈V (T (v)) q n l , (13b)
q uv := min

q n ∈Q n (q b ) - l∈V (T (v)) q n l . (13c)
Since the booking-compliant nominations Q n (q b ) form a polytope and because the objective functions are linear, Problems (13b) and (13c) are linear optimisation problems that can be solved efficiently. However, for nonlinear potential functions Φ, Problem (13a) is a nonlinear and nonconvex optimisation problem. Fortunately, we can show that Problem (13) can be solved efficiently by dynamic programming.

Given the monotonicity of the potential functions Φ, the most stressful nomination for a given arc (u, v) ∈ A is obtained by maximising the flow in both directions on this arc. This is formalised in the next lemma.

Lemma 17. For a given arc (u, v) ∈ A, it holds arg max

q n ∈Q n (q b ) Φ uv   l∈V (T (v)) q n l   = min    k∈V-\V (T (v)) q b k , k∈V+∩V (T (v)) q b k    and arg min q n ∈Q n (q b ) Φ uv   l∈V (T (v)) q n l   = -min    k∈V+\V (T (v)) q b k , k∈V-∩V (T (v)) q b k    .
Proof. We consider the maximisation problem in detail. The minimisation problem can then be solved similarly. Since the potential function Φ uv is non-decreasing, we only need to show that arg max

q n ∈Q n (q b ) l∈V (T (v)) q n l = min    k∈V-\V (T (v)) q b k , k∈V+∩V (T (v)) q b k    holds.
Interpreting the nomination q n l as the amount of item l ∈ V (T (v)) to be loaded, this problem can be transformed into a knapsack problem with continuous variables; see [START_REF] Kellerer | Knapsack Problems[END_REF] for a general treatment of knapsack problems. This view has the advantage that we can solve it using a greedy algorithm as proposed in [START_REF] Dantzig | Discrete-Variable Extremum Problems[END_REF].

First, observe that the balance constraint v∈V q n v = 0 can be written as

l∈V (T (v)) q n l = - k∈V \V (T (v)) q n k ≤ k∈V-\V (T (v)) q b k ,
where the right-hand side of the inequality is the maximum load of the knapsack. We want to maximise the total weight of the knapsack while only considering nodes in V (T (v)). The variables of this problem are therefore given by q n l for l ∈ V (T (v)). Since all the profits are positive, it is enough to only impose upper bounds derived from Q n (q b ). Consequently, the problem we need to solve is given by max

q n l∈V (T (v)) q n l s.t. l∈V (T (v)) q n l ≤ k∈V-\V (T (v)) q b k , q n l ≤ q b l for all l ∈ V + ∩ V (T (v)), q n l ≤ 0 for all l ∈ (V -∪ V 0 ) ∩ V (T (v)).
To apply the greedy algorithm, let

V * ⊆ V + ∩ V (T (v)) be such that l∈V * q b l ≤ k∈V-\V (T (v)) q b k and let w ∈ (V + ∩ V (T (v))) \ V * such that l∈V * ∪{w} q b l > k∈V-\V (T (v)) q b k holds, if it exists. Otherwise, we have V * = V + ∩ V (T (v))
. The optimal solution is then given by

(q n v ) * =          q b v , if v ∈ V * , k∈V-\V (T (v)) q b k - l∈V * q b l , if v = w, 0, if v ∈ V \ (V * ∪ {w}) .
This completes the proof.

As a by-product of this result, we also obtain a closed-form expression for the maximum flow in both directions on every arc (u, v) ∈ A by using [START_REF] Geißler | The MILPrelaxation approach[END_REF]. Consequently, we have

q uv = min    k∈V+\V (T (v)) q b k , k∈V-∩V (T (v)) q b k    , (14a)
q uv = -min    k∈V-\V (T (v)) q b k , k∈V+∩V (T (v)) q b k    . (14b)
In particular, the flows given in ( 14) can be computed in O(|V |) using depthfirst search. With Lemma 17 at hand, we can now determine the most stressful nominations in terms of the potential change between the root node 0 and any other node w ∈ V .

Theorem 18. For all w ∈ V , we have max

q n ∈Q n (q b ) g w (q n ) = (u,v)∈P (0,w) Φ uv (-q uv )
and

min q n ∈Q n (q b ) g w (q n ) = (u,v)∈P (0,w)
Φ uv (-q uv ).

Proof. We again consider the maximisation problem in detail. The minimisation problem can then be tackled using the same techniques. It is easy to see that max

q n ∈Q n (q b ) g w (q n ) ≤ (u,v)∈P (0,w) max q n ∈Q n (q b ) Φ uv   l∈V (T (v)) q n l   . (15)
If we show that this inequality is satisfied with equality, the result follows from Lemma 17 and (14).

The idea to prove this is to use dynamic programming to determine a nomination q n ∈ Q n (q b ) that is optimal for all sub-problems on the right-hand side of [START_REF] Geißler | Solving power-constrained gas transportation problems using an MIP-based alternating direction method[END_REF]. Starting with the sub-tree T (w) and iterating backwards over P (0, w), we fix the entries of q n in such a way that the partial solution is optimal for the current sub-problem and that it is still possible to balance the nomination using nodes that have not yet been treated. Algorithm 1 presents the dynamic programming that achieves this goal.

First, consider the initial iteration where v = w = 0. The inequality in the while-condition in Line 3 does not hold since V * = ∅. Note that the quantity ρ(w) := k∈V-\V (T (w))

q b k - k∈V *
q n k is a valid upper bound for the value that the nomination q n l at a node l ∈ V + ∩ V (T (w)) can take. It indicates the largest value that can be balanced using nodes in V -\ V (T (w)) w.r.t. already fixed nomination values. On the other hand, the nomination q n l needs to satisfy its booking bound. We iterate over all untreated nodes in the sub-tree T (w) in Line 7. We fix the nomination of nodes l ∈ V + ∩ V (T (w)) to the largest possible value given by min{q b l , ρ(w)}. Moreover, we fix nominations corresponding to nodes l ∈ (V -∪ V 0 ) ∩ V (T (w)) to 0.

Algorithm 1 Dynamic programming for computing max{g w (q n ) : q n ∈ Q n (q b )} Require: node w ∈ V Ensure: q n ∈ arg max{g w (q n ) :

q n ∈ Q n (q b )} 1: v ← w, V * ← ∅ 2: while v = 0 do 3: while l ∈ V -∩ (V (T (v)) \ V * ) and k∈V-\V (T (v)) q b k -k∈V * q n k < 0 do 4: q n l ← -min{q b l , -( k∈V-\V (T (v)) q b k -k∈V * q n k )} 5: V * ← V * ∪ {l} 6:
end while 7:

while l ∈ V (T (v)) \ V * do 8:
if l ∈ V + then 9:

q n l ← min{q b l , k∈V-\V (T (v)) q b k -k∈V * q n k } 10:
else 11:

q n l ← 0 12:

end if 13:

V * ← V * ∪ {l} 14:

end while

15: v ← V in (v) 16: end while 17: while l ∈ V -\ V * do 18: q n l ← -min{q b l , k∈V * q n k } 19:
V * ← V * ∪ {l} 20: end while As a consequence, l∈V+∩V (T (w)) Lemma 17, this construction leads to an optimal solution of the subproblem in the right-hand side of (15) corresponding to w. We have V * = T (w) and let v be the unique predecessor of w in Line 15. This completes the while-iteration in Line 2 corresponding to node w.

q n l = min    k∈V-\V (T (w)) q b k , k∈V+∩V (T (w)) q b k    holds. By
If we observe that ρ(v) ≥ 0, we proceed as in the previous case. On the other hand, if ρ(v) < 0 there needs to be an exit node l ∈ V -∩ (V (T (v)) \ V * ) with q n l < 0. More precisely, while treating the nodes of T (v), we need to balance the total nomination given by the values fixed over V * that cannot be balanced in a later iteration. This is accomplished by the while-loop in Line 3. The total quantity to be withdrawn at nodes in T (v) is given by -ρ(v) and thus gives a lower bound for the nomination q n l for l ∈ V -∩ (V (T (v)) \ V * ). Another lower bound is again given by the booking. We thus fix the nomination q n l to -min{q b l , -ρ(v)} while ρ(v) < 0. The remaining steps are identical to the initial iteration.

More generally, the following invariant holds at the end of the while-iteration in Line 2 corresponding to node v:

V * = T (v) and k∈V * q n k = min    k∈V+∩V (T (v)) q b k , k∈V-\V (T (v)) q b k    .
It thus always holds ρ(v) ≥ 0 in Line 7.

The final while-loop in Line 17 extends the partial nomination vector to a complete balanced nomination q n ∈ Q n (q b ). By Lemma 17 and by construction, q n is optimal for every sub-problem of the right-hand side of [START_REF] Geißler | Solving power-constrained gas transportation problems using an MIP-based alternating direction method[END_REF]. Thus, equality holds, which concludes the proof.

More generally, we can determine stressful nominations in terms of a potential change between every pair of nodes w 1 , w 2 ∈ V . If we let w ∈ V be the last common node of P (0, w 1 ) and P (0, w 2 ), then it is not hard to see that the potential change between w 1 and w 2 is given by

∆g w1w2 (q n ) = (u,v)∈P (w,w1) Φ uv   l∈V (T (v)) q n l   - (u,v)∈P (w,w2) Φ uv   l∈V (T (v)) q n l   .
Since we are considering trees and by definition of w, for any pair of arcs (u 1 , v 1 ) ∈ P (w, w 1 ) and (u 2 , v 2 ) ∈ P (w, w 2 ), the sub-trees T (v 1 ) and T (v 2 ) do not share any nodes, i.e., V (T (v 1 )) ∩ V (T (v 2 )) = ∅. As a consequence, both sums in the expression for ∆g w1w2 (q n ) are separable. The idea is to maximise the first sum, similarly to Algorithm 1, and apply an adapted version of this algorithm to minimise the second sum. The resulting dynamic programming is given in Algorithm 2.

First, note that an inequality similar to [START_REF] Geißler | Solving power-constrained gas transportation problems using an MIP-based alternating direction method[END_REF] holds in this case as well. We show that this inequality is satisfied with equality by constructing a suitable nomination with this property. In Lines 3-17, we thus apply the maximisation techniques depicted in Algorithm 1 over sub-trees of nodes covered by the path P (w, w 1 ). On the other hand, in Lines 19-33 we apply a "symmetric" construction for sub-trees of nodes covered by path P (w, w 2 ). The procedure is essentially the same after exchanging entries and exits and their corresponding quantities in Algorithm 1. Similarly to the proof of Theorem 18, the quantity

ρ(v) := k∈V+\V (T (v)) q b k + k∈V * q n k
is a valid upper bound on the amount to be extracted at l ∈ V -∩ (V (T (v)) \ V * ), the other bound being again given by the booking. If ρ(v) < 0, there has to be a node l ∈ V + ∩ (V (T (v)) \ V * ) with q n l > 0. The necessary minimal injection is then given by -ρ(v). This construction leads again to an extension of partial solutions q n in the sense of Lemma 17. It remains to complete the nomination q n in such a way that it is balanced. This is achieved in Lines 34-41, while treating entries and exits independently. This discussion in particular proves the following result.

Corollary 19. For given w 1 , w 2 ∈ V , let w ∈ V be the last common node of P (0, w 1 ) and P (0, w 2 ). Then,

∆g * w1w2 = (u,v)∈P (w,w1) Φ uv (-q uv ) - (u,v)∈P (w,w2) Φ uv (-q uv )
holds.

In order to determine the most stressful nominations on a tree it is thus sufficient to generate 2 |A| nominations yielding a maximum flow in both directions on every arc. As we have seen in the proof of Lemma 17, this can be done by dynamic programming for solving a continuous knapsack problem. Formally, we have the following complexity result.

Theorem 20. Verifying the feasibility of a booking q b ∈ R V ≥0 on trees with nonlinear potential functions is in P. More precisely, it can be done in O(|V |

2 ).

Proof. We check the feasibility of booking q b using Corollary 16. To this end, we generate q uv and q uv for every arc (u, v) ∈ A using ( 14). This is achieved in O(|V |).

Algorithm 2 Dynamic programming for computing ∆g * w1w2

Require: nodes w 1 , w 1 ∈ V Ensure: q n ∈ arg max{∆g w1w2 (q n ) : q n ∈ Q n (q b )} 1: w ← last common node of P (0, w 1 ) and P (0, w 2 )

2: v ← w 1 , V * ← ∅ 3: while v = w do 4: while l ∈ V -∩ (V (T (v)) \ V * ) and k∈V-\V (T (v)) q b k -k∈V * q n k < 0 do 5: q n l ← -min{q b l , -( k∈V-\V (T (v)) q b k -k∈V * q n k )} 6:
We finish this section with some remarks on the tree case. In [START_REF] Robinius | Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks[END_REF], the authors consider the problem of robust discrete arc sizing for potential-based trees. This problem consists in determining optimal diameters for the pipes in a tree network such that a certain set of nominations is feasible. This can be used to cover the case of bookings as well. Further assuming that every pipe can take only a single diameter, namely the one in place in the existing network, we can verify the feasibility of the booking q b using the approach of robust discrete arc sizing. In Lemma 4.5 of [START_REF] Robinius | Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks[END_REF] it is shown that this leads to a time complexity of O(|V | 4 ). When only considering the sub-problem of verifying feasibility over trees, we have managed to improve this complexity to O(|V |

2 ). However, let us also remark that the main goal of [START_REF] Robinius | Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks[END_REF] is different to ours and our setting is only contained there as a special case. Thus, it reasonable that our tailored solution approach outperforms the one in [START_REF] Robinius | Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks[END_REF].

Note also that we can restate the characterisation of feasible bookings from Corollary 16 under a closed form involving only the booking q b . It is sufficient to replace the corresponding quantities by using Corollary 19 and (14). As a final remark, it is also interesting to point out that the results of this section can easily be extended to series-parallel networks, since they can be reduced to trees [START_REF] Groß | Algorithmic Results for Potential-Based Flows: Easy and Hard Cases[END_REF] in our potential-based setting.

Conclusion and Open Problems

In this paper we have studied the problem of verifying the feasibility of a set of bookings as they are used in the European entry-exit gas market system. To this end, we introduced the basic notions of feasible nominations and bookings. Then, we proved a characterisation of feasible bookings for potential-based flow models. This characterisation is based on an extension of the characterisation of feasible nominations presented in [START_REF] Gotzes | On the Quantification of Nomination Feasibility in Stationary Gas Networks with Random Load[END_REF]. Our characterisation of feasible bookings is given in terms of inequalities on the optimal values of well-chosen optimisation problems. We applied this result to the special cases of (i) linear potential functions on general networks and (ii) nonlinear potential functions on trees. As a consequence, we showed that the feasibility of a set of bookings can be verified in polynomial time in both cases. In contrast, we have shown that the problem on general networks with nonlinear potential functions is in coNP. By these results, it has become obvious that the hardness of the problem depends both on characteristics of the physical flow model and the structure of the network.

There are still open problems since the exact border between easy and hard variants of this problem is not yet entirely known. Figure 3 summarises what is presently known regarding the problem of feasible bookings on trees and cyclic networks under different flow models.

We first discuss the upper part of the figure where a classical linear flow model is imposed for the underlying physics. It is not hard to observe that if there are no arc capacities, every balanced nomination is feasible and thus also every booking is. On the other hand, when capacities are given, it is shown in [START_REF] Hayn | Computing Maximal Entry and Exit Capacities of Transportation Networks-Complexity Analysis and a Discrete Relaxation Applied to Gas Transmission Systems[END_REF] that the problem is solvable in polynomial time on trees, but is coNP-complete on general, i.e., cyclic networks.

In the lower part of the figure, we illustrate cases using a potential-based flow model. Again, it is not hard to observe that every nomination and booking is feasible on an uncapacitated network without potential bounds. On the other hand, if either arc capacities or potential bounds are given the hardness depends on the nature of the potential functions and the specific structure of the network. First, we have shown in this paper that the problem can be solved in polynomial time if all potential functions are linear. This holds independently of the network structure. Second, the same polynomial time solvability applies to trees with nonlinear potential functions. By a simple extension of the arguments given in [START_REF] Hayn | Computing Maximal Entry and Exit Capacities of Transportation Networks-Complexity Analysis and a Discrete Relaxation Applied to Gas Transmission Systems[END_REF] it can be shown that the problem is in P for the classical linear flow model on a single cycle. It, however, is not yet known if the problem is easy or hard for a single cycle and nonlinear potentialbased flows. Finally, nothing is known -at least to the best of our knowledge -for the case of networks with controllable elements like compressors or valves.

Networks". Martin Schmidt thanks the Deutsche Forschungsgemeinschaft for their support within projects A05 and B08 in the "Sonderforschungsbereich / Transregio 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks". This research has been performed as part of the Energie Campus Nürnberg (EnCN) and is supported by funding of the Bavarian State Government.

Figure 2 .

 2 Figure 2. Example of a rooted out-tree.

Figure 3 .

 3 Figure 3. Overview of known complexity results for the problem of feasible bookings

  Example of a stylised gas network and its incidence matrix M. Dashed arcs indicate entry or exit nodes.2.1. The Physics Model. The main motivation of this paper is to analyse structural properties of flows in gas networks. However, we will adopt a more general view of the underlying physical laws in terms of potential-based flows. In that way, it is possible to model flow problems with similar physical properties like electricity or water network flows. In contrast to classical flow models, potential-based flows are governed by potentials on every node of the network. Let us denote by π v the potential on node v ∈ V . Due to technical limitations, the potential on every node v needs to satisfy bounds, i.e.,

Acknowledgements

Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique -FNRS under Grant no PDR T0098.18. Fränk Plein thanks the Fonds de la Recherche Scientifique -FNRS for his Aspirant fellowship supporting the research for this publication. He also thanks the Deutsche Forschungsgemeinschaft for their support within the project Z01 in the "Sonderforschungsbereich / Transregio 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas

end while 8:

if l ∈ V + then 10:

q n l ← 0 13:

end if 14:

end while

end while 24:

if l ∈ V -then 26:

else 28:

end while

q n l ← min q b l , k∈V * q n k 40:

V * ← V * ∪ {l} 41: end while