天然气管网规划中的混合整数规划模型与算法

Mixed-Integer Programming Models and Algorithms in Natural Gas Network Planning

摘要: 天然气管网规划问题极具挑战性，其核心是混合整数非线性规划(MINLP)特征。该特征主要源于复杂的网络拓扑、非线性的物理守恒关系，以及离散的管道建设与设备选型决策。本文针对该MINLP模型，采用分段线性近似技术，将其转化为可求解的混合整数线性规划(MILP)模型。本文为了加速MILP模型的求解效率，深入分析了管网的特殊拓扑结构和流量守恒特性，并基于此提出了强化的有效不等式(即加速割平面)。该不等式经验证可有效地应用于一般拓扑结构下的管网规划MILP模型。数值实验结果表明，所提出的不等式能够显著加强模型的线性松弛界，从而有效缩短MILP模型的求解时间。

Abstract: The natural gas network planning problem presents significant challenges, primarily characterized by its Mixed-Integer Nonlinear Programming (MINLP) nature. This complexity stems from intricate network topology, nonlinear physical conservation relationships, and the discrete decisions involved in pipeline construction and equipment selection. This paper addresses the MINLP model by employing a Piecewise Linearization technique to reformulate it into a solvable Mixed-Integer Linear Programming (MILP) model. To accelerate the solution efficiency of the resulting MILP model, we conduct an in-depth analysis of the pipeline network’s special topological structure and flow conservation properties. Based on this analysis, we propose a strengthened valid inequality (i.e., accelerating cutting plane). The inequality is demonstrated to be effectively applicable to MILP models for pipeline network planning under general topological structures. Numerical results confirm that the proposed inequality significantly tightens the linear relaxation bound of the model, consequently effectively reducing the MILP solution time.