Novel Piecewise Linear Approximation Methods with Application to Operational Optimization of Natural Gas Networks

Abstract

Natural gas transmission networks are the primary means of gas transportation. Given the quantity of gas transported globally, optimizing the operation of transmission networks has long attracted academic and industrial interest. This thesis is concerned with employing novel piecewise-linear (PWL) approximation techniques to improve the ability to find globally optimal solutions to gas transmission network operation problems. Practical gas transmission networks are large-scale systems whose operation must be modeled using hundreds of variables and equations. Discrete operating decisions and nonlinear physics introduce nonconvexity into the model. For the model to be useful in guiding optimal operating decisions in response to changing process conditions, it must be solvable within minutes. The first contribution is to model the transient operation of a gas network using a two-stage stochastic framework to capture future gas supply uncertainty. The two-stage framework adds further model complexity. The nonlinearity in the original model is approximated with convex/concave continuous piecewise-linear (CPWL) functions. The CPWL approximate model is shown to be solvable to global optimality within minutes, whereas the best available solvers are unable to locate a feasible solution to the original model within hours. The second contribution is to improve the ability to generate CPWL approximations of arbitrary nonlinear functions. The difference-of-convex CPWL representation is introduced to formulate any CPWL function as the difference of two convex CPWL functions. This admits a convenient formulation as any convex CPWL function can be modeled through integer-linear constraints. This enables the introduction of several algorithms that are applicable to functions of any dimension and can find a CPWL approximation that is within $\delta > 0$ on a compact domain, referred to as a CPWL $\delta$-approximation. The final contribution improves the relaxations of constraints with weak convex relaxations through (not necessarily continuous) PWL $\delta$-approximators. Theoretical results prove that a PWL $\delta$-approximator can formulate through linear constraints a convex underestimator that is arbitrarily tight to the convex envelope of the function it approximates. This yields several approaches to tighten the convex relaxations throughout the branch-and-bound search. Computational results demonstrate substantial speedup of global optimization for a particular gas transmission operations problem.