Parallel nonconvex generalized Benders decomposition for natural gas production network planning under uncertainty

• Large-scale nonconvex MINLP for gas network planning solved with multiple CPUs.
• Efficient global optimization of the nonconvex MINLP by NGBD.
• Three parallelization strategies developed for NGBD to exploit multiple CPUs.
• Adaptive scenario and bounding parallelization shown to be the best strategy.
• A nonconvex MINLP with 30,000+ variables, 38 binary variables and 4000+ bilinear terms solved to global optimality with 8 CPUs within 45 min.

A scenario-based two-stage stochastic programming model for gas production network planning under uncertainty is usually a large-scale nonconvex mixed-integer nonlinear programme (MINLP), which can be efficiently solved to global optimality with nonconvex generalized Benders decomposition (NGBD). This paper is concerned with the parallelization of NGBD to exploit multiple available computing resources. Three parallelization strategies are proposed, namely, naive scenario parallelization, adaptive scenario parallelization, and adaptive scenario and bounding parallelization. Case study of two industrial natural gas production network planning problems shows that, while the NGBD without parallelization is already faster than a state-of-the-art global optimization solver by an order of magnitude, the parallelization can improve the efficiency by several times on computers with multicore processors. The adaptive scenario and bounding parallelization achieves the best overall performance among the three proposed parallelization strategies.