Convex Relaxations for Gas Expansion Planning

Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the nonconvex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approac...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2016-09, Vol.28 (4), p.645-656
Main Authors: Borraz-Sanchez, Conrado, Bent, Russell, Backhaus, Scott, Hijazi, Hassan, Van Hentenryck, Pascal
Format: Article
Language:English
Subjects:
03 NATURAL GAS
Algorithms
Capital investments
Convex analysis
convex relaxations
Decision support systems
Distribution
Expansion
Expansion planning problem
Expenditures
Gas expansion
Gas transmission
Global optimization
Integer programming
Lower bound
Lower bounds
Management research
Methods
MINLP problem
Mixed integer
mixed-integer programming
Natural gas
Natural gas distribution
Natural gas network
network design
Numerical analysis
second-order cone programming
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the nonconvex nature of gas transmission constraints, global optimality and infeasibility guarantees can only be offered by global optimisation approaches. Unfortunately, state-of-the-art global optimisation solvers are unable to scale up to real-world size instances. In this study, we present a convex mixed-integer second-order cone relaxation for the gas expansion planning problem under steady-state conditions. The underlying model offers tight lower bounds with high computational efficiency. In addition, the optimal solution of the relaxation can often be used to derive high-quality solutions to the original problem, leading to provably tight optimality gaps and, in some cases, global optimal solutions. The convex relaxation is based on a few key ideas, including the introduction of flux direction variables, exact McCormick relaxations, on/off constraints, and integer cuts. Numerical experiments are conducted on the traditional Belgian gas network, as well as other real larger networks. The results demonstrate both the accuracy and computational speed of the relaxation and its ability to produce high-quality solutions.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.2016.0697