基于含连通图约束的背包问题的图分割方法

作者：林济铿; 王旭东; 李胜文; 吴鹏; 邵广惠; 徐兴伟; 马新

来源：中国电机工程学报, 2012, 32(10): 19+134-141.

DOI：10.13334/j.0258-8013.pcsee.2012.10.001

• 图分割
• 含连通图约束的背包问题
• 含图约束的背包问题
• 近似算法
• 电力系统最优主动解列

图分割技术(网络分割技术)在互联网研究、交通运输、电网故障诊断和电力系统解列等方面有着重要的意义。首次建立一个新的图分割问题——含连通图约束的背包问题(connected graph constrained knapsack problem,CGKP),并提出其有效近似算法。引入与图连通性相关的4个新节点集合,证明这些新节点集合的性质,并提出这些节点集合的搜索方法;结合新节点集合的性质及搜索算法,通过对含图约束的背包问题近似算法进行扩展,提出求解CGKP的近似算法,并讨论此算法的计算复杂性。算例结果证明了该算法的有效性。因电力系统主动最优解列问题在一定条件下可归结为一个CGKP,该研究成果为电力系统最优主动解列断面搜索问题的求解奠定了理论基础。

• 单位
  天津大学; 智能电网教育部重点实验室; 天津市电力公司