Convex Relaxations for Gas Expansion Planning

Conrado Borraz-Sanchez, Russell Bent, Scott Backhaus, Hassan Hijazi, Pascal Van Hentenryck

TL;DR

This paper introduces a novel convex relaxation—specifically a Mixed-Integer Second-Order Cone Programming (MISOCP) model—to solve the notoriously difficult problem of planning natural gas network expansions. By cleverly reformulating non-convex physics constraints into a convex form, the authors achieve computational speedups of up to two orders of magnitude, allowing them to find high-quality (and often globally optimal) designs for large-scale, real-world networks that stymie traditional solvers.

What Problem Does This Paper Address?

Expanding a natural gas transmission network is a multi-billion-dollar engineering challenge. Planners must decide where to install new pipelines and compressors to meet growing demand while ensuring the system obeys the laws of physics.

The core difficulty lies in the Weymouth equation, which describes the relationship between gas flow and pressure drop. This relationship is non-linear and non-convex, meaning the "feasible region" of possible solutions has "dents" and "holes" that make it extremely hard for optimization algorithms to find the absolute best (globally optimal) design.

While global optimization solvers exist, they typically fail to scale beyond tiny, textbook examples. Consequently, industry has often relied on local search heuristics (which might miss the best design) or piecewise linear approximations (which can be computationally heavy and inaccurate). The authors aim to bridge this gap by providing a model that is both mathematically rigorous and computationally scalable.

Methods

The authors transform the original Mixed-Integer NonLinear Programming (MINLP) problem into a Mixed-Integer Second-Order Cone Programming (MISOCP) relaxation. The "relaxation" part means they slightly expand the feasible region to make it convex, ensuring that any solution to the relaxation provides a provable "lower bound" on the true cost.

Key technical innovations include:

  • Flux Direction Variables: They introduce binary variables to explicitly track which way the gas is flowing. This allows them to remove the absolute value terms in the pressure equations that usually cause mathematical headaches.
  • Exact McCormick Relaxations: They use a standard technique (McCormick envelopes) to linearize the product of the binary direction variables and continuous pressure variables. Because the direction variables are discrete, this relaxation is actually exact.
  • Perspective Formulations: To handle "on/off" constraints (e.g., a pipe is either built and follows physics, or it isn't built and has zero flow), they use perspective functions to create a tighter convex hull.
  • Valid Integer Cuts: They derive logical constraints (cuts) based on network topology—for example, ensuring that if gas enters a simple pass-through node, it must also exit.

Datasets

The researchers evaluated their approach on several benchmarks:

  1. The Belgian Network: A classic 20-node, 24-pipeline benchmark used extensively in the literature. They created several expansion scenarios (A1–A3) and "from-scratch" design problems (B1–B4).
  2. Instance D: A proprietary, real-world 60-node network from the United States.
  3. GasLib Instances: Large-scale synthetic but realistic networks based on the German gas grid, ranging from 40 nodes (GasLib-40) to 582 nodes (GasLib-582).

Key Insights and Ideas

  • Convexity is King for Scalability: The jump from non-convex MINLP to convex MISOCP is the primary driver of performance. It allows the use of highly efficient commercial solvers like CPLEX or Gurobi that are optimized for these specific mathematical structures.
  • The Power of "Cuts": One of the most striking findings is that the "integer cuts" (logical rules about flow direction) are not just supplementary—they are critical. Without them, the solver's performance on large networks degrades significantly.
  • Tightness Matters: A relaxation is only useful if it stays "close" to the original problem. The authors show that their MISOCP relaxation is remarkably "tight," meaning the gap between the relaxed solution and the true optimal solution is often zero or negligible.

Key Results

  • Speed: On the Belgian network, the MISOCP approach was consistently 10 to 100 times faster than the standard MINLP formulation.
  • Scalability: The MISOCP model successfully solved the 582-node network (GasLib-582) to optimality or near-optimality. In contrast, the standard MINLP approach failed to find any feasible solutions for the larger instances.
  • Accuracy: Compared to Piecewise Linear Approximation (PLA) models—a common industry alternative—the MISOCP model was both faster and more accurate. PLA models often significantly underestimated the true cost of expansion because they struggle with the non-convexity of the pressure constraints.

Limitations and Future Work

  • Steady-State Assumption: The model assumes "steady-state" conditions (gas flow is constant over time). In reality, gas grids experience "line pack" and transient fluctuations that require dynamic modeling.
  • Objective Function: The paper focuses primarily on minimizing capital expenditure (building costs). While the authors note the model can be generalized to include operational costs (like the fuel used by compressors), this was not the primary focus of the reported experiments.
  • Extreme Stress: For the largest network (582 nodes) under extreme demand stress (75%–125% increase), the solver timed out before reaching a 0% gap, though it still provided high-quality upper and lower bounds.

Overall, this work provides a powerful new tool for energy engineers, proving that with the right mathematical "shortcuts," we can solve massive infrastructure problems with global guarantees.

Summary updated

Abstract

Expansion of natural gas networks is a critical process involving substantial capital expenditures with complex decision-support requirements. Given the non-convex 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 soluutions. 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.
BibTeX
@article{borrazsanchez2016convex,
  author = {Conrado Borraz-Sanchez and Russell Bent and Scott Backhaus and Hassan 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