Convex Relaxations for Gas Expansion Planning

Conrado Borraz-Sánchez, Russell Bent, Scott Backhaus, Hassan L. Hijazi, Pascal Van Hentenryck

Abstract

Expanding natural gas transmission infrastructure is a high-stakes engineering challenge involving significant capital expenditure. The core optimization problem, Gas Transmission Network Expansion Planning (GTNEP), is traditionally modeled as a Mixed-Integer NonLinear Program (MINLP) due to the non-convex physics of gas flow. This paper presents a novel Mixed-Integer Second-Order Cone Programming (MISOCP) relaxation that transforms these non-convex equations into a tractable form. By leveraging flux direction variables, perspective formulations, and network-based integer cuts, the proposed method achieves solutions orders of magnitude faster than traditional global solvers and scales to real-world networks with hundreds of nodes.

Introduction

Deciding where to install new pipelines or compressors in a gas network is a complex task. Engineers must balance the high cost of construction against the physical requirements of gas delivery. This problem, known as GTNEP, is notoriously difficult because gas flow is governed by the Weymouth equations. These equations describe a non-convex relationship between pressure drops and flow rates, creating a "bumpy" search space. When combined with the discrete decisions of whether or not to build specific infrastructure, the resulting MINLP often paralyzes standard optimization solvers, particularly as network sizes grow.

Historically, industry practitioners have relied on Piecewise Linear Approximations (PLA). However, PLA models often underestimate costs or return solutions that are physically infeasible. This research addresses these shortcomings by introducing a convex relaxation that provides both high-quality lower bounds and a reliable roadmap for finding feasible, near-optimal expansion plans.

The MISOCP Framework

The authors propose a Mixed-Integer Second-Order Cone Programming (MISOCP) relaxation. Unlike traditional MINLP approaches that struggle with the absolute value terms and bilinearities of gas physics, this framework relies on four technical pillars to maintain tractability and tightness:

  1. Flux Direction Variables: The model introduces binary variables to explicitly represent the direction of gas flow. This allows for the removal of absolute value terms in the pressure-drop equations, which are a primary source of numerical instability.
  2. Exact McCormick Relaxations: Bilinear terms (products of variables) are linearized using McCormick envelopes. Because the direction variables are discrete, these relaxations become exact within the integer space, preserving the physical accuracy of the model.
  3. Perspective Formulations: To handle the "on/off" nature of infrastructure investment, the authors utilize perspective techniques. These create a tight convex hull for the constraints associated with new pipes, significantly improving the solver's ability to prune the search tree during the branch-and-bound process.
  4. Valid Integer Cuts: The researchers derived logical constraints based on network topology. For instance, if a node has no supply or demand, the flow direction of an incoming pipe must logically match that of the outgoing pipe. These "integer cuts" act as a mathematical secret sauce, dramatically accelerating computation by eliminating redundant search spaces.

To ensure the final plan is physically viable, the solution from the MISOCP relaxation is used as a starting point for a local nonlinear solver, which refines the results into a guaranteed feasible solution.

Experimental Results and Scalability

The model was evaluated against a variety of benchmarks, ranging from classic academic problems to massive synthetic grids:

  • The Belgian Network: On this standard 20-node benchmark, the MISOCP approach was consistently one to two orders of magnitude faster than traditional MINLP solvers.
  • GasLib Benchmarks: The framework demonstrated remarkable scalability by successfully solving the GasLib-582 instance (582 nodes). Traditional solvers typically time out or fail to find any feasible solution on networks of this magnitude.
  • Optimality and Cost: In many instances, the gap between the lower bound (the relaxation) and the feasible solution was 0%, indicating that the model found the global optimum. Furthermore, on several modified Belgian instances, the MISOCP approach identified expansion plans that were significantly cheaper than those previously reported in the literature.

Discussion and Future Work

The primary insight of this work is that a tight convex relaxation serves as more than just a mathematical bound; it is an efficient guide for navigating complex engineering landscapes. By translating physical intuition—such as flow conservation—into valid integer cuts, the authors bridged the gap between physical reality and computational efficiency.

However, some limitations remain. The current model assumes a "steady-state" condition where gas flow is constant. Real-world networks must manage "transients," or fluctuations in demand over time. Additionally, while the model excels at minimizing capital expenditure, future iterations could more deeply integrate operational costs, such as the fuel consumed by compressors. While the GasLib-582 instance was solved, it pushed the limits of current solvers, suggesting that further refinements in duality gap reduction are needed for even larger continental-scale grids.

Conclusion

This MISOCP relaxation represents a significant step forward in gas network optimization. By combining convex analysis with discrete logic, the authors provide a tool that is both physically rigorous and computationally scalable, offering a robust alternative to the approximations currently used in industrial planning.

Summary updated

BibTeX
@article{borrazsanchez2016convex,
  author = {Conrado Borraz-Sánchez and Russell Bent and Scott Backhaus and Hassan L. Hijazi and Pascal Van Hentenryck},
  title = {{Convex Relaxations for Gas Expansion Planning}},
  journal = {INFORMS J. Comput.},
  year = {2016},
  doi = {10.1287/ijoc.2016.0697},
}
Figure