Embed Size (px)
Citation preview
– Forschungskooperation Netzoptimierung
Optimization of Gas Networks
Martin Grötschel
2012-06-05
The PartnersZuse-Institut BerlinDiskrete Methoden / OptimierungDr. Thorsten Koch (Projektkoordinator)
Friedrich-Alexander Universität Erlangen-NürnbergEconomics · Discrete Optimization · MathematicsProf. Dr. Alexander Martin
Leibniz-Universität HannoverInstitut für Angewandte MathematikProf. Dr. Marc Steinbach
Universität Duisburg-EssenFachbereich MathematikProf. Dr. Rüdiger Schultz
Technische Universität BraunschweigInstitut für Mathematische OptimierungProf. Dr. Marc Pfetsch
Humboldt-Universität zu BerlinInstitut für MathematikProf. Dr. Werner Römisch
Weierstraß-Institut für Angewandte Analysis und Stochastik (WIAS)Dr. Rene Henrion
Open Grid EuropeNetzplanung und -steuerung / NetzoptimierungDr. Klaus Spreckelsen (Projektleiter)
BMWiProjektträger Jülich, Geschäftsbereich EnergietechnologienChristoph Jessen (Projektbetreuer)
Martin Grötschel Optimization of Gas Networks 2 / 31
The Team
T. Berthold, J. Bödecker, M. Ebbers, A. Emgrunt, A. Fügenschuh, G. Gamrath, B. Geißler, N. Geißler, R. Gollmer, U. Gotzes,
M. Grötschel, C. Hayn, S. Heinz, R. Henrion, B. Hiller, L. Huke, J. Humpola, J. Hülsewig, I. Joormann, W. Knieschweski,
T. Koch, V. Kühl, H. Leövey, F. Malow, D. Mahlke, A. Martin, R. Mirkov, A. Morsi, G. Möhlen, A. Möller, F. Nowosatko,
D. Oucherif, M. Pfetsch, W. Römisch, L. Sax, L. Schewe, M. Schmidt, R. Schultz, R. Schwarz, J. Schweiger, K. Spreckelsen,
C. Stangl, M. Steckhan, M. Steinbach, A. Steinkamp, J. Szabó, H. Temming, I. Wagner-Specht, B. Willert, S. Vigerske, A. Zelmer
Martin Grötschel Optimization of Gas Networks 3 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
The Entry/Exit Model
. the entry/exit model was introduced as ameans to liberalize the gas market(directive 2003/55/EC, GasNZV)
. in the entry/exit model network users booktransmission capacity at entries and exitsseparately
. transmission cost may depend on entry/exit,but not on transportation path
. customers later nominate the actual inflowand outflow within their booked capacities⇒ nomination of all customers
. transmission system operator has to ensurethat each nomination within the bookedcapacities can technically be realized
• •
••
•
entries
exits
booked capacities
10 5
520
10
nomination 1
5 5
00
10
nomination 2
8 3
52
4
Martin Grötschel Optimization of Gas Networks 4 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find
1. settings for the active devices(valves, control valves, compressors)
2. values for the physical parameters of thenetwork
that comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find
1. settings for the active devices(valves, control valves, compressors)
2. values for the physical parameters of thenetwork
that comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find1. settings for the active devices
(valves, control valves, compressors)
2. values for the physical parameters of thenetwork
that comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find1. settings for the active devices
(valves, control valves, compressors)2. values for the physical parameters of the
network
that comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find1. settings for the active devices
(valves, control valves, compressors)2. values for the physical parameters of the
networkthat comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find1. settings for the active devices
(valves, control valves, compressors)2. values for the physical parameters of the
networkthat comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find1. settings for the active devices
(valves, control valves, compressors)2. values for the physical parameters of the
networkthat comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Essential Subtask: Validating Nominations
Given: . a detailed description of a gas network. a nomination specifying amounts of gas flow
at entries and exits
Task: Find1. settings for the active devices
(valves, control valves, compressors)2. values for the physical parameters of the
networkthat comply with. gas physics. legal and technical limitations
human experience
simulation tool
Issue: How to decide whether a nomination is technically feasible?
Martin Grötschel Optimization of Gas Networks 5 / 31
Using Optimization Rather Than SimulationSimulation. allows very accurate gas physics
models. relies on human experience to
decide feasibility. is thus inappropriate to determine
infeasibility of a nomination
Optimization. works on simplified models of gas
physics. automatically finds settings for
active devices. eventually proves infeasibility of an
infeasible nomination
Beware: different solution spaces due to different modeling
simulation A
simulation B
optimization A
optimization B
Martin Grötschel Optimization of Gas Networks 6 / 31
Using Optimization Rather Than SimulationSimulation. allows very accurate gas physics
models. relies on human experience to
decide feasibility. is thus inappropriate to determine
infeasibility of a nomination
Optimization. works on simplified models of gas
physics. automatically finds settings for
active devices. eventually proves infeasibility of an
infeasible nomination
Beware: different solution spaces due to different modeling
simulation A
simulation B
optimization A
optimization B
Martin Grötschel Optimization of Gas Networks 6 / 31
Using Optimization Rather Than SimulationSimulation. allows very accurate gas physics
models. relies on human experience to
decide feasibility. is thus inappropriate to determine
infeasibility of a nomination
Optimization. works on simplified models of gas
physics. automatically finds settings for
active devices. eventually proves infeasibility of an
infeasible nomination
Beware: different solution spaces due to different modeling
simulation A
simulation B
optimization A
optimization B
Martin Grötschel Optimization of Gas Networks 6 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against
. a worst case start state?
definitely far too pessimistic
. all likely start states?
infinitely many
. a suitable start state?
might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against
. a worst case start state?
definitely far too pessimistic
. all likely start states?
infinitely many
. a suitable start state?
might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against
. a worst case start state?
definitely far too pessimistic
. all likely start states?
infinitely many
. a suitable start state?
might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against. a worst case start state?
definitely far too pessimistic
. all likely start states?
infinitely many
. a suitable start state?
might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against. a worst case start state? definitely far too pessimistic. all likely start states?
infinitely many
. a suitable start state?
might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against. a worst case start state? definitely far too pessimistic. all likely start states? infinitely many. a suitable start state?
might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Transient Models
Transient models describe the network state evolution over time.
. similar to reality
but. can only be computed over a finite time horizon. require a forecast of the in- and outflow over time. require a start state, which is not known for planning. deviations between predicted / physical network state grow over time
Deciding feasibility of a future nomination requires to test it against. a worst case start state? definitely far too pessimistic. all likely start states? infinitely many. a suitable start state? might be overly optimistic
Martin Grötschel Optimization of Gas Networks 7 / 31
Stationary Models
Stationary models describe a (timeless) equilibrium network state.
. stable situation (by definition) modeling an “average network state”
. no start state needed, no time horizon
. ensures that the situation is sustainable
. much less data requirements, simpler physics
But. using pipes as gas storage (linepack) cannot be modelled. transition between nominations cannot be modelled. too pessimistic especially regarding short-term peak situations
Nevertheless, the better choice for medium and long-term planning.
Martin Grötschel Optimization of Gas Networks 8 / 31
Stationary Models
Stationary models describe a (timeless) equilibrium network state.
. stable situation (by definition) modeling an “average network state”
. no start state needed, no time horizon
. ensures that the situation is sustainable
. much less data requirements, simpler physics
But. using pipes as gas storage (linepack) cannot be modelled. transition between nominations cannot be modelled. too pessimistic especially regarding short-term peak situations
Nevertheless, the better choice for medium and long-term planning.
Martin Grötschel Optimization of Gas Networks 8 / 31
Stationary Models
Stationary models describe a (timeless) equilibrium network state.
. stable situation (by definition) modeling an “average network state”
. no start state needed, no time horizon
. ensures that the situation is sustainable
. much less data requirements, simpler physics
But. using pipes as gas storage (linepack) cannot be modelled. transition between nominations cannot be modelled. too pessimistic especially regarding short-term peak situations
Nevertheless, the better choice for medium and long-term planning.
Martin Grötschel Optimization of Gas Networks 8 / 31
Stationary Models
Stationary models describe a (timeless) equilibrium network state.
. stable situation (by definition) modeling an “average network state”
. no start state needed, no time horizon
. ensures that the situation is sustainable
. much less data requirements, simpler physics
But. using pipes as gas storage (linepack) cannot be modelled. transition between nominations cannot be modelled. too pessimistic especially regarding short-term peak situations
Nevertheless, the better choice for medium and long-term planning.
Martin Grötschel Optimization of Gas Networks 8 / 31
Gas Network: H-Nord
. 32 entries, 142 exits
. 498 pipes,9 resistors,33 valves,26 control valves,7 compressor stations
. 32 cycles
Martin Grötschel Optimization of Gas Networks 9 / 31
Network and Variables
Mathematical model description:Network: directed Graph G = (V ,E ) with vertices V and edges EVariables: . pressure at node i ∈ V : pi
. mass flow, volumetric flow rate on edge e ∈ E : qe , Qe
. decision for active element ea ∈ Ea ⊂ E : xea
. temperature at node i ∈ V : Ti
. velocity on edge e ∈ E : ve
. fuel, power for compressor eCS ∈ ECS ⊂ E : beCS , PeCS
. density at node i ∈ V : ρi
. real gas factor of gas at node i ∈ V : zi
. calorific value of gas at node i ∈ V : B̂i
. speed of compressor eCS ∈ ECS : neCS
. adiabatic head of compressor eCS ∈ ECS : Had ,eCS
. adiabatic efficiency of compressor eCS ∈ ECS : ηad ,eCS
Martin Grötschel Optimization of Gas Networks 10 / 31
Hierarchical Modeling
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
PDE WeymouthHPPCs
Weymouth
Accurate Approximate
QuadraticModel
PolyhedralModel
IdealCompressor
AccurateModel
ApproximateModel
AccurateModel
ApproximateModel
Martin Grötschel Optimization of Gas Networks 11 / 31
Euler Differential Equation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
PDE WeymouthHPPCs
Weymouth
Euler-differential equation&
equation of state for real gases:
∂ρ
∂t+∂ (ρv)
∂x= 0
∂ (ρv)
∂t+∂(ρv2)
∂x+∂p∂x
+ gρ∂h∂x
+ λ(q)|v |v2D
ρ = 0
Aρcp
(∂T∂t
+ v∂T∂x
)− A
(1 +
Tz∂z∂T
)∂p∂t
−AvTz∂z∂T
∂p∂x
+ Avgρdhdx
+ QE = 0
ρ− ρ0z0T0
p0· pz(p,T )T
= 0
Martin Grötschel Optimization of Gas Networks 12 / 31
Weymouth Equation of HPPCs Model
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
PDE WeymouthHPPCs
Weymouth
Weymouth-equation
based on HPPCs-model:
p2j =
(p2i − Λ · φ (q)
eS − 1S
)e−S
Λ =
(4π
)2 Lp0z (pm,Tm) Tm
D5ρ0z0T0
S = 2Lgdhdx
ρ0z0T0
p0z (pm,Tm) Tm
Martin Grötschel Optimization of Gas Networks 13 / 31
Weymouth Equation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
PDE WeymouthHPPCs
Weymouth
Simplified Weymouth-equation:
Friction coefficient according to Nikuradze
λ =
(2 log10
(Dk
)+ 1.138
)−2
yields
p2j =
(p2i − Λ|qe |qe
eS − 1S
)e−S
Martin Grötschel Optimization of Gas Networks 14 / 31
Flow-dependent Resistor
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
Accurate Approximate
Exact flow dependent resistor equation:
Pressure decrease:
pi − pj =8ρ0p0
π2z0T0
ξTi
D4|qe |qez(pi ,Ti )
pi
Temperature decrease due to Joule-Thomson effect:
Te,out = Te,in + µJT (pj − pi )
Martin Grötschel Optimization of Gas Networks 15 / 31
Resistor Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
Accurate Approximate
Approximation
of flow dependent resistors:
ε(p2i − p2
j)
=8ρ0p0
π2z0T0
ξTD4 |qe |qe
with
minε∈R
u∫l
pv∫l
(p2v − pv · pw
1 + ζe · pv− ε · (p2
v − p2w )
)2dpw dpv
+
u∫l
pw∫l
(−
p2w − pv · pw
1 + ζe · pw− ε · (p2
v − p2w )
)2dpv dpw
12
Martin Grötschel Optimization of Gas Networks 16 / 31
Valves and Control Valves
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
Valve: open or closed
One decision variable xe ∈ {0, 1}:
closed: xe = 0 =⇒ qe = 0open: xe = 1 =⇒ pi = pj
Control Valve: active, bypassed, or closed
Two decision variables xbypasse and xactive
e :
xbypasse + xactive
e ≤ 1
closed: xbypasse = xactive
e = 0 =⇒ qe = 0
bypass: xbypasse = 1 =⇒ pi = pj
active: xactivee = 1 =⇒ ∆ ≤ pi − pj ≤ ∆
Martin Grötschel Optimization of Gas Networks 17 / 31
Valves and Control Valves
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
Valve: open or closed
One decision variable xe ∈ {0, 1}:
closed: xe = 0 =⇒ qe = 0open: xe = 1 =⇒ pi = pj
Control Valve: active, bypassed, or closed
Two decision variables xbypasse and xactive
e :
xbypasse + xactive
e ≤ 1
closed: xbypasse = xactive
e = 0 =⇒ qe = 0
bypass: xbypasse = 1 =⇒ pi = pj
active: xactivee = 1 =⇒ ∆ ≤ pi − pj ≤ ∆
Martin Grötschel Optimization of Gas Networks 17 / 31
Valves and Control Valves
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
Valve: open or closed
One decision variable xe ∈ {0, 1}:
closed: xe = 0 =⇒ qe = 0open: xe = 1 =⇒ pi = pj
Control Valve: active, bypassed, or closed
Two decision variables xbypasse and xactive
e :
xbypasse + xactive
e ≤ 1
closed: xbypasse = xactive
e = 0 =⇒ qe = 0
bypass: xbypasse = 1 =⇒ pi = pj
active: xactivee = 1 =⇒ ∆ ≤ pi − pj ≤ ∆
Martin Grötschel Optimization of Gas Networks 17 / 31
Valves and Control Valves
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
Valve: open or closed
One decision variable xe ∈ {0, 1}:
closed: xe = 0 =⇒ qe = 0open: xe = 1 =⇒ pi = pj
Control Valve: active, bypassed, or closed
Two decision variables xbypasse and xactive
e :
xbypasse + xactive
e ≤ 1
closed: xbypasse = xactive
e = 0 =⇒ qe = 0
bypass: xbypasse = 1 =⇒ pi = pj
active: xactivee = 1 =⇒ ∆ ≤ pi − pj ≤ ∆
Martin Grötschel Optimization of Gas Networks 17 / 31
Quadratic Compressor Model
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
QuadraticModel
PolyhedralModel
IdealCompressor
Quadratic approximation
of turbo-compressor:
Had (Q, n) = a1 + a2n + a3n2 +(a4 + a5n + a6n2)Q
+(a7 + a8n + a9n2)Q2
η (Q, n) = b1 + b2n + b3n2 +(b4 + b5n + b6n2)Q
+(b7 + b8n + b9n2)Q2
Had ≤ s1 + s2Q + s3Q2
Had ≥ c1 + c2Q + c3Q2
P = HadQ/η
Martin Grötschel Optimization of Gas Networks 18 / 31
Polyhedral Compressor Model
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
QuadraticModel
PolyhedralModel
IdealCompressor
Polyhedral approximation based on:
Had =ziRsTiκ
κ− 1
((pj
pi
)κ−1κ
− 1
)
Q =p0z(pi ,T )T3.6z0T0
qpi
pi
pj
q
= pi
1
( κ−1ziRsTiκ
Had + 1)κκ−1
3.6z0T0p0z(pi ,T )T Q
Martin Grötschel Optimization of Gas Networks 19 / 31
Idealized Compressor
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
QuadraticModel
PolyhedralModel
IdealCompressor
Idealized compressor:
Pe =κ
κ− 1ρ0RTiz(pi ,Ti )
ηadm
((pj
pi
)κ−1κ
− 1
)qe
Martin Grötschel Optimization of Gas Networks 20 / 31
Compressor Station
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
Compressor Station:
. union of single compressor machines
. compressor station can operate in differentconfigurations
. configuration: selected compressormachines operateI parallellyI sequentiallyI parallelly and sequentially
Martin Grötschel Optimization of Gas Networks 21 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
1. The feasible operating range of a compressormachine is mainly described by the characteristicdiagram:
0 1 2 3 4 5 6 7 8 9 100
5
10
15
20
25
30
35
40
Q
Had
M1
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
1. The feasible operating range of a compressormachine is mainly described by the characteristicdiagram:
0 1 2 3 4 5 6 7 8 9 100
5
10
15
20
25
30
35
40
Q
Had
M1
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 8 9 100
5
10
15
20
25
30
35
40
Q
Had
M1
M3 M1 ‖ M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 8 9 100
5
10
15
20
25
30
35
40
Q
Had
M1M3
M1 ‖ M3
I parallel operation of machines M1 ‖ M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 8 9 100
5
10
15
20
25
30
35
40
Q
Had
M1M3 M1 ‖ M3
I parallel operation of machines M1 ‖ M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 8 9 100
5
10
15
20
25
30
35
40
Q
Had
M1M3 M1 ‖ M3
I parallel operation of machines M1 ‖ M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 80
10
20
30
40
50
60
70
Q
Had
M1M3
M1 � M3
I sequential operation of machines M1 � M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 80
10
20
30
40
50
60
70
Q
Had
M1M3
M1 � M3
I sequential operation of machines M1 � M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
2. Approximation of the feasible operating range ofa configuration by convex approximation incombination with Fourier-Motzkin-Elimination:
0 1 2 3 4 5 6 7 80
10
20
30
40
50
60
70
Q
Had
M1M3
M1 � M3
I sequential operation of machines M1 � M3
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
3. Convex hull of the union of all configurationsyields approximation of the feasible operatingrange of a compressor station
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160
10
20
30
40
50
60
70
Q
Had
parallelserial
1. Machines
2. Configurations3. Approximation of Compressor Station
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
3. Convex hull of the union of all configurationsyields approximation of the feasible operatingrange of a compressor station
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160
10
20
30
40
50
60
70
Q
Had
parallelserial
1. Machines2. Configurations
3. Approximation of Compressor Station
Martin Grötschel Optimization of Gas Networks 22 / 31
Compressor Station Approximation
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
AccurateModel
ApproximateModel
3. Convex hull of the union of all configurationsyields approximation of the feasible operatingrange of a compressor station
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160
10
20
30
40
50
60
70
Q
Had
parallelserial
1. Machines2. Configurations3. Approximation of Compressor Station
Martin Grötschel Optimization of Gas Networks 22 / 31
Subnetwork Operation Modes
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
April 20, 2011Zuse Institute BerlinDep. Optimization
Schematischer Stationsaufbau (neu)
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
4
800600120010
. each operation mode is described by abinary vector giving the state of each valve
. we use the convex hull of these binaryvectors to include the operation modes inour model
Martin Grötschel Optimization of Gas Networks 23 / 31
Subnetwork Operation Modes
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
April 20, 2011Zuse Institute BerlinDep. Optimization
Schematischer Stationsaufbau (neu)
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
4
800600120010
April 20, 2011Zuse Institute BerlinDep. Optimization
2a. Verdichten von Stolberg (M11 o. M12)
5
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
800600120010
. each operation mode is described by abinary vector giving the state of each valve
. we use the convex hull of these binaryvectors to include the operation modes inour model
Martin Grötschel Optimization of Gas Networks 23 / 31
Subnetwork Operation Modes
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
April 20, 2011Zuse Institute BerlinDep. Optimization
Schematischer Stationsaufbau (neu)
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
4
800600120010
April 20, 2011Zuse Institute BerlinDep. Optimization
2b. Verdichten von Stolberg (M5 o. M6)
6
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
800600120010
. each operation mode is described by abinary vector giving the state of each valve
. we use the convex hull of these binaryvectors to include the operation modes inour model
Martin Grötschel Optimization of Gas Networks 23 / 31
Subnetwork Operation Modes
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
April 20, 2011Zuse Institute BerlinDep. Optimization
Schematischer Stationsaufbau (neu)
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
4
800600120010
April 20, 2011Zuse Institute BerlinDep. Optimization
3a. Verdichten von Paffrath nach Stolberg und nach Scheidt, oder verdichtet aus Paffrath und unverdichtet aus Scheidt nach Stolberg
7
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
800600120010
. each operation mode is described by abinary vector giving the state of each valve
. we use the convex hull of these binaryvectors to include the operation modes inour model
Martin Grötschel Optimization of Gas Networks 23 / 31
Subnetwork Operation Modes
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
April 20, 2011Zuse Institute BerlinDep. Optimization
Schematischer Stationsaufbau (neu)
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
4
800600120010
April 20, 2011Zuse Institute BerlinDep. Optimization
3a. Verdichten von Paffrath nach Stolberg und nach Scheidt, oder verdichtet aus Paffrath und unverdichtet aus Scheidt nach Stolberg
7
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
800600120010
. each operation mode is described by abinary vector giving the state of each valve
. we use the convex hull of these binaryvectors to include the operation modes inour model
Martin Grötschel Optimization of Gas Networks 23 / 31
Subnetwork Operation Modes
Pipeline
Resistor
Valve
Control Valve
Compressor
Compressor Station
Operation Modes
April 20, 2011Zuse Institute BerlinDep. Optimization
Schematischer Stationsaufbau (neu)
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
4
800600120010
April 20, 2011Zuse Institute BerlinDep. Optimization
3a. Verdichten von Paffrath nach Stolberg und nach Scheidt, oder verdichtet aus Paffrath und unverdichtet aus Scheidt nach Stolberg
7
PORZ_VS-S(11p/s, 12p/s)
PORZ_VS-H(5, 6)
PORZ_VS-H1(5, 6)
VA_219 VA_221
VA_193 VA_192 VA_198
VA_200
VA_194 VA_195 VA_199
VA_205
PI_798 VA_198O0003 80060012008
VA_192I
PI_799 VA_199O0004
VA_193O
PI_863
HEROS-H-S-FI
800600120010
. each operation mode is described by abinary vector giving the state of each valve
. we use the convex hull of these binaryvectors to include the operation modes inour model
Martin Grötschel Optimization of Gas Networks 23 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Visualization of Solutionsutilization
entries
exits
Martin Grötschel Optimization of Gas Networks 24 / 31
Automatic Testing of Many Nominations
There are mathematically sound methods to reduce a large set ofnominations to a much smaller representative set.
1 500 000 nominations ca. 4 000 representative nominations
Martin Grötschel Optimization of Gas Networks 25 / 31
Future Tasks
As usual:Citius,Altius,Fortius
bigger networks,faster computations,higher precision
. we need to deal with bigger networks as the market areas increase
. calculation times have to be reduced
. we have to incorporate more detailed physics
. we should be able to handle multi-scale networks.
Martin Grötschel Optimization of Gas Networks 26 / 31
Future Tasks
As usual:Citius,Altius,Fortius
bigger networks,faster computations,higher precision
. we need to deal with bigger networks as the market areas increase
. calculation times have to be reduced
. we have to incorporate more detailed physics
. we should be able to handle multi-scale networks.
Martin Grötschel Optimization of Gas Networks 26 / 31
Future Tasks
As usual:Citius,Altius,Fortius
bigger networks,faster computations,higher precision
. we need to deal with bigger networks as the market areas increase
. calculation times have to be reduced
. we have to incorporate more detailed physics
. we should be able to handle multi-scale networks.
Martin Grötschel Optimization of Gas Networks 26 / 31
Future Tasks
As usual:Citius,Altius,Fortius
bigger networks,faster computations,higher precision
. we need to deal with bigger networks as the market areas increase
. calculation times have to be reduced
. we have to incorporate more detailed physics
. we should be able to handle multi-scale networks.
Martin Grötschel Optimization of Gas Networks 26 / 31
Future Tasks
As usual:Citius,Altius,Fortius
bigger networks,faster computations,higher precision
. we need to deal with bigger networks as the market areas increase
. calculation times have to be reduced
. we have to incorporate more detailed physics
. we should be able to handle multi-scale networks.
Martin Grötschel Optimization of Gas Networks 26 / 31
Future Tasks
As usual:Citius,Altius,Fortius
bigger networks,faster computations,higher precision
. we need to deal with bigger networks as the market areas increase
. calculation times have to be reduced
. we have to incorporate more detailed physics
. we should be able to handle multi-scale networks.
Martin Grötschel Optimization of Gas Networks 26 / 31
Bigger Networks
H-Süd. 47 entries, 265 exits. 1136 pipes,
45 resistors,224 valves,78 control valves,29 compressor stations
. 175 cycles
Martin Grötschel Optimization of Gas Networks 27 / 31
Bigger Networks
L-Gas. 12 entries, 1001 exits. 3623 pipes,
26 resistors,300 valves,118 control valves,12 compressor stations
. 259 cycles
Martin Grötschel Optimization of Gas Networks 28 / 31
Some Insights
But. a substantial effort is needed to succeed,
. the setup cost is high compared to pure research,
. close cooperation with practitioners is necessary,
. different disciplines have to collaborate.
Martin Grötschel Optimization of Gas Networks 29 / 31
Some Insights
Relevant real-world questions can be tackled efficiently bymathematical optimization.
But. a substantial effort is needed to succeed,
. the setup cost is high compared to pure research,
. close cooperation with practitioners is necessary,
. different disciplines have to collaborate.
Martin Grötschel Optimization of Gas Networks 29 / 31
Some Insights
Relevant real-world questions can be tackled efficiently bymathematical optimization.
But. a substantial effort is needed to succeed,
. the setup cost is high compared to pure research,
. close cooperation with practitioners is necessary,
. different disciplines have to collaborate.
Martin Grötschel Optimization of Gas Networks 29 / 31
Some Insights
Relevant real-world questions can be tackled efficiently bymathematical optimization.
But. a substantial effort is needed to succeed,
. the setup cost is high compared to pure research,
. close cooperation with practitioners is necessary,
. different disciplines have to collaborate.
Martin Grötschel Optimization of Gas Networks 29 / 31
Some Insights
Relevant real-world questions can be tackled efficiently bymathematical optimization.
But. a substantial effort is needed to succeed,
. the setup cost is high compared to pure research,
. close cooperation with practitioners is necessary,
. different disciplines have to collaborate.
Martin Grötschel Optimization of Gas Networks 29 / 31
Some Insights
Relevant real-world questions can be tackled efficiently bymathematical optimization.
But. a substantial effort is needed to succeed,
. the setup cost is high compared to pure research,
. close cooperation with practitioners is necessary,
. different disciplines have to collaborate.
Martin Grötschel Optimization of Gas Networks 29 / 31
Future Challenges
How can we incorporate transient effects intostationary optimization models?
. To be able toI compute probabilities for interruptible capacities,I take storage into account when computing capacities,I compute capacities less pessimistically while still ensuring
security of supply,
. we need toI analyse the gap between transient and stationary models,I understand transitions between successive nominations better,I make improvements on the stochastic treatment,I develop more powerful optimization algorithms.
Research on all levels –from basic theory to practicalapplication– is needed to face future challenges!
Martin Grötschel Optimization of Gas Networks 30 / 31
Future Challenges
How can we incorporate transient effects intostationary optimization models?
. To be able toI compute probabilities for interruptible capacities,I take storage into account when computing capacities,I compute capacities less pessimistically while still ensuring
security of supply,
. we need toI analyse the gap between transient and stationary models,I understand transitions between successive nominations better,I make improvements on the stochastic treatment,I develop more powerful optimization algorithms.
Research on all levels –from basic theory to practicalapplication– is needed to face future challenges!
Martin Grötschel Optimization of Gas Networks 30 / 31
Future Challenges
How can we incorporate transient effects intostationary optimization models?
. To be able toI compute probabilities for interruptible capacities,I take storage into account when computing capacities,I compute capacities less pessimistically while still ensuring
security of supply,
. we need toI analyse the gap between transient and stationary models,I understand transitions between successive nominations better,I make improvements on the stochastic treatment,I develop more powerful optimization algorithms.
Research on all levels –from basic theory to practicalapplication– is needed to face future challenges!
Martin Grötschel Optimization of Gas Networks 30 / 31
Future Challenges
How can we incorporate transient effects intostationary optimization models?
. To be able toI compute probabilities for interruptible capacities,I take storage into account when computing capacities,I compute capacities less pessimistically while still ensuring
security of supply,
. we need toI analyse the gap between transient and stationary models,I understand transitions between successive nominations better,I make improvements on the stochastic treatment,I develop more powerful optimization algorithms.
Research on all levels –from basic theory to practicalapplication– is needed to face future challenges!
Martin Grötschel Optimization of Gas Networks 30 / 31
Thank you very much!
Martin Grötschel Optimization of Gas Networks 31 / 31
