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

王 彬, 孙德峰

(1. 山西大同大学 数学与计算机科学学院, 山西 大同 037009;2. 东北大学 信息科学与工程学院, 沈阳 110819)

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

王 彬1, 孙德峰2

(1. 山西大同大学 数学与计算机科学学院, 山西 大同 037009;2. 东北大学 信息科学与工程学院, 沈阳 110819)

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

最小连通支配集; Benders分解; 组合割; 整数规划

0 引 言

最小连通支配集问题因其在无线传感器网络领域的重要作用受到了学者越来越多的关注。它能够作为一个“虚拟骨干网”来降低网络节点的能量损耗、拓扑网络的维护费用,并能够减轻广播风暴的影响。

(a)—支配集; (b)—连通支配集。图1 支配集及连通支配集示意图Fig.1 Dominating set and connected dominating set

MCDSP问题被证明是NP难的[1], 并且与最多叶子生成树问题(MLSTP)等价[2]。最小连通支配集问题被广泛地应用于无线传感器网络的规划问题[3],同时也被应用在光纤网络设计[4]等一系列网络问题中。……