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

A decomposition approach for the Minimum Connected Dominating Set Problem

作　　者：王彬[1] 孙德峰 

机构地区：[1]山西大同大学数学与计算机科学学院,山西大同037009 [2]东北大学信息科学与工程学院,沈阳110819

出　　处：《沈阳师范大学学报（自然科学版）》2017年第4期419-424,共6页Journal of Shenyang Normal University:Natural Science Edition

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

摘　　要：在无线网络设计中,连通支配集(CDS)有着广泛的应用。针对最小连通支配集问题(MCDSP),提出了基于Benders的分解算法进行最优求解。将原问题分解为较易求解的最小支配集主问题和连通性子问题,其中主问题能够生成最小支配集,子问题负责判断所生成的最小支配集的连通性。若不连通,生成相应的Benders cut对主问题进行修正和进一步限定。在上述Benders算法中,主问题与子问题均为纯整数规划。在此基础上,分析了最小连通支配集问题的上下界性质,通过构造容易求解的辅助问题,并结合二分法思想进一步降低问题的搜索空间,设计了改进的Benders分解算法,加速算法收敛速度。通过计算实验与现有文献中的分解算法进行对比,证明了所提分解算法的优越性。The Connected Dominating Set(CDS)is significant in the area of wireless network design.This paper investigates the Minimum Connected Dominating Set Problem(MCDSP),and proposes a Benders-based decomposition approach to solve it optimally.The problem is decomposed into a master problem which generates minimum dominating set,and a slave problem which is solved to check the generated dominating set is connected or not.If not connected,the Benders cut will be generated and added into the master problem.Note that in the resulting Benders approach,the master problem and slave problem are both integer programming.Moreover,this paper analyzes the lower-and upper-bound properties of MCDSP to reduce the searching space of the problem by constructing an easier auxiliary problem and applying a dichotomy-iterative updating strategy,and finally proposes an accelerated Benders approach which is fast in convergence.The computational tests show that the proposed approach outperforms other decomposition approaches in previous literature,especially for low density instances.

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

分 类 号：O221.4[理学—运筹学与控制论]