Natural Gas Flow Solutions with Guarantees: A Monotone Operator Theory Approach

Krishnamurthy Dvijotham, Marc Vuffray, Sidhant Misra, Michael ChertkovarXiv 2015 · arXiv

Managing natural gas transmission is becoming increasingly complex due to the "hydro-fracking revolution" and the integration of gas-fired turbines into power grids. At the heart of operations lies the Gas Flow (GF) equations, which describe how pressure and mass flow are distributed across a network of pipes. These equations are nonlinear and notoriously difficult to solve. While simple tree-shaped networks are easy to handle, real-world "loopy" networks—especially those with multiplicative compression (pumps that boost pressure)—have long been suspected to be NP-hard.

This research addresses the lack of rigorous proof regarding when a solution exists, whether it is unique, and how to find it efficiently without getting stuck in local minima or facing exponential complexity.

The Monotone Operator Framework

The authors pivot away from standard nonlinear solvers and instead employ Monotone Operator Theory. In optimization, finding the zero of a "monotone operator" is analogous to finding the minimum of a convex function—it can be done efficiently in polynomial time.

While the GF operator isn't monotone everywhere, the authors prove it is monotone within specific regions of the state space (pressures and flows), termed Monotonicity Domains. They characterize these regions using Linear Matrix Inequalities (LMIs) and introduce a parameterizing matrix $W$ that defines the shape of these domains. By choosing $W$ correctly, they can "wrap" a monotonicity domain around the physically relevant operating points of a gas network. For general loopy networks, the algorithm solves a quasi-convex optimization problem to find the largest possible monotonicity domain, represented by a flow-bound ratio $\gamma$.

Network Modeling and Scalability

The paper evaluates the approach using synthetic test networks. A primary test case is a Synthetic 16-Bus Network, which represents a more complex, realistic scenario with multiple sources (injections), sinks (consumptions), and compressors.

A synthetic 16-bus network featuring multiple sources, sinks, and pipelines with compressors used to evaluate the scalability of the monotone operator approach.

This framework is robust enough that it naturally "recovers" known easy cases. For example, it proves that for tree networks or networks without compressors, the equations are inherently monotone for all positive pressures.

Results and the Compression Trade-off

Numerical experiments showed that the method produced $\gamma$ values (ranging from 85 to 470) that were significantly higher than any actual flows encountered in practice. By reducing the problem to a Monotone Variational Inequality (VI), the solution can be found using standard iterative methods with a convergence rate of $O(1/\epsilon)$.

One of the key insights is the discovery of a clear relationship between compression ratios and the size of the "guaranteed" domain. As the gas is pumped harder (higher compression), the theoretical "safe zone" for the solver shrinks.

The relationship between the mean compression ratio and the flow-bound ratio (gamma), demonstrating how the guaranteed monotonicity domain shrinks as compression increases.

Despite this shrinkage, the domain remains large enough for practical engineering limits. Even when compression ratios were scaled up to 7—well beyond typical operating values—the monotonicity domains remained sufficiently large to capture the solution.

Conclusion

This approach provides a level of mathematical certainty that heuristic solvers lack. Within a defined monotonicity domain, the paper proves that there can be at most one solution. While the current work focuses on steady-state regimes and doesn't yet provide a universal certificate for existence across the entire physical space, it marks a significant step toward reliable, polynomial-time solutions for complex gas grids. Future work will look into transient dynamics and scaling the algorithms for massive national-level grids.

Summary updated

Abstract

We consider balanced flows in a natural gas transmission network and discuss computationally hard problems such as establishing if solution of the underlying nonlinear gas flow equations exists, if it is unique, and finding the solution. Particular topologies, e.g. trees, are known to be easy to solve based on a variational description of the gas flow equations, but these approaches do not generalize. In this paper, we show that the gas flow problem can be solved efficiently using the tools of monotone operator theory, provided that we look for solution within certain monotonicity domains. We characterize a family of monotonicity domains, described in terms of Linear Matrix Inequalities (LMI) in the state variables, each containing at most one solution. We also develop an efficient algorithm to choose a particular monotonicity domain, for which the LMI based condition simplifies to a bound on the flows. Performance of the technique is illustrated on exemplary gas networks.
BibTeX
@misc{dvijotham2015natural,
  author = {Krishnamurthy Dvijotham and Marc Vuffray and Sidhant Misra and Michael Chertkov},
  title = {{Natural Gas Flow Solutions with Guarantees: A Monotone Operator Theory Approach}},
  year = {2015},
  eprint = {1506.06075},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.06075},
}
Figure