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

摘要

在无线网络设计中,连通支配集(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.