求解大规模支配集类问题的混合算法研究

Dominating set problems are among classic NP-hard combinatorial optimization problems, with applications in the management of wireless ad-hoc networks and the locating of relays in optical networks. It has become the bottleneck of the high-performance management for intensively deployed networks. Therefore, the research on efficient algorithms for dominating set problems is critical both in theoretical and practical aspects. This project focuses on the following works: (1) the mathematical model for obtaining the lower bounds of dominating set problems; (2) configuration checking meta-heuristics for solving dominating set problems; (3) the hybrid algorithm of the configuration checking heuristic and the lower bound method. The goal of this project is not only to solve dominating set problems efficiently but also to combine its lower bound method and the metaheuristic, such that these two phases guide each other to obtain better results. The hybrid algorithms get both the ability to obtain a near optimum solution and the proof for the goodness of the solution. This project also proposes general hybrid mechanisms for solving other combinatorial optimization problems as well.

支配集类问题是一类经典的NP难问题，在无线自组网的管理及光网络中继的选址问题等领域中有着广泛的应用，是大规模部署网络高效管理的主要瓶颈所在。因此设计求解支配集类问题的高效算法具有重要的理论价值和实际意义。本课题主要进行以下方面的研究：（1）支配集类问题的下界求解模型；（2）支配集类问题的元启发式上界格局检测算法；（3）支配集类问题上下界算法相结合的混合求解算法。本课题的研究不仅力求实现对支配集类问题的高效求解，同时力求将下界算法融入启发式算法中以指导并验证上界算法的求解。上下界算法结合的混合算法使得元启发式算法在获得高质量解的同时获得对解优度的说明能力，对求解其他组合优化问题具有很好的借鉴意义。

支配集类问题是一类经典的NP难问题，在无线自组网的管理及光网络中继的选址问题等领域中有着广泛的应用，是大规模部署网络高效管理的主要瓶颈所在。本课题在执行过程中进行了如下方面的研究：（1）支配集类问题的下界求解模型研究；（2）支配集类问题的高效元启发式求解算法研究；（3）支配集类问题的混合算法研究。课题执行过程与研究计划基本吻合，完成了主要的预期研究目标，成果产出丰厚，在运筹管理学顶级期刊上发表论文，在信息学重要SCI期刊上发表多篇论文。依托本课题所设计的用于求解最小连通支配集问题的快速顶点加权局部搜索算法、用于求解最小支配树问题的双层元启发式算法以及用于求解最小最大图边交叉数问题的变身度邻域搜索算法能有效求解并且更新了大量算例的已知最优解。研究中所采用的各项技术能够对其他类似结构的组合优化问题产生良好的借鉴意义。