Fränk Plein

Johannes Thürauf

Martine Labbé

Martin Schmidt

Bilevel Optimization Approaches to Decide the Feasibility of Bookings in the European Gas Market

Keywords: Mathematics Subject Classification. 90B10, 90C11, 90C35, 90C46, 90C90 Gas networks, Bilevel optimization, European entry-exit market, Bookings, Active elements. 1

The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors and control valves that do not lie on cycles of the network. Since these active elements allow the TSO to control the gas flow, the single-level approaches from the literature are no longer applicable. We thus present a bilevel approach to decide the feasibility of bookings in networks with active elements. Besides the classical Karush-Kuhn-Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations, which also lead to novel characterizations of feasible bookings in active networks. We compare the performance of our methods by a case study based on data from the GasLib.

Introduction

The main goal of the European entry-exit gas market is to decouple transport and trading of gas. The transmission system operator (TSO), who operates the network, and gas traders interact via so-called bookings. A booking represents a mid-to long-term contract between gas traders and the TSO that grants the gas traders a capacity right to inject, respectively withdraw, gas from the network at certain nodes up to this capacity. After signing these booking contracts, gas traders can nominate on a daily basis the actual quantities of gas within their booked capacities to be shipped through the network. In total, these so-called nominations have to be balanced and represent the quantities of gas that are injected at entry nodes or withdrawn at exit nodes in a single time period.

By signing a booking contract, the TSO is obliged to guarantee that every balanced and booking-compliant load flow can be transported through the network, which follows from the European directive [8] and the subsequent regulation [9] on the entry-exit gas market. Indeed, this condition decouples transport and trading, since after signing the booking contracts, the gas traders can nominate any balanced quantity of gas without considering any transport requirements of the network. However, from a mathematical point of view, deciding the feasibility of a booking poses a significant challenge since infinitely many different balanced load flows have to be checked for being transportable through the network.

First mathematical results regarding bookings are obtained in the PhD theses [START_REF] Hayn | Computing maximal entry and exit capacities of transportation networks[END_REF][START_REF] Willert | Validation of Nominations in Gas Networks and Properties of Technical Capacities[END_REF]. Some structural properties of bookings are analyzed in [START_REF] Willert | Validation of Nominations in Gas Networks and Properties of Technical Capacities[END_REF]. Further, the author of [START_REF] Hayn | Computing maximal entry and exit capacities of transportation networks[END_REF] studies the problem of deciding the feasibility of a booking as a quantifier elimination problem and present an algorithm that decides the feasibility of a booking in an active network up to a certain tolerance. The remaining literature regarding bookings focuses on the case of passive networks. In [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF], the so-called reservation-allocation problem is studied for linear flow problems, which is closely related to the feasibility of a booking. Later on, in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF], a characterization of feasible bookings is obtained, in which for each pair of nodes, a nonlinear optimization problem needs to be solved to global optimality. These nonlinear problems compute the maximum pressure difference between the corresponding two nodes that can be obtained within the considered booking. If these maximum pressure differences satisfy certain pressure bounds, the booking is feasible and otherwise, it is infeasible. This characterization can be used to decide the feasibility of a booking in polynomial time for passive, tree-shaped networks [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF] or passive, single-cycle networks [START_REF] Labbé | Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks[END_REF]. However, the problem is coNP-hard on passive networks in general [START_REF] Thürauf | Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard[END_REF]. Moreover, optimizing over the set of feasible bookings is hard even on tree-shaped networks [START_REF] Schewe | Computing technical capacities in the European entry-exit gas market is NP-hard[END_REF]. We note that deciding the feasibility of bookings can also be seen as a special twostage robust or adjustable robust optimization problem in which the uncertainty set consists of balanced and booking-compliant load flows. Exploiting this point of view, the authors of [START_REF] Aßmann | Exact Methods for Two-Stage Robust Optimization with Applications in Gas Networks[END_REF][START_REF] Aßmann | Decomposable robust two-stage optimization: an application to gas network operations under uncertainty[END_REF][START_REF] Robinius | Robust optimal discrete arc sizing for tree-shaped potential networks[END_REF] derive methods that can be used to decide the feasibility of bookings in passive networks. Moreover, results of booking feasibility are not restricted to the European entry-exit gas market, but can also be applied to other potential-based network problems such as network expansion under demand uncertainties. This is demonstrated, e.g., in [START_REF] Robinius | Robust optimal discrete arc sizing for tree-shaped potential networks[END_REF], where a robust diameter selection for hydrogen networks is computed that is protected against unknown future demand fluctuations.

Unfortunately, all these results in passive networks cannot be used directly to decide the feasibility of bookings in active networks. Switching from passive to active networks makes the problem even more challenging as it introduces binary decisions for switching on or off active elements such as compressors or control valves. These binary decisions have to be taken individually for each balanced load flow within the booking bounds, since the TSO is able to change the settings of the active elements. This additional degree of freedom leads us to consider the following bilevel structure. The upper-level adversarial player tries to find a balanced and booking-compliant load flow that cannot be transported. The TSO, acting as the lower-level player, uses the active elements to transport this "worst-case" load flow of the upper level through the network. Consequently, if the upper-level player finds a balanced and booking-compliant load flow that cannot be transported by the TSO in the lower level, then the booking is infeasible. Otherwise, it is feasible. For an introduction to bilevel optimization, we refer to the books [START_REF] Bard | Practical Bilevel Optimization[END_REF][START_REF] Dempe | Foundations of Bilevel Programming[END_REF] and the recent survey article [START_REF] Kleinert | A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization[END_REF]. In general, bilevel optimization has been successfully applied to many different problems in the context of energy networks; see [START_REF] Wogrin | Applications of Bilevel Optimization in Energy and Electricity Markets[END_REF]. Moreover, it has specifically been applied to find scenarios that lead to severe transport situations in passive gas networks with linear flow models; see, e.g., [START_REF] Hennig | Using Bilevel Optimization to Find Severe Transport Situations in Gas Transmission Networks[END_REF].

In this paper, we present a first stepping stone towards deciding the feasibility of bookings in networks with linearly modeled active elements and a nonlinear model for stationary gas transport. First, a bilevel model for validating bookings on networks with active elements is derived. Since even linear bilevel optimization is computationally hard, see [START_REF] Hansen | New branch-and-bound rules for linear bilevel programming[END_REF][START_REF] Jeroslow | The polynomial hierarchy and a simple model for competitive analysis[END_REF], and since we additionally consider nonlinear gas transport models, we assume that no active element is part of a cycle of the network; see, e.g., [START_REF] Aßmann | Decomposable robust two-stage optimization: an application to gas network operations under uncertainty[END_REF], where this assumption is used as well. This allows us to recast our model into a bilevel problem with mixed-integer nonlinear upper level and a linear lower level. We then develop different approaches to solve this challenging bilevel problem. First, the standard Karush-Kuhn-Tucker (KKT) approach is applied. We provide provably correct bounds on the lower-level primal and dual variables to be used in the linearization of the KKT complementarity constraints. Then, three closed-form expressions of the lower-level optimal value function are studied. Using these closedform formulas, we set up optimal-value-function reformulations of the presented bilevel model, which then lead to novel characterizations of feasible bookings in active networks. The obtained approaches are evaluated in a computational study for some instances of the GasLib [START_REF] Schmidt | GasLib -A Library of Gas Network Instances[END_REF]. The results show that the nonlinear gas flow model is computationally very challenging, which only allows for a limited comparison of the methods. Thus, we also conducted a computational study for a simplified linear flow model.

The remainder of this paper is structured as follows. In Section 2, we formally introduce the problem of deciding the feasibility of a booking in networks with active elements. In Section 3, we then illustrate why the methods for the case of passive networks cannot be applied and how active elements make the problem even more challenging. We present our bilevel models for deciding the feasibility of a booking for active networks in Section 4. Afterward, we provide the single-level KKT reformulation in Section 5 and discuss various optimal-value-function reformulations and characterizations of feasible bookings in active networks in Section 6. We then compare our methods in a computational study in Section 7. Finally, we summarize our results and discuss possible directions for future research in Section 8.

Problem Description

We now formalize the problem of deciding the feasibility of a booking in gas networks including compressors and control valves. We follow and extend the problem description in [START_REF] Labbé | Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks[END_REF], which deals with the feasibility of a booking for a single-cycle network without active elements. To this end, we consider linearly modeled active elements and stationary gas flows.

We model a gas network by a weakly connected and directed graph G = (V, A) with nodes V and arcs A. The set of nodes is partitioned into entry nodes V + , at which gas is injected, exit nodes V -, at which gas is withdrawn, and the remaining inner nodes V 0 . The set of arcs is partitioned into pipes A pipe and active elements A act , which can actively control the pressure. Further, the set of active elements is split into compressors A cm , which can increase the pressure, and control valves A cv , which can decrease the pressure.

We now introduce our framework for deciding the feasibility of a booking.

Definition 2.1. A load flow is a vector = ( u ) u∈V ∈ R V ≥0 with u = 0 for all u ∈ V 0 . The set of load flows is denoted by L.

A load flow represents an actual flow situation in the gas network. More precisely, u denotes the amount of gas that is injected at u ∈ V + and that is withdrawn at node u ∈ V -. Since we consider stationary gas flows, the quantities of gas injected and withdrawn from the network have to be balanced. This leads to the definition of a nomination. Definition 2.2. A nomination is a balanced load flow , i.e., u∈V+ u = u∈V-u . The set of nominations is given by

N :=    ∈ L : u∈V+ u = u∈V- u    .
A booking, on the other hand, represents a mid-to long-term contract in the European entry-exit gas market between the gas traders and the TSO that allows gas traders to inject or withdraw gas at certain nodes up to the booked capacity. To do so, the TSO is obliged to guarantee that all infinitely many booking-compliant nominations can be transported through the network. Formally, a booking can be defined as follows. In the following, we consider stationary gas flows based on the Weymouth pressure loss equation [START_REF] Weymouth | Problems in Natural Gas Engineering[END_REF]. In line with the corresponding literature [START_REF] Labbé | Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks[END_REF][START_REF] Schewe | Computing technical capacities in the European entry-exit gas market is NP-hard[END_REF][START_REF] Thürauf | Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard[END_REF], we model gas flow physics using potential-based flows, which for active networks consists of arc flows q = (q a ) a∈A , node potentials π = (π u ) u∈V , and controls ∆ = (∆ a ) a∈Aact . In the context of gas networks with horizontal pipes, potentials represent squared gas pressures at the nodes, i.e., π u = p 2 u for u ∈ V . We note that potential-based flow models are also capable of handling non-horizontal pipes; see [START_REF] Gross | Algorithmic Results for Potential-Based Flows: Easy and Hard Cases[END_REF]. For modeling active elements, a variety of different modeling approaches exist that range from simple linear to sophisticated mixed-integer nonlinear ones; see [START_REF] Fügenschuh | Chapter 2: Physical and technical fundamentals of gas networks[END_REF]. In this paper, we focus on linearly modeled active elements similar to [START_REF] Aßmann | Exact Methods for Two-Stage Robust Optimization with Applications in Gas Networks[END_REF]. A compressor or control valve a ∈ A act linearly increases, respectively decreases, potentials by ∆ a ∈ [0, ∆ + a ] and can only be active if a minimal quantity of flow m a ≥ 0 passes the arc in the "correct" direction, i.e., if q a > m a holds. We model an active element a = (u, v) ∈ A act by

π u -π v = -∆ a , if a ∈ A cm , ∆ a , if a ∈ A cv , ∆ a ∈ [0, ∆ + a χ a (q)],
where the indicator function χ a (q) is given by χ a (q) := 1, if q a > m a , 0, otherwise.

We note that explicitly modeling the indicator function χ a introduces binary variables in general, which we explicitly consider in Section 4. We can now formally define the feasibility of a nomination and a booking.

Definition 2.4. A nomination ∈ N is feasible if (q, π, ∆) exists that satisfies a∈δ out (u) q a - a∈δ in (u) q a =      u , u ∈ V + , -u , u ∈ V -, 0, u ∈ V 0 , (1a)
π u -π v = Λ a q a |q a |, a = (u, v) ∈ A pipe , (1b)
π u -π v = -∆ a , a = (u, v) ∈ A cm , ∆ a , a = (u, v) ∈ A cv , (1c)
∆ a ∈ [0, ∆ + a χ a (q)], a ∈ A act , (1d)
π u ∈ [π - u , π + u ], u ∈ V, (1e)
where δ out (u) and δ in (u) denote the sets of arcs leaving and entering node u ∈ V , Λ a > 0 is a pipe-specific constant for all a ∈ A pipe , 0 < π - u ≤ π + u are potential bounds for all u ∈ V , and 0 ≤ ∆ + a is an upper bound on the operation of an active element for all a ∈ A act .

Constraints (1a) ensure flow conservation at every node of the network. For pipes a ∈ A pipe , Constraints (1b) link the arc flow to the incident node potentials. For active elements a ∈ A act , Constraints (1c) determine the potentials incident to the active element according to its control ∆ a . Moreover, Constraints (1d) ensure that the active element operates in the allowed range, which is determined by technical restrictions. Finally, the potentials have to satisfy certain potential bounds, see Constraints (1e). The feasibility of a booking is then defined as follows.

∀ ∈ N (b) ∃(q, π, ∆) satisfying (1). (2)
Consequently, for checking the feasibility of a booking, possibly infinitely many booking-compliant nominations have to be checked for feasibility.

From a robust optimization perspective, Problem (2) can be seen as a special two-stage robust or adjustable robust optimization problem, see [START_REF] Ben-Tal | Robust optimization[END_REF]43] for more details. Here, the uncertainty set consists of all booking-compliant nominations N (b). Moreover, the robust problem consists only of so-called "wait-and-see" decisions given by (1) and no "here-and-now" decisions are made. The switch from passive to active networks makes Problem (2) even more challenging since it introduces binary "wait-and-see" decisions due to the indicator functions χ a for all a ∈ A act .

Why Active Elements Are Difficult

In this section, we first review a known characterization of the feasibility of a booking in passive networks as obtained in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF]. Afterward, we show that this characterization cannot be applied to the considered case with active elements, which illustrates the need for new methods to decide the feasibility of a booking in networks including active elements.

In passive networks, the feasibility of a given booking b can be characterized by computing the maximum potential difference for each pair of nodes; see Theorem 10 in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF]. For each pair of nodes (w 1 , w 2 ) ∈ V 2 , the authors introduce the nonlinear optimization problem

s v t   b π - π +   =   1 5 5     0 0 10     1 5 7   m (s,v) = 0 ∆ + (s,v) = 2 Λ (v,t) = 1
ϕ w1w2 (b) := max ,q,π π w1 -π w2 (3a) s.t. a∈δ out (u) q a - a∈δ in (u) q a =      u , u ∈ V + , -u , u ∈ V -, 0, u ∈ V 0 , (3b)
π u -π v = Λ a q a |q a |, a = (u, v) ∈ A, (3c) 0 ≤ u ≤ b u , u ∈ V. (3d)
The feasibility of a booking is then characterized by constraints on the optimal value function ϕ w1w2 (b) of (3).

Theorem 3.1 (Theorem 10 in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF]). Let G = (V, A) be a weakly connected and passive network and let b ∈ L be a booking. Then, the booking b is feasible if and only if for each pair of nodes (w 1 , w 2 ) ∈ V 2 , the corresponding optimal value ϕ w1w2 (b)

satisfies ϕ w1w2 (b) ≤ π + w1 -π - w2 . (4)
For passive tree-shaped or passive single-cycle networks, this characterization can be checked in polynomial time; see [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF][START_REF] Labbé | Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks[END_REF][START_REF] Robinius | Robust optimal discrete arc sizing for tree-shaped potential networks[END_REF]. However, the problem of validating a booking on general passive networks is known to be coNP-hard [START_REF] Thürauf | Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard[END_REF].

Unfortunately, the characterization given in Theorem 3.1 does not hold if active elements are present in the network, which we demonstrate by the following counterexample. To this end, we consider a tree G = (V, A) with corresponding lower and upper potential bounds π -and π + :

V := {s, v, t}, A := {(s, v), (v, t)}, π - s = π + s = 5, π - v = 0, π + v = 10, π - t = 5, π + t = 7
, where s ∈ V + is an entry node, t ∈ V -is an exit node, and v ∈ V 0 is an inner node. Furthermore, (s, v) ∈ A cm is a compressor that operates in the range ∆ (s,v) ∈ [0, 2] if q (s,v) > m (s,v) = 0 and otherwise, it is switched to bypass mode, i.e., ∆ (s,v) = 0. The arc (v, t) ∈ A pipe is a pipe with potential drop coefficient Λ (v,t) = 1. A graphical representation is given in Figure 1.

We consider the booking (b s , b v , b t ) = (1, 0, 1). By construction, every feasible point of (3) satisfies 0 ≤ q a ≤ 1 for all a ∈ A. To apply the passive characterization (4) to the active network G = (V, A), we set the active element to bypass mode and interpret it as a pipe with Λ (s,v) = 0. Consequently, it follows that the characterization conditions (4) are directly satisfied for every pair of nodes except of (s, t). For the latter pair of nodes, the booking-compliant nomination ( s , v , t ) = (1, 0, 1) is the optimal solution of (3) w.r.t. (s, t) with objective value ϕ st (b) = 1 and therefore violates the corresponding condition (4). Consequently, the booking is infeasible. However, this is wrong here since for every booking-compliant nomination ∈ N (b), we can explicitly construct a corresponding feasible point of (1) as follows: The zero nomination is feasible due to π u = 5 for all u ∈ V , q a = 0 for all a ∈ A, ∆ (s,v) = 0, and χ (s,v) (q) = 0. Thus, we now consider an arbitrary nonzero nomination ∈ N (b). The corresponding flows q are unique since G is a tree. We thus can construct the following feasible point of (1): [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF][START_REF] Dempe | Foundations of Bilevel Programming[END_REF] holds due to 0 ≤ q a ≤ 1 for all a ∈ A. This small counterexample illustrates that the existing characterization for deciding the feasibility of a booking in passive networks cannot be applied directly to the case of networks with active elements.

π s = 5, π v = 7, π t = 7 -q 2 (v,t) , ∆ (s,t) = 2, χ (s,v) (q) = 1, where π t = 7 -q 2 (v,t) ∈ [
Furthermore, the introduction of active elements may lead to a disconnected set of feasible nominations, which is proven to be connected for the case of passive networks; see [START_REF] Schewe | Structural properties of feasible bookings in the European entry-exit gas market system[END_REF]. We can observe this effect in our small counterexample by setting the threshold value m (s,v) = 0.5. Then, the set of nominations N (b) splits into infeasible nominations {( s , v , t ) = (x, 0, x) : x ∈ (0, 0.5]} and the set of feasible nominations {( s , v , t ) = (x, 0, x) : x ∈ (0.5, 1]} ∪ {(0, 0, 0)}, which are not connected. Consequently, the booking (b s , b v , b t ) = (1, 0, 1) is infeasible. We additionally note that the maximum potential difference between s and t is 0.25, which is obtained by the nomination (0.5, 0, 0.5) that differs from the optimal solution ϕ st (b) given by (1, 0, 1) of the passive characterization (4). Consequently, the usual monotonicity property of passive network, namely that more flow between a pair of nodes leads to a larger potential difference, is not satisfied in active networks anymore.

In the following section, we adapt the method of computing maximum potential differences to decide the feasibility of a booking in active networks using a bilevel approach. Choosing the tool of bilevel optimization is based on the following intuition. First, an arbitrary booking-compliant nomination is chosen. Afterward, the TSO controls the active elements to transport the nomination through the network. If this is possible for every booking-compliant nomination, then the booking is feasible. Otherwise, it is infeasible. We explore this bilevel perspective to derive new methods to decide the feasibility of a booking in networks with active elements.

Bilevel Modeling

We adapt the methodology of [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF] to validate a booking on networks with active elements by adequately computing nominations with maximum potential difference. As previously discussed, an analogous single-level optimization problem is not sufficient if active elements are present. Here, we consider a max-min bilevel optimization problem. The leader chooses a booking-compliant nomination ∈ N (b) that maximally violates potential bounds. The goal of the follower, i.e., the TSO, is to transport this nomination while minimizing the violation. The TSO determines flows q, potentials π, and controls ∆ of the active elements according to [START_REF] Aßmann | Exact Methods for Two-Stage Robust Optimization with Applications in Gas Networks[END_REF], where the potential bound intervals are adjusted using auxiliary variables y, z ∈ R. More precisely, for every node u

∈ V it is required that π u ∈ [π - u -y, π + u + z]. The bilevel problem is thus given by max ∈N (b) min q,π,∆,y,z y + z (5a) s.t. (1a)-(1d), π u + y ≥ π - u , u ∈ V, (5b)
π u -z ≤ π + u , u ∈ V. (5c)
The leader chooses a booking-compliant nomination and maximizes the sum of the violation y ∈ R of lower potential bounds and the violation z ∈ R of upper potential bounds. The follower transports the nomination through the network and chooses a control of the active elements to minimize the total potential bound violation, as modeled by (5b) and (5c). This max-min problem, where leader and follower share the same objective function, is part of a special class of bilevel optimization problems, which includes, e.g., interdiction-like problems; see [START_REF] Smith | A Survey of Network Interdiction Models and Algorithms[END_REF]42] and Section 6 of [START_REF] Kleinert | A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization[END_REF]. If there is a solution of (5) of value y +z > 0, then there exists an infeasible nomination.

In this case, the leader has chosen a nomination such that the follower cannot route flows without violating the potential bounds. In contrast, if y + z ≤ 0 holds for an optimal solution, then the corresponding booking is feasible. From the perspective of the TSO, this objective value measures how close within or how far outside of its physical capabilities the network is operated given a "worst-case" nomination w.r.t. the considered booking. The following result proves the correctness of Problem ( 5).

Proposition 4.1. Let G = (V, A) be a weakly connected network with linearly modeled active elements A act ⊆ A. Then, the booking b ∈ L is feasible if and only if the optimal value of (5) is nonpositive.

Proof. If y + z > 0, it is clear that there exists a nomination ∈ N (b) that violates either a lower potential bound (y > 0) or an upper potential bound (z > 0). Thus, the booking is infeasible in that case. Suppose now that for an arbitrary solution ( , q, π, ∆, y, z) of ( 5), it holds that y + z ≤ 0. If y, z ≤ 0, all booking-compliant nominations can be transported within the original potential bounds and the booking is feasible. If y > 0 and z ≤ -y, the nomination violates at least one lower potential bound π u = π - u -y < π - u for u ∈ V . Without changing flows q or the controls ∆, we consider new potentials πu := π u + y for all u ∈ V . Adapting the corresponding auxiliary variables ỹ := 0 and z := y + z ≤ 0, we have constructed a new solution ( , q, π, ∆, ỹ, z) of the same objective value without any violation of lower or upper potential bounds. The symmetric case of z > 0 and y ≤ -z can be treated analogously.

It has been discussed in Section 3 that the problem of validating the feasibility of a booking when considering active elements is difficult in general. This is reflected in Problem [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF], which is a bilevel problem with nonlinear and nonconvex lower level. Thus, to tackle this highly challenging problem we need to make the following structural assumption that allows us to derive a practically more tractable reformulation of the bilevel model considered so far.

Assumption 1. No active element is part of an undirected cycle in G.

We note that this assumption is also used in [START_REF] Aßmann | Exact Methods for Two-Stage Robust Optimization with Applications in Gas Networks[END_REF][START_REF] Aßmann | Decomposable robust two-stage optimization: an application to gas network operations under uncertainty[END_REF]. Figure 2 shows on the left a stylized gas network satisfying Assumption 1. Intuitively, Assumption 1 implies that there cannot be any flow along a cycle in the network. More precisely, flow in pipes always leads to a potential drop due to (1b), which for flows along a cycle would lead to mismatching starting and end potentials on that cycle. Such a mismatch could however be fixed by using active elements that act on that cycle in order to match starting and end potentials. Assumption 1 eliminates this possibility and allows us to show the uniqueness of the flows corresponding to any given nomination. To this end, we extend the results of [START_REF] Collins | Solving the Pipe Network Analysis Problem Using Optimization Techniques[END_REF][START_REF] Maugis | Étude de réseaux de transport et de distribution de fluide[END_REF][START_REF] Ríos-Mercado | A Reduction Technique for Natural Gas Transmission Network Optimization Problems[END_REF] for passive networks. Theorem 4.2. Suppose that Assumption 1 holds. Then, for a given nomination ∈ N , every feasible point (q, π) of (1a) and (1b) admits the same unique flows q and potential differences π u -π v are unique for all (u, v) ∈ A pipe .

Proof. We prove that flows q are uniquely determined by the nomination . The uniqueness of potential differences on pipes then directly follows from (1b). First, observe that by Assumption 1, the removal of an active element a ∈ A act decomposes the network G = (V, A) into two smaller networks. Moreover, after removing all active elements A act , the network G is split into disconnected and passive components.

If A act = ∅, the network G is passive and the result follows from [START_REF] Collins | Solving the Pipe Network Analysis Problem Using Optimization Techniques[END_REF][START_REF] Maugis | Étude de réseaux de transport et de distribution de fluide[END_REF]. By induction on |A act |, we show that the result also holds true in general. Thus, suppose that the result holds for networks with at most |A act | -1 active elements. We remove an arbitrary active element a ∈ A act from G, which results in two networks with fewer active elements G 1 = (V 1 , A 1 ) and G 2 = (V 2 , A 2 ). We assume w.l.o.g. that a = (s, t) with s ∈ V 1 and t ∈ V 2 . For every node u ∈ V , we define

σ u :=      1, if u ∈ V + , -1, if u ∈ V -, 0, if u ∈ V 0 .
Then, the balancedness of supply and demand of nomination implies that the arc flow q a is uniquely given by

q a = u∈V1 σ u u = - u∈V2 σ u u .
Starting from the nomination , we now construct another nomination ˜ for

G 1 that is balanced over V 1 . We define ˜ u := u for all u ∈ V 1 \ {s} and ˜ s := σ s s - w∈V1 σ w w .
All nodes in V 1 \ {s} keep the same nomination value. The modification at node s might change its role, i.e., it can either be an entry or an exit node. Thus, we also define σu := σ u for all u ∈ V 1 \ {s} and

σs := 1, if σ s s -w∈V1 σ w w ≥ 0, -1, if σ s s -w∈V1 σ w w < 0,
which exactly corresponds to the sign of σ s s -w∈V1 σ w w . In particular, we have produced a nomination for G 1 , since

u∈V1 σu ˜ u = u∈V1\{s} σ u u + σ s s - w∈V1 σ w w = 0.
By the induction hypothesis, the restriction of q to A 1 is uniquely determined. Symmetrical arguments can be applied to show that the restriction of q to A 2 is also unique. Finally, the result follows given the fact that

A = A 1 ∪ A 2 ∪ {a}.
The latter result implies that, once a nomination is given, most lower-level decisions in [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF] are already fixed by physics. The lower-level problem can thus be reduced to only include the remaining decision variables. Therefore, consider the collection of passive subnetworks obtained by removing all active elements from G, which we denote by G := {G 0 , G 1 , . . . , G |Aact| }. For convenience, we sometimes denote an active arc a ∈ A act by a

= (G i , G j ) if a = (u, v) for u ∈ V (G i ) and v ∈ V (G j ).
Then, by Assumption 1, the graph G = (G, A act ) obtained by merging passive subnetworks into single nodes is a tree. In line with [START_REF] Ríos-Mercado | Optimization problems in natural gas transportation systems: A state-of-the-art review[END_REF][START_REF] Ríos-Mercado | A Reduction Technique for Natural Gas Transmission Network Optimization Problems[END_REF], we call G the reduced network. Figure 2 illustrates a network (left) and its associated reduced network (right).

Using the rationale of [START_REF] Ríos-Mercado | A Reduction Technique for Natural Gas Transmission Network Optimization Problems[END_REF], it follows by Theorem 4.2 that the potentials corresponding to a nomination ∈ N are determined as soon as a reference potential in an arbitrary passive subnetwork G j ∈ G and the controls ∆ a of all active elements a ∈ A act are fixed. Exploiting this uniqueness of flows and potentials, the following result presents an equivalent reformulation of Problem [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF]. Therein, the upper level consists of a potential-based flow over G where all active elements are inactive, i.e., π u = π v for all (u, v) ∈ A act . The TSO then reacts by using the active elements, as well as a constant shift for the potentials of every passive subnetwork G j ∈ G. Intuitively, in addition to choosing a worst-case nomination, the upper-level player thus already fixes all physical quantities that are uniquely determined by the nomination, i.e., all flows and the potential differences on pipes. The lower level, on the other hand, consists of a problem containing only those decision variables that the TSO influences. In addition, this new bilevel structure allows us to linearly model the indicator function χ a for the activation of an element a ∈ A act using binary variables.

Theorem 4.3. Consider the bilevel problem max ,q,π,s y + z (6a)

s.t. (1a), (1b), (6b)
∈ N (b), (6c)
π u = π v , (u, v) ∈ A act , (6d)
q a ≤ m a (1 -s a ) + M s a , a ∈ A act , (6e)
s a ∈ {0, 1}, a ∈ A act , (6f)
(∆, τ, y, z) ∈ R( , q, π, s), (6g)
where M := min{ u∈V+ b u , u∈V-b u } is an upper bound on the flow on any arc and the set of lower-level solutions R( , q, π, s) is given by

arg min ∆,τ,y,z y + z (7a) s.t. τ i -τ j = -∆ a , a = (G i , G j ) ∈ A cm , ∆ a , a = (G i , G j ) ∈ A cv , (7b)
∆ a ∈ [0, ∆ + a s a ], a ∈ A act , (7c)
τ j + y ≥ π - u -π u , u ∈ V (G j ), G j ∈ G, (7d)
τ j -z ≤ π + u -π u , u ∈ V (G j ), G j ∈ G. ( 7e
)
Under Assumption 1, Problems (5) and (6) admit the same optimal value.

Proof. Let ( , q, π, ∆, y, z) be a bilevel-feasible point of [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF]. In [START_REF] Ríos-Mercado | A Reduction Technique for Natural Gas Transmission Network Optimization Problems[END_REF], it is shown that for a passive network, all potentials are uniquely determined once a reference potential is fixed. In particular, all solutions of (1a) and (1b) are equivalent up to a constant shift in every passive subnetwork. Thus, potentials in every passive subnetwork G j ∈ G are of the form π u = π u ( ) + τ j for all u ∈ V (G j ), where π( ) is a solution of (1b) and (6d). Moreover, τ j ∈ R is an arbitrary shift of the potentials in G j . Constraints (7b) then also hold, since the potentials π satisfy (1c). It remains to model the indicator function χ. For every a ∈ A act , we set s a = 1 if and only if q a > m a . Since q a ≤ M , it follows that (6e) is satisfied. Consequently, ( , q, π( ), s, ∆, τ, y, z) is bilevel feasible for ( 6) and admits the same objective value.

For the converse, first note that for every a ∈ A act , Constraints (6e) guarantee that s a = 1 holds if q a > m a . Assume now that q a ≤ m a . Then, the leader's decision on s a is arbitrary. However, the lower level with s a = 1 is a relaxation of the lower level with s a = 0. Upper and lower level have the same objective function with opposing optimization directions. Consequently, there is a bilevel-optimal solution of (6) with s a = 0, and thus satisfying s a = χ a (q). Let ( , q, π, s, ∆, τ, y, z) be a bilevel-optimal solution of (6) with s a = χ a (q) for all a ∈ A act . Theorem 4.2 states that the flows q corresponding to and solving the System (1a) and (1b) are unique. If we denote these unique flows by q( ), then q = q( ) and every bilevel-feasible point of (5) also admits flows q( ). Let us now define πu := π u + τ j for all u ∈ V (G j ) and G j ∈ G. Then, ( , q, π, ∆, y, z) is bilevel-feasible for [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF] and admits the same objective function value.

To summarize, in this section we first presented a bilevel optimization model of the adversarial interplay of checking the feasibility of a booking. In the resulting Problem [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF], the upper-level player selects the worst possible nomination w.r.t. a violation of the potential bounds. The lower-level player, i.e., the TSO, determines flows, potentials, and a control of the active elements to minimize the violation. Exploiting the structure resulting from Assumption 1, we deduced that many of the physical quantities of the TSO's problem are already uniquely determined by the upper-level nomination. These observations led to Problem [START_REF] Collins | Solving the Pipe Network Analysis Problem Using Optimization Techniques[END_REF], where only variables that the TSO can actively control remain in the lower-level problem. Moving flow and potential variables to the upper level has, in particular, allowed us to linearly model the indicator functions χ. Note also that in Problem [START_REF] Collins | Solving the Pipe Network Analysis Problem Using Optimization Techniques[END_REF], the upper level is a mixed-integer nonlinear problem (MINLP), but the lower level is a linear problem (LP) for fixed upper-level decisions. In the next section, we will focus on Problem [START_REF] Collins | Solving the Pipe Network Analysis Problem Using Optimization Techniques[END_REF] and derive the classical KKT reformulation.

Karush-Kuhn-Tucker Reformulation

Problem ( 6) is a bilevel problem with mixed-integer variables. In general, these problems are strongly NP-hard, see, e.g., [START_REF] Hansen | New branch-and-bound rules for linear bilevel programming[END_REF]. Many approaches for bilevel problems with mixed-integer variables rely on the fact that the linking variables, i.e., the variables of the upper level that appear in the lower level, are all integers. This is not the case here since, in addition to the binaries s a for a ∈ A act , the potentials π u for u ∈ V link the upper and the lower level. However, we observe that the lower level of ( 6) is linear for every fixed upper-level decision. As a consequence, we can characterize the optimal solutions of the lower level using its KKT conditions. 5.1. Reformulation. Let us first consider the lower level's dual problem for fixed upper-level decision ( , q, π, s). We introduce dual variables α a for a ∈ A act for constraints (7b), δ - u and δ + u for u ∈ V corresponding to (7d) and (7e), and finally β a for a ∈ A act associated to the upper bound on ∆ a . The dual problem is then given by

max α,β,δ + ,δ - - a∈Aact ∆ + a s a β a + u∈V (π - u -π u )δ - u -(π + u -π u )δ + u (8a) s.t. a∈δ out (Gj ) α a - a∈δ in (Gj ) α a = u∈V (Gj ) (δ + u -δ - u ), G j ∈ G, (8b)
α a ≤ β a , β a ≥ 0, a ∈ A cm , (8c)
-α a ≤ β a , β a ≥ 0, a ∈ A cv , (8d)
u∈V δ + u = 1, u∈V δ - u = 1, (8e)
δ + u , δ - u ≥ 0, u ∈ V. (8f)
Let G be the reduced network obtained from G by merging all passive subnetworks. The dual problem (8) can then be interpreted as a flow problem on G. From that point of view, α represents dual flows, β are the capacities on arcs corresponding to active elements, and u∈V (Gj ) δ + u and u∈V (Gj ) δ - u are the supply and demand at each node G j . Constraints (8b) ensure dual flow balance. Note that the dual arc flows have an unconstrained sign, with the same interpretation as before, i.e., α a > 0 corresponds to flow in the direction of arc a ∈ A act , while α a < 0 represents flow in the opposite direction. For compressors a ∈ A cm , dual flows are bounded from above, i.e., flow in the direction of the arc is bounded, whereas for control valves a ∈ A cv , arc flows are bounded from below, i.e., flow in the opposite direction of the arc is bounded. Finally, total supply and demand equal one; see (8e).

The KKT conditions for the lower level consist of primal feasibility [START_REF] Dempe | Foundations of Bilevel Programming[END_REF], dual feasibility (8b)-(8f), and the complementarity constraints

δ - u (τ j + y + π u -π - u ) = 0, u ∈ V (G j ), G j ∈ G, (9a)
δ + u (τ j -z + π u -π + u ) = 0, u ∈ V (G j ), G j ∈ G, (9b)
β a (∆ a -∆ + a s a ) = 0, a ∈ A act , (9c)
(-α a + β a )∆ a = 0, a ∈ A cm , (9d)
(α a + β a )∆ a = 0, a ∈ A cv . (9e)
Consequently, Problem [START_REF] Collins | Solving the Pipe Network Analysis Problem Using Optimization Techniques[END_REF] 9) is via big-M linearizations; see [START_REF] Fortuny-Amat | A Representation and Economic Interpretation of a Two-Level Programming Problem[END_REF]. For a dual variable λ ≥ 0 and a primal constraint c(x) ≥ 0, the complementarity condition λc(x) = 0 is replaced by

λ ≤ M d u, c(x) ≤ M p (1 -u)
, where u ∈ {0, 1} is an auxiliary binary variable and M d , M p ≥ 0 are upper bounds for λ and c(x), respectively. It is shown in [START_REF] Kleinert | There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization[END_REF] that determining a bilevel-correct big-M is a hard task if problem-specific knowledge is lacking. In the following, by exploiting the structure of Problem (6), we obtain provably correct bounds on lower-level primal and dual variables that can be used in the linearization of (9). First, let us consider the lower-level's dual variables.

Lemma 5.1. Let ( , q, π, s) be feasible for (UL). Then, there is a corresponding optimal solution (α, β, δ + , δ -) of the lower level's dual problem (8) with α a ∈ [-1, 1] and β a ∈ [0, 1] for all a ∈ A act as well as δ + u , δ - u ∈ [0, 1] for all u ∈ V . Proof. If follows directly from (8e) and (8f) that δ + u , δ - u ∈ [0, 1] holds for all u ∈ V . Following the interpretation of the lower level's dual problem as a flow problem on G, it holds that |α a | ≤ 1 for all a ∈ A act , since the total demand and supply are both 1 and G is a tree under Assumption 1. Finally, by optimality it follows that β a ≤ 1 holds if for an arc a ∈ A act the inequality ∆ + a s a > 0 is satisfied. Otherwise, if ∆ + a s a = 0 holds for an arc a ∈ A act , then β a can be any nonnegative value. Next, we derive bounds for lower-level primal variables such that an optimal solution satisfying them always exists. Lemma 5.2. Let ( , q, π, s, ∆, τ, y, z) be a bilevel-feasible point of (6), then for any ε, ε ∈ R, the point ( , q, π + ε, s, ∆, τ + ε, y -ε -ε, z + ε + ε) is also bilevel feasible with the same objective value.

Proof. Let ( , q, π, s, ∆, τ, y, z) be a bilevel-feasible point of ( 6) and consider arbitrary but fixed ε, ε ∈ R. We now check the feasibility of the point ( , q, π + ε, s, ∆, τ + ε, y -ε -ε, z + ε + ε) for ( 6).

Since we have not changed the upper-level variables , q, and s, and have only shifted the potential π by ε, upper-level feasibility follows from Theorem 7.1 in [START_REF] Koch | Evaluating Gas Network Capacities[END_REF]Chapter 7]. We now turn to the lower level. Since the lower-level variables ∆ stay unchanged, Constraint (7c) holds. Moreover, Constraints (7b), (7d), and (7e) are satisfied due to

τ i + ε -τ j -ε + ω a ∆ a = τ i -τ j + ω a ∆ a = 0, a = (G i , G j ) ∈ A act , τ j + ε + y -ε -ε = τ j + y -ε ≥ π - u -π u -ε, u ∈ V (G j ), G j ∈ G, τ j + ε -z -ε -ε = τ j -z -ε ≤ π + u -π u -ε, u ∈ V (G j ), G j ∈ G.
This shows the feasibility of the considered point. Additionally, the objective values of both points are equal, which directly follows by construction.

Corollary 5.3. There is an optimal solution ( , q, π, s, ∆, τ, y, z) of (6) that satisfies min u∈V {π u } = 0 and min Gj ∈G

{τ j } = 0.
Using this result, we can bound the values π and τ in an optimal solution.

Lemma 5.4. There is an optimal solution ( , q, π, s, ∆, τ, y, z) of the bilevel problem (6) that satisfies

0 ≤ π u ≤ a∈A Λ a M 2 , u ∈ V, 0 ≤ τ j ≤ a∈Aact ∆ + a , G j ∈ G,
where M := min{ u∈V+ b u , u∈V-b u } is an upper bound on the flow on any arc.

Proof. Corollary 5.3 implies that there is an optimal solution ( , q, π, s, ∆, τ, y, z) of the bilevel problem ( 6) with u ∈ V and G j ∈ G that satisfies

min v∈V {π v } = π u = 0, min Gi∈G {τ i } = τ j = 0. (11)
For an arbitrary node v ∈ V , we now consider a path P (u, v), which consists of the arcs A(P (u, v)) ⊆ A corresponding to an undirected path from u to v in G.

Additionally, for an arc a = (s, t) ∈ A(P (u, v)), we introduce η a (P ), which evaluates to 1, if a is directed from u to v, and otherwise it evaluates to -1. Consequently, Constraint (1b) and Condition [START_REF] Fügenschuh | Chapter 2: Physical and technical fundamentals of gas networks[END_REF] imply

0 ≤ π v = π u - a∈P (u,v)∩Apipe η a (P )Λ a |q a |q a ≤ a∈Apipe Λ a M 2 .
In analogy, for an arbitrary G i ∈ G, Constraints (7b) and Condition [START_REF] Fügenschuh | Chapter 2: Physical and technical fundamentals of gas networks[END_REF] imply

0 ≤ τ i = τ j + a∈P (u,v)∩Acm η a (P )∆ a - a∈P (u,v)∩Acv η a (P )∆ a ≤ a∈Aact ∆ + a .
By carefully combining these lower and upper bounds, we can derive the big-M s required for the linearization of (9). In particular, for a lower-level primal optimal solution, we obtain

y = max Gj ∈G, u∈V (Gj ) π - u -π u -τ j , z = max Gj ∈G, u∈V (Gj )
π u + τ j -π + u .

Optimal-value-function Reformulations and Characterizations of Feasible Bookings

As an alternative to the KKT reformulation of Section 5, the bilevel problem (6) can also be reformulated using the lower level's optimal value function; see, e.g., [START_REF] Dempe | Foundations of Bilevel Programming[END_REF]. Let ϕ( , q, π, s) be the optimal value of ( 7) for given upper-level decisions ( , q, π, s). Note that the lower level [START_REF] Dempe | Foundations of Bilevel Programming[END_REF] is feasible for every ( , q, π, s), i.e., (LLP) always admits a feasible point. Thus, ( 6) is equivalent to max ,q,π,s {ϕ( , q, π, s) : (UL)} .

(

) 12
By strong duality of the lower level, ϕ is also the optimal value function of the lower level's dual problem (8). The latter is a linear problem with objective function parameterized by π and s. Thus, ϕ is a piecewise-linear and convex function. More precisely, given that the lower level is always feasible and bounded, the same holds for the lower-level's dual problem. The optimal value function ϕ can thus be expressed as the maximum over the lower level's dual objective function evaluated in a potentially exponential number of vertices of the feasible set of the lower level's dual problem. Consequently, the single-level reformulation ( 12) is a convex maximization problem over a nonconvex feasible set, which is a highly intractable problem class, in general.

6.1. The Optimal Value Function. We exploit the special structure of the lower level under Assumption 1 to express ϕ by polynomially many vertices of the polyhedral feasible set of the lower level's dual problem. To this end, let G be the reduced network corresponding to G. Additionally, for every two passive subnetworks G i , G j ∈ G, there exists a unique, undirected path joining them, which we denote by P (G i , G j ). Choosing any G k as the root of G, we can partition the active elements into arcs pointing away from or towards G k , i.e., A act = A k,→ act ∪A k,← act . Formally, we define

A k,→ act := {(G i , G j ) ∈ A act : P (G k , G i ) ⊆ P (G k , G j )} , A k,← act := A act \ A k,→ act .
In the following, we prove that for given δ + and δ -, the flow variables α can be uniquely determined using the conservation constraints (8b). Given that (8b) contains |A act | + 1 many linear equations and that the system is of rank |A act |, we can eliminate an arbitrarily chosen row. We denote by G 0 the passive subnetwork in G for which we delete the corresponding equation in (8b). Then, G 0 can be interpreted as the root of G and we can consider subtrees of G w.r.t. G 0 . If we remove an arc a ∈ A act in G, then the network decomposes into two subnetworks. For a ∈ A act and G j ∈ G, the set G a (G j ) denotes all passive sub-components that are contained in the subnetwork, which contains G j after removing arc a. In particular, the subtree of G "following" a is obtained by

G a (G j ) if a = (G i , G j ) ∈ A 0,→ act and by G a (G i ) if a = (G i , G j ) ∈ A 0,←
act . The solution of (8b) is then given by the following lemma. Lemma 6.1. Constraints (8b) are equivalent to

α a = - G l ∈Ga(Gj ) u∈V (G l ) δ + u -δ - u , a = (G i , G j ) ∈ A 0,→ act , (13a)
α a = G l ∈Ga(Gi) u∈V (G l ) δ + u -δ - u , a = (G i , G j ) ∈ A 0,← act . (13b)
Proof. For given supplies δ + and demands δ -, we already noted that α can be interpreted as a flow. Due to Constraints (8e), Constraints (8b), which ensure flow conservation in G, always admit feasible flows. For an arc a = (G i , G j ) ∈ A 0,→ act , the flow α a is determined by the net demand

D := G l ∈Ga(Gj ) u∈V (G l ) δ + u -δ - u
of the subtree "following" a. If D ≥ 0, a surplus in supply needs to leave the subtree over a flowing from G j to G i . Respecting the sign convention on the flow along directed arcs, it then holds α a = -|D| = -D. If D < 0, a surplus in demand needs to be shipped over a into the subtree, thus α a = |D| = -D. Similar arguments apply to a = (G i , G j ) ∈ A 0,← act . With this result at hand, we can explicitly determine the vertices of the polyhedral feasible set of the lower level's dual problem (8). Theorem 6.2. The vertices of the polyhedron (8) are given by [START_REF]General Algebraic Modeling System[END_REF] and

β a = max{α a , 0}, a ∈ A cm , β a = max{-α a , 0}, a ∈ A cv , δ + w1 = 1, δ + u = 0, u ∈ V \ {w 1 }, δ - w2 = 1, δ - u = 0, u ∈ V \ {w 2 }, for all pairs of nodes (w 1 , w 2 ) ∈ V 2 .
Proof. By Lemma 6.1, Constraints [START_REF]General Algebraic Modeling System[END_REF] uniquely determine α as a function of δ + and δ -. Furthermore, for every feasible point of (8), the constraints

β a ≥ max{α a , 0}, a ∈ A cm , β a ≥ max{-α a , 0}, a ∈ A cv ,
hold and have to be active at a vertex. It is therefore sufficient to determine the vertices of (8e) and (8f) in the space of δ + and δ -, which are given by

δ + w1 = 1, δ + u = 0, u ∈ V \ {w 1 }, δ - w2 = 1, δ - u = 0, u ∈ V \ {w 2 }
, for any pair of nodes (w 1 , w 2 ) ∈ V 2 . This concludes the proof.

Using this result and the network structure, we now elaborate on a representation of these vertices as follows. For any two nodes w 1 ∈ G j1 and w 2 ∈ G j2 , we introduce for any a = (G i , G j ) ∈ A 0,→ act ,

α a (w 1 , w 2 ) :=      -1, if G j1 ∈ G a (G j ), G j2 / ∈ G a (G j ), 1, if G j1 / ∈ G a (G j ), G j2 ∈ G a (G j ), 0, otherwise,
and for any a = (G i , G j ) ∈ A 0,← act ,

α a (w 1 , w 2 ) :=      1, if G j1 ∈ G a (G i ), G j2 / ∈ G a (G i ), -1, if G j1 / ∈ G a (G i ), G j2 ∈ G a (G i ), 0, otherwise.
Furthermore, for any a ∈ A act , we define

β a (w 1 , w 2 ) := max{α a (w 1 , w 2 ), 0}, if a ∈ A cm , max{-α a (w 1 , w 2 ), 0}, if a ∈ A cv .
Before we give a closed-form expression of the lower-level optimal value function ϕ, we discuss an alternative way of representing α a (w 1 , w 2 ) and β a (w 1 , w 2 ). Recall that the set of active elements A act is partitioned into the set of compressors A cm and the set of control valves A cv . The directional sets A k,→ act and A k,← act can be partitioned similarly. For all a ∈ A act , we then obtain

α a (w 1 , w 2 ) =      -1, if a ∈ P (G j1 , G j2 ) ∩ A j1,← act , 1, if a ∈ P (G j1 , G j2 ) ∩ A j1,→ act , 0, otherwise.
Consequently, it also holds

β a (w 1 , w 2 ) = 1, if a ∈ P (G j1 , G j2 ) ∩ A j1,→ cm ∪ A j1,← cv , 0, otherwise.
Using this representation of β a (w 1 , w 2 ), we obtain the closed form of the lower-level optimal value function stated in the following result. Corollary 6.3. The optimal value function ϕ of (7) is given by

max (Gj 1 ,Gj 2 )∈G 2 , w1∈V (Gj 1 ), w2∈V (Gj 2 )          π w1 -π w2 -      π + w1 -π - w2 + a∈P (Gj 1 ,Gj 2 ): a∈A j 1 ,→ cm ∪A j 1 ,← cv ∆ + a s a               . ( 14
)
Similar to the results obtained in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF] for passive networks, we can now establish a characterization of feasible bookings for networks with linearly modeled active elements. Theorem 6.4. Let G = (V, A) be a weakly connected network satisfying Assumption 1. Then, the booking b ∈ L is feasible if and only if φ w1w2 (b) ≤ π + w1 -π - w2 is satisfied for every pair of nodes (w 1 , w 2 ) ∈ V 2 with w 1 ∈ V (G j1 ) and w 2 ∈ V (G j2 ), where we define

φ w1w2 (b) := max ,q,π,s          π w1 -π w2 - a∈P (Gj 1 ,Gj 2 ): a∈A j 1 ,→ cm ∪A j 1 ,← cv ∆ + a s a : (UL)          .
Proof. As a consequence of Proposition 4.1 and Theorem 4.3, the booking b is feasible if and only if the solutions of ( 12) satisfy ϕ( , q, π, s) ≤ 0. By Corollary 6.3, the latter holds if and only if

π w1 -π w2 - a∈P (Gj 1 ,Gj 2 ): a∈A j 1 ,→ cm ∪A j 1 ,← cv ∆ + a s a ≤ π + w1 -π - w2
for every pair of nodes (w

1 , w 2 ) ∈ V 2 . Observe that φ w1w2 (b) -(π + w1 -π - w2
) is a lower bound for the solutions of ( 12). Thus, if the booking is feasible, φ w1w2 (b) ≤ π + w1 -π - w2 holds for every pair of nodes (w 1 , w 2 ) ∈ V 2 . On the contrary, if the booking is infeasible, there exists a feasible point ( , q, π, s) of (UL) and a pair of nodes (w 1 , w 2 ) ∈ V 2 such that ϕ( , q, π, s) > 0 holds, i.e., π w1 -π w2 -

a∈P (Gj 1 ,Gj 2 ): a∈A j 1 ,→ cm ∪A j 1 ,← cv ∆ + a s a > π + w1 -π - w2 .
In particular, we also have φ w1w2 (b) > π + w1 -π - w2 . The optimal-value-function reformulation [START_REF] Fügenschuh | The Reservation-Allocation Network Flow Problem[END_REF], where ϕ is given by ( 14), requires optimizing a piecewise-linear function with |V | 2 pieces over a nonlinear and nonconvex feasible domain. Using the characterization given in Theorem 6.4, all |V | 2 linear pieces can be optimized in individual subproblems. 6.2. Reduced Optimal Value Function. Since the lower level mainly controls active elements that link passive subnetworks, it is possible to give a coarser interpretation of the lower-level optimal value function. The main intuition now is to consider the lower level as a problem on the reduced network G. By grouping all nodes of a passive subnetwork, we can rewrite the lower-level optimal value function,

G0 G1 G2 G3 G4
Figure 3. Illustration of [START_REF] Hayn | Computing maximal entry and exit capacities of transportation networks[END_REF].

yielding

max (Gj 1 ,Gj 2 )∈G 2          max w1∈V (Gj 1 ) π w1 -π + w1 + max w2∈V (Gj 2 ) π - w2 -π w2 - a∈P (Gj 1 ,Gj 2 ): a∈A j 1 ,→ cm ∪A j 1 ,← cv ∆ + a s a          . ( 15
)
Then, applying the same arguments as in the proof of Theorem 6.4, we deduce a characterization with fewer subproblems to be solved.

Corollary 6.5. Let G = (V, A) be a weakly connected network satisfying Assumption 1. Then, the booking b ∈ L is feasible if and only if φ j1j2 (b) ≤ 0 is satisfied for every pair of passive subnetworks

(G j1 , G j2 ) ∈ G 2 , where φ j1j2 (b) is defined by max ,q,π,s          max w1∈V (Gj 1 ) π w1 -π + w1 + max w2∈V (Gj 2 ) π - w2 -π w2 - a∈P (Gj 1 ,Gj 2 ): a∈A j 1 ,→ cm ∪A j 1 ,← cv ∆ + a s a : (UL)         
.

We introduce variables θ + j and θ - j for every G j ∈ G that satisfy θ + j = max u∈V (Gj )

π u -π + u , (16a)
θ - j = max u∈V (Gj ) π - u -π u . (16b)
The optimal value function [START_REF] Hansen | New branch-and-bound rules for linear bilevel programming[END_REF] then is a piecewise-linear function with (|A act | + 1) 2 pieces. For G j ∈ G, θ + j and θ - j are also piecewise-linear functions with each |V (G j )| pieces. The characterization in Corollary 6.5 requires optimizing (|A act | + 1) 2 pieces of (15) separately, under the additional Constraint (16a) for G j1 ∈ G and Constraint (16b) for G j2 ∈ G.

Separable Optimal Value Function.

Still considering the lower level as a problem defined on the reduced network G, we derive a third closed-form expression of the lower-level optimal value function ϕ. Note that for any three subnetworks

G j1 , G k , G j2 ∈ G, it holds that P (G j1 , G j2 ) ∩ A j1,→ cm ∪ A j1,← cv ⊆ (P (G k , G j1 ) ∩ (A k,← cm ∪ A k,→ cv )) ∪ (P (G k , G j2 ) ∩ (A k,→ cm ∪ A k,← cv )), (17)
where equality holds if G k lies on the path P (G j1 , G j2 ). Figure 3 illustrates this relation for

G j1 = G 3 , G k = G 0 , G j2 = G 2 .
Here, the arc (G 0 , G 1 ) appears in the right-hand side of (17), while clearly not lying on P (G 3 , G 2 ).

The previous observation allows us to prove the following result.

Lemma 6.6. For every G k ∈ G, it holds ϕ ≥ ϕ k , where we define ϕ k ( , q, π, s) := max

Gj 1 ∈G, w1∈V (Gj 1 )          π w1 -π + w1 - a∈P (G k ,Gj 1 ): a∈A k,← cm ∪A k,→ cv ∆ + a s a          + max Gj 2 ∈G, w2∈V (Gj 2 )          π - w2 -π w2 - a∈P (G k ,Gj 2 ): a∈A k,→ cm ∪A k,← cv ∆ + a s a          (18)
for every feasible point ( , q, π, s) of (UL).

Proof. Given that ∆ + a s a ≥ 0 for all a ∈ A act , ( 17) implies that ϕ( , q, π, s) is bounded from below by

max (Gj 1 ,Gj 2 )∈G 2 , w1∈V (Gj 1 ), w2∈V (Gj 2 )          π w1 -π + w1 - a∈P (G k ,Gj 1 ): a∈A k,← cm ∪A k,→ cv ∆ + a s a + π - w2 -π w2 - a∈P (G k ,Gj 2 ): a∈A k,→ cm ∪A k,← cv ∆ + a s a         
.

For given G k , the elements of the latter max-operator are separable w.r.t. (G j1 , w 1 ) and (G j2 , w 2 ). Consequently, the joint max-operator can be split, which concludes the proof.

Based on this result, we can derive the third closed form of the lower-level optimal value function ϕ by considering all G k ∈ G and ϕ k . Theorem 6.7. The optimal value function ϕ of (7) is given by max

G k ∈G ϕ k , ( 19
)
where ϕ k is defined in [START_REF] Hennig | Using Bilevel Optimization to Find Severe Transport Situations in Gas Transmission Networks[END_REF].

Proof. By Lemma 6.6, ϕ ≥ max G k ∈G ϕ k holds. Let ( , q, π, s) be feasible for (UL). Furthermore, let (G j1 , G j2 , w 1 , w 2 ) be the maximizer defining ϕ( , q, π, s). For G k on the path P (G j1 , G j2 ), equality holds in [START_REF] Hayn | Computing maximal entry and exit capacities of transportation networks[END_REF]. Thus,

max G k ∈G ϕ k ( , q, π, s) = ϕ( , q, π, s).
Again, we can solve several subproblems independently and obtain the third characterization.

Corollary 6.8. Let G = (V, A) be a weakly connected network satisfying Assumption 1. Then, the booking b ∈ L is feasible if and only if

φ k (b) ≤ 0 is satisfied for a passive subnetwork G k ∈ G, where φ k (b) = max ,q,π,s ϕ k ( , q, π, s) : (UL) .
We introduce variables ϑ + k and ϑ - k for every G k ∈ G that satisfy

ϑ + k = max Gj ∈G, u∈V (Gj )          π u -π + u - a∈P (G k ,Gj ): a∈A k,← cm ∪A k,→ cv ∆ + a s a          , (20a)
ϑ - k = max Gj ∈G, u∈V (Gj )
         π - u -π u - a∈P (G k ,Gj ): a∈A k,→ cm ∪A k,← cv ∆ + a s a          . ( 20b
)
The optimal value function ϕ as defined in Theorem 6.7 then is a piecewise-linear function with

|A act | + 1 pieces. For G k ∈ G, ϑ +
k and ϑ - k are also piecewise linear with |V | pieces each. The characterization of Corollary 6.8 considers |A act | + 1 linear objectives. For each subproblem for G k ∈ G, only the additional constraints [START_REF] Kleinert | A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization[END_REF] corresponding to G k are required.

As a closing remark, we discuss how the formulations and characterizations presented in this section can be implemented using standard linearization techniques for the max-operators. Remark 6.9 (Linerization of max-operators). We have seen that the lower-level optimal value function is a piecewise-linear function that is convex and that needs to be maximized over a nonconvex domain. To model the max-operators involved in the different models of ϕ, we make use of the following classical technique. For a finite index set I, we want to model max i∈I {f i }. To this end, we introduce binary variables u i for all i ∈ I and let L, U ∈ R be chosen such that L ≤ f i ≤ U holds for every i ∈ I. Then, g = max i∈I {f i } holds if and only if

f i ≤ g ≤ f i + (U -L)(1 -u i ), i ∈ I, (21a)
i∈I u i = 1, u i ∈ {0, 1}, i ∈ I. (21b)
This reformulation can be applied to all three variants (14), [START_REF] Hansen | New branch-and-bound rules for linear bilevel programming[END_REF], and (19) of the lower-level optimal value function. The appropriate big-M values L, U ∈ R can be easily derived from the results of Section 5.2. By doing so, the three representations of the lower-level optimal value function ϕ (and the characterizations derived from them) can be modeled as MINLPs.

Computational Experiments

In this section, we evaluate the performance of the different approaches developed in this paper. In Section 7.3, the presented nonlinear potential-based flow model is studied. In order to better evaluate the performance of our methods and to eliminate challenging nonlinearities, we additionally study a simplified linear potential-based flow model in Section 7.4. We compare the KKT reformulation with the three optimal-value-function reformulations and the three characterizations derived in Section 6. The columns Method and Definition of Table 1 give a short overview regarding the considered methods including their abbreviations used throughout this section. 7.1. Data. Our case study is based on two instances of the GasLib [START_REF] Schmidt | GasLib -A Library of Gas Network Instances[END_REF] and different corresponding bookings. On the one hand, we study GasLib-134 (version 2), which is a tree-shaped network with 134 nodes, one compressor, and one control valve. It roughly represents the Greek gas network. The flow thresholds m are set to 0 for the compressor and to -10 -2 for the control valve. The latter value is chosen to guarantee the feasibility of the zero nomination in GasLib-134. Since the zero nomination is always booking-compliant, its feasibility is a necessary condition for the feasibility of any booking. Bookings for networks in the GasLib can be obtained by setting the corresponding nominations contained in the GasLib as bookings. For GasLib-134, these nominations reflect actual demand scenarios over several years in the past. We selected three random nominations over the year to consider different demands. In particular, we study bookings derived from the nominations 2011-11-06, 2012-07-22, and 2014-10-24.

On the other hand, we consider the GasLib-40 network for which we have replaced one compressor by a pipe to satisfy Assumption 1. This results in a network with six fundamental cycles, 40 nodes, and five compressors. All flow thresholds m are set to 0. As before, we derive one booking, denoted by 0-0, from the single GasLib nomination. This booking then serves as a base for the generation of additional bookings. To do so, we slightly vary the booking at entries and exits as follows. For parameters µ 1 , µ 2 ∈ (0, 100) and node u ∈ V , we obtain a new booking b, denoted µ 1 -µ 2 , by uniformly sampling a random integer in

bu ∈      100-µ1 100 b u , 100+µ1 100 b u , if u ∈ V + , 100-µ2 100 b u , 100+µ2 100 b u , if u ∈ V -, {0}, if u ∈ V 0 ,
where b is the initial booking 0-0. For GasLib-40, we generate three additional bookings for (µ 1 , µ 2 ) ∈ {(10, 10), [START_REF] Aßmann | Exact Methods for Two-Stage Robust Optimization with Applications in Gas Networks[END_REF][START_REF] Kleinert | A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization[END_REF], (10, 5)}. Note that in this way, we obtain bookings that are not balanced, which is in contrast to the bookings derived from GasLib nominations.

7.2. Computational Setup. All models have been implemented in Python 3.8.0 using Pyomo 5.7.1 [START_REF] Hart | Pyomo -Optimization Modeling in Python[END_REF]. We performed all computations using the Kaby Lake nodes with 32 GB RAM of the compute cluster [START_REF]Woodcrest Cluster[END_REF]. The time limit is 2 h. In Section 7.3, when treating nonlinear gas physics, we use ANTIGONE 1.1 [START_REF] Misener | ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations[END_REF] and BARON 17.4 [37] within GAMS 24.8 [START_REF]General Algebraic Modeling System[END_REF] to solve the occurring MINLPs. We perform the computations on a single thread and set the optCr parameter in GAMS to 10 -4 . In Section 7.4, we use Gurobi 9.0.1 [START_REF]Gurobi Optimizer Reference Manual[END_REF] to solve linear approximations of the gas physics. We again perform computations on a single thread and set Gurobi parameters IntFeasTol to 10 -9 and NumericFocus to 3.

We now discuss some statistics of our models, which are summarized in Table 1. To solve the single-level reformulations, a single optimization problem needs to be solved, whereas characterizations require solutions of multiple subproblems. The columns Subproblems present the number of optimization problems to be solved for each method w.r.t. the GasLib-134 and GasLib-40 networks. As we can see in Table 1, the number of subproblems drastically differs for the considered characterizations. This is due to the fact that F-CHAR consists of |V | 2 many subproblems, whereas the other two characterizations R-CHAR and S-CHAR consist of (|A act | + 1) 2 and (|A act | + 1) subproblems. A reduced number of subproblems comes, however, at the cost of additional binary variables. All models are implemented in their linearized form, i.e., KKT's complementarity constraints have been linearized as discussed in Section 5.2 and for all other models, the linearization (21) of the max-operators is used. The Binaries columns indicate the maximum number of additional binary variables (other than the |A act | binary variables s) required for the linearization of a subproblem. Among all optimal-value-function reformulations, i.e., F-OVF, R-OVF, and S-OVF, we can observe that R-OVF contains the smallest number of binary variables, which is comparable to the number of binary variables for KKT. Regarding the characterizations, there is a clear trade-off between the number of subproblems and the number of binary variables, for which we later see that the large number of subproblems in F-CHAR is a computational disadvantage.

We finally note that all subproblems of the characterizations are solved iteratively without warm-starts. Thus, we do not exploit that all characterizations can be fully parallelized since all subproblems can be solved independently. The actual parallelization of the approaches based on the characterizations is out of the scope of this paper. However, to take this aspect into account during the discussion of our results, we discuss, besides the total sequential time, also an idealized parallel time, i.e., the maximum time required to solve a single subproblem. 1. Vio. represents the obtained violation, i.e., for single-level reformulations the optimal value of the problem and for the characterizations the maximum violation of any bound on the optimal solutions of the corresponding subproblems. Thus, this column denotes the measure of feasibility of a booking. Positive values indicate violated potential bounds and thus the infeasibility of a booking. On the other hand, nonpositive values indicate that all booking-compliant nominations can be transported within the potential bounds, which implies the feasibility of a booking. Sol. gives the running time in seconds for single-level reformulations. Min., Med., and Max. denote the minimum, median, and maximum running times (in seconds) necessary for solving a single characterization subproblem and checking whether the corresponding bound on the optimal solution is satisfied. Finally, Total reports the total time, which for characterizations is equal to the time spent in the sequential treatment of all subproblems. If an instance could not be solved within the time limit of 2 h, then we represent it by "-" in the corresponding row of the table.

Unfortunately, the solvers do not give consistent results although all violations are negative, i.e., the booking seems to be feasible. The runs using BARON for R-OVF and S-OVF deviate from the common answer of all other combinations of methods and solvers. In particular, the optimal solution has been cut off from the search space at some point during the spatial branching. Consequently, we have to interpret the obtained results by BARON with great caution. On the other hand, we can analyze the trend presented by ANTIGONE. F-OVF and F-CHAR need the most time, which is expected since they have the most binary variables and subproblems, respectively. Although, the idealized parallel time of F-CHAR, i.e., 3.17 s, is faster than the total time of KKT, it should not be forgotten that for GasLib-134, we need to solve 17 956 subproblems. Here, the only method slightly outperforming KKT is R-OVF. The latter has approximately the same number of additional binary variables as KKT, while S-OVF requires more binary variables. Concerning the corresponding methods using the characterizations, we observe that R-CHAR and S-CHAR are outperformed both w.r.t. the total sequential time and the idealized parallel time. Although, they require fewer subproblems to be solved than F-OVF, they admit additional binary variables to be branched on. For some subproblems, the solvers struggle to prove optimality. While the median time is good, there exist some outlier problems that require a long time to close the duality gap. Similar trends can be observed on GasLib-134 for the 2012-07-22 and 2014-10-24 bookings, which we include in Appendix A.

For GasLib-40, we are not able to generate meaningful results within the time limit of 2 h. We generally have to conclude that the problem at hand is numerically very unstable and hard to handle for the used nonlinear solvers. Some models could still be solved relatively fast, in particular the KKT model. However, the solvers often incorrectly certify optimality or get stuck in suboptimal solutions, not being able to close the duality gap. The spatial branching on the nonlinear gas physics in addition to the branching on linearized piecewise-linear functions leads to very challenging problems, which would require further tuning of the MINLP solvers. This is, however, out of the scope of this case study. To compare our methods, we have thus resorted to analyzing linear approximations of gas physics as presented in the next section. 7.4. The Linear Case. Except for the nonlinear gas physics at the right-hand side of (1b), all considered models are linear with mixed-integer variables. In this section, we consider linear approximations of gas physics to obtain mixedinteger linear problems (MILP) to be solved by Gurobi. To this end, we replace |q a | for every a ∈ A pipe by cM , where c ∈ (0, 1] is a scaling factor and M := min{ u∈V+ b u , u∈V-b u } is an upper bound on the flow on each arc. Thus, we replace Constraints (1b) with

π u -π v = ξ a q a , ξ a = cΛ a M, a = (u, v) ∈ A pipe .
Table 3 shows the results for GasLib-134 and the 2011-11-06 booking, where Appr. indicates the different scaling factors c ∈ {0.2, 0.4, 0.6, 0.8, 1.0}. Since both F-OVF and F-CHAR are clearly outperformed by the other methods, we choose to omit them in the tables. First, we observe that all methods present consistent results in the linear case. Additionally, for increasing scaling factors c, the resulting violations also increase. This trend is easily explained by the fact that a large scaling factor leads to a larger potential drop along all pipes, which again results in larger overall potential differences. In particular, the booking is feasible for c ∈ {0.2, 0.4} and becomes infeasible for larger scaling factors. We observe that for all scaling factors, KKT is performing well. Although slightly faster, R-OVF does not significantly outperform KKT. Similarly, S-OVF admits running times comparable to KKT, but is the slowest among the presented methods, which can be explained by its large number of binary variables necessary for the complete linearization of the optimal value function [START_REF] Jeroslow | The polynomial hierarchy and a simple model for competitive analysis[END_REF]. Concerning the methods using the characterizations, the sequential time necessary to solve R-CHAR and S-CHAR is of the same order of magnitude as KKT. When considering the idealized parallel time, R-CHAR and S-CHAR are the clear winners.

To obtain these idealized parallel times, 9 and 3 subproblems need to be solved in parallel, respectively. In that regard, R-CHAR is the fastest method for four scaling factors and only takes a little longer for c = 0.4, where S-CHAR is slightly faster. Again, similar trends can be observed for the remaining bookings of GasLib-134. We therefore do not explicitly discuss the corresponding results, but list them in Appendix B. Table 4 shows the results for GasLib-40 and booking 0-0. In contrast to GasLib-134, F-OVF and F-CHAR are more competitive for GasLib-40, which has fewer nodes 1. However, the cyclic structure of GasLib-40 makes the problem of checking the feasibility of a booking more challenging. In our experiments, S-OVF is not able to find a provably optimal solution and has thus been omitted from this table. For c ∈ {0.4, 0.6, 0.8, 1.0}, the optimal solution was found by S-OVF, however the duality gap could not be closed during the time limit. Overall, we observe more variability in running times across different scaling factors c for all methods. In terms of total time, i.e., the sequential time for characterizations, KKT is the fastest method. In terms of idealized parallel time, i.e., the maximum time necessary to solve a single subproblem, all three characterizations outperform KKT. Note that we still have to solve 1600 subproblems for F-CHAR, although all individual computations can be done in at most 0.5 s for c ∈ {0.2, 0.4, 0.6, 1.0} and in roughly 1 s for c = 0.8. If computations can be fully parallelized, i.e., a sufficient number of cores are available to solve all subproblems in parallel, R-CHAR is the most adequate method for GasLib-40 to obtain a beneficial trade-off between the small number of subproblems to be solved and the number of additional binary variable in each subproblem. On the other hand, S-CHAR requires more time for each subproblem, at the benefit of very few subproblems to be solved and can thus still outperform KKT if fewer parallel computing resources are available.

To eliminate the possibility that the interpretation of the previous results are purely linked to the balancedness of bookings generated from nominations of the GasLib, we have additionally studied the three perturbed bookings 10-10, 1-20, and 10-5. Qualitatively, the results follow the discussion of the booking 0-0. The corresponding tables are thus listed in Appendix C.

As a final discussion, note that all of the methods studied in this paper also allow for preemptive decisions without the need to solve the models to optimality. For each single-level reformulation, whenever a relaxation produces a nonpositive value, we can stop the computation and certify that the booking is feasible. Similarly, whenever a feasible point of positive violation is found, the booking is infeasible with the certificate given by the corresponding nomination. For showing the infeasibility of a booking, the same logic can be extended to characterizations. As soon as a feasible point of one subproblem with positive violation has been found, we can stop and certify that the booking is infeasible. This can be useful especially in practice, since TSOs generally have additional knowledge regarding their networks and are aware of their bottlenecks. With this knowledge at hand, it could be possible to check specific individual subproblems to identify infeasible nominations that lead to a rejection of the considered booking request. In case of a feasible booking, all subproblems must be solved. They can however be terminated early, based on a nonpositive value of a relaxation.

Conclusion

The problem of deciding the feasibility of a booking in the European entry-exit gas market has been studied mostly for passive networks up to now. In this paper, we considered networks with linearly modeled active elements that do not lie on cycles of the network. By doing so, we present a first stepping stone towards the study of more general networks and more general models of active elements. The approaches for verifying the feasibility of a booking in passive networks are not directly applicable to the case of networks with active elements, as discussed in Section 3. Thus, we have then presented a bilevel optimization model, in which the upper-level player chooses a nomination that is most difficult to transport and the TSO at the lower level uses the active elements to transport this nomination. Consequently, the bilevel structure results from the fact that the TSO takes a decision individually for every nomination by controlling the active elements appropriately. We studied both the classical KKT reformulation and problem-specific optimal-value-function reformulations. More precisely, we have given three optimal-value-function reformulations giving rise to three equivalent characterizations of feasible bookings, which generalize the characterization in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF] for passive networks. Our case studies show that the KKT approach is already a very well performing method to check the feasibility of a booking. It also shows that the more problem-specific approaches of Section 6 can sometimes outperform KKT approach, especially when parallel computing resources are available. It should, however, be noted that the applicability of these methods depends on the structure of the network at hand. In particular, the number of binary variables for the linearizations and the number of subproblems to be solved in the characterizations vary significantly. They are determined by the number of active elements and nodes. Thus, the best-performing method among the various optimal-value-function reformulations and characterizations strongly depends on the considered network.

For future work, it will be interesting to study networks without specific assumptions on the location of the active elements, as well as more general models for the active elements. However, even in the setting of this paper, some challenges still need to be tackled. It is required to develop problem-specific solution approaches, especially for the case of nonlinear gas physics. Similar to the studies in [START_REF] Labbé | Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results[END_REF][START_REF] Robinius | Robust optimal discrete arc sizing for tree-shaped potential networks[END_REF] for tree-shaped and in [START_REF] Labbé | Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks[END_REF] for single-cycle networks, algorithms to solve the nonlinear subproblems of the characterizations presented in this paper can be beneficial. Finally, the analyses of the European gas market models studied in [START_REF] Böttger | The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market[END_REF][START_REF] Schewe | Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees[END_REF] can be extended to take into account linearly modeled active elements by integrating the novel characterizations of feasible bookings presented in this paper.

Definition 2 . 3 .

 23 A booking is a load flow b ∈ L. A nomination is called bookingcompliant w.r.t. the booking b if ≤ b holds, where "≤" is meant componentwise throughout this paper. The set of booking-compliant nominations is given by N (b) := { ∈ N : ≤ b}.

Definition 2 . 5 .

 25 A booking b ∈ L is feasible if all booking-compliant nominations ∈ N (b) are feasible, i.e., a booking b is feasible if

Figure 1 .

 1 Figure 1. Network of the counterexample consisting of three nodes, one compressor, and one pipe, together with relevant node and arc parameters.

Figure 2 .

 2 Figure 2. Stylized gas network satisfying Assumption 1 (left) and its reduced network (right).

7. 3 .

 3 The Nonlinear Case.

  can be reformulated as the MINLP , q, π, s, ∆, τ, y, z, α, β, δ + , δ -) is the vector of upper-level, lower-level primal, and lower-level dual variables. Here, Constraint (UL) groups all upper-level constraints. Constraint (LLP) and Constraint (LLD) group lower-level primal and dual constraints, respectively. 5.2. Big-M Linearization. A standard way of reformulating the KKT complementarity conditions (

	max ξ	y + z	(10)
	s.t. (6b)-(6f),	(UL)
		(7b)-(7e),	(LLP)
		(8b)-(8f),	(LLD)
		(9),
	where ξ = (

Table 1 .

 1 Overview of methods and model statistics.

			GasLib-134	GasLib-40
	Method	Definition	Subproblems Binaries Subproblems Binaries
	KKT	(10)	1	272	1	90
	F-OVF (12) using (14)	1	17956	1	1600
	R-OVF (12) using (15)	1	277	1	116
	S-OVF (12) using (19)	1	807	1	486
	F-CHAR	Theorem 6.4	17956	0	1600	0
	R-CHAR Corollary 6.5	9	162	36	44
	S-CHAR Corollary 6.8	3	268	6	80

  Table 2 lists the results for the GasLib-134 network and the 2011-11-06 booking. Method indicates the method from Table

Table 2 .

 2 Results for GasLib-134 and the 2011-11-06 booking.

	Time

Table 3 .

 3 Results for GasLib-134 and the 2011-11-06 booking.

	Time

Table 4 .

 4 Results for GasLib-40 and the 0-0 booking.

	Time

Table 8 .

 8 Results for GasLib-134 and the 2014-10-24 booking.

	Time

Table 10 .

 10 Results for GasLib-40 and the 1-20 booking.

	Time

Table 11 .

 11 Results for GasLib-40 and the 10-5 booking.

	Time

Acknowledgments

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. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. Martin Schmidt and Johannes Thürauf thank the Deutsche Forschungsgemeinschaft for their support within projects A05, B07, and B08 in CRC TRR 154.

Advances and Next Challenges. Ed. by S. Dempe