Parallel Solution of Optimal Gas Network Control Under Uncertainty.

Michael Bynum, Lorenz T. Biegler, Carl D. Laird, Sakshi Naik, Robert Parker, John D. Siirola2022 · DOI

TL;DR

Researchers at Sandia National Laboratories have developed PyNumero and Parapint, a high-level Python framework that enables massive parallelization of complex optimization problems. By applying Schur-complement decomposition, they achieved a 360x speedup on 1024 cores, reducing the solution time for gas network control under uncertainty from minutes to seconds.

What Problem Does This Paper Address?

Managing natural gas distribution is a high-stakes balancing act. Operators must minimize the cost of running massive compressors while ensuring that fluctuating consumer demands are met across a vast network of pipelines. Because future demand is never certain, engineers use stochastic programming—a method that models multiple possible "scenarios" to find a robust control strategy.

The challenge is scale. Even a tiny 2-node network with just 32 scenarios can take nearly two minutes to solve using standard serial solvers like IPOPT. For real-world, continental-scale networks with thousands of nodes and hundreds of scenarios, the math becomes computationally "heavy" and far too slow for real-time decision-making. The field desperately needed a way to break these massive problems into smaller pieces that can be solved simultaneously across hundreds or thousands of computer processors.

Methods

The authors introduced two primary software contributions:

  1. PyNumero: A high-level Python framework designed for rapid development of optimization algorithms. It allows researchers to write code that looks like standard Python (using NumPy/SciPy syntax) but performs like compiled C++ by linking to high-performance linear algebra libraries (like MUMPS and HSL).
  2. Parapint: A library built on top of PyNumero specifically for "Parallel in Time" and parallel stochastic optimization.

The core mathematical "trick" used is Schur-complement decomposition. Instead of trying to solve one giant matrix representing the entire gas network and all its scenarios at once, the algorithm:

  • Decomposes the problem into independent sub-blocks (e.g., one for each scenario).
  • Factors these blocks in parallel across different CPU cores.
  • Reduces the global problem to a much smaller "Schur-complement" system that coordinates the pieces.
  • Communicates only the essential data between processors using MPI (Message Passing Interface).

Datasets

The paper evaluates the framework using:

  • A 2-node natural gas network model: Used as a benchmark for stochastic control under 32 different demand scenarios.
  • Discretized PDE Control (Burgers’ Equation): A standard mathematical benchmark used to compare PyNumero’s performance against fully compiled C++ solvers (IPOPT).
  • Large-scale scalability tests: Synthetic scaling of time horizons and process counts to test performance up to 1024 cores.

Key Insights and Ideas

  • The "Python Performance Gap" is a Myth (mostly): The authors demonstrate that if you use Python to orchestrate the algorithm while letting compiled C++ libraries handle the heavy arithmetic, the performance penalty is negligible (within 15% of pure C++).
  • Block-Awareness is Essential: By creating BlockVector and BlockMatrix classes that store pointers to data rather than duplicating it, the framework avoids the memory bottlenecks that usually plague high-level languages in HPC (High-Performance Computing).
  • Structure Matters: The "shape" of the uncertainty changes how the math should be solved. Stochastic optimization creates "dense" structures, while dynamic optimization (time-based) creates "sparse" structures. Parapint is designed to analyze these structures symbolically once and then exploit that knowledge for faster communication during every subsequent step.

Key Results

  • Massive Scalability: The parallel Schur-complement approach achieved approximately 360x speedup when scaled to 1024 cores. While the serial solution time grew exponentially as the problem size increased, the parallel solution time remained nearly flat.
  • Real-World Speed: The 2-node, 32-scenario gas network problem that previously took 1.7 minutes (102 seconds) to solve was reduced to just 6.7 seconds using Parapint on 16 processes.
  • Efficiency: For large-scale problems (100,000+ variables), the Python-based PyNumero solver performed comparably to the industry-standard IPOPT written in C++.

Limitations and Future Work

While the speedups are impressive, the authors note a few areas for improvement:

  • Algorithm Robustness: The interior point algorithm within Parapint needs further refinement to handle a wider variety of "poorly behaved" nonlinear problems as reliably as established solvers.
  • Nested Decomposition: Future work aims to combine "scenario" decomposition and "time" decomposition. This "nested Schur-complement" approach would allow for even finer-grained parallelism, potentially tackling problems with millions of variables.
  • Algorithm Library: The team plans to expand the library to include a broader suite of optimization algorithms beyond the current equality-constrained SQP and interior point methods.

Summary updated

BibTeX
@misc{bynum2022parallel,
  author = {Michael Bynum and Lorenz T. Biegler and Carl D. Laird and Sakshi Naik and Robert Parker and John D. Siirola},
  title = {{Parallel Solution of Optimal Gas Network Control Under Uncertainty.}},
  year = {2022},
  doi = {10.2172/2006150},
}
Figure