Global Optimization of Gas Transportation and Storage: Convex Hull Characterizations and Relaxations

Abstract Gas transportation and storage has become one of the most relevant and important optimization problems in energy systems. This problem inherently includes highly nonlinear and nonconvex aspects due to gas physics, and discrete aspects due to the control decisions of active network elements. Obtaining even locally optimal solutions for this problem presents significant mathematical and computational challenges for system operators. In this paper, we formulate the gas transportation and storage problem as a nonconvex mixed-integer nonlinear program (MINLP) through disjunctions on the flow directions. Moreover, we study the nonconvex sets induced by gas physics and propose mixed-integer second-order cone programming relaxations for the nonconvex MINLP problem. The proposed relaxations are based on the convex hull representations of two nonconvex sets: Firstly, we give the convex hull representation of the nonconvex set for pipes and show that it is second-order cone representable. Secondly, we also give a complete characterization of the extreme points of the nonconvex set for compressors and show that the convex hull of the extreme points is power cone representable. Moreover, for practical applications, we propose a second-order cone outer-approximation for the nonconvex set for compressors. To obtain (near) globally optimal solutions, we develop an algorithmic framework based on our convex hull results. We evaluate our framework through extensive computational experiments on various GasLib networks in comparison with the convex relaxations from the literature and a state-of-the-art global solver. Our results highlight the computational efficiency and convergence performance of our convex relaxation method compared to other methods. Moreover, our method also consistently provides (near) global solutions as well as high-quality warm-starting points for local solvers.