最小连通支配集问题的分解算法

摘要：

在无线网络设计中,连通支配集(CDS)有着广泛的应用.针对最小连通支配集问题(MCDSP),提出了基于Benders的分解算法进行最优求解.将原问题分解为较易求解的最小支配集主问题和连通性子问题,其中主问题能够生成最小支配集,子问题负责判断所生成的最小支配集的连通性.若不连通,生成相应的Benders cut对主问题进行修正和进一步限定.在上述Benders算法中,主问题与子问题均为纯整数规划.在此基础上,分析了最小连通支配集问题的上下界性质,通过构造容易求解的辅助问题,并结合二分法思想进一步降低问题的搜索空间,设计了改进的Benders分解算法,加速算法收敛速度.通过计算实验与现有文献中的分解算法进行对比,证明了所提分解算法的优越性.

关键词：最小连通支配集、Benders分解、组合割、整数规划

所属期刊栏目：35

分类号：O221.4(运筹学)

资助基金：中国博士后基金资助项目2017M552213

在线出版日期：2018-04-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：419-424