最小加权顶点覆盖问题的求解算法研究

The minimum weighted vertex cover problem is one of the earliest proved NP hard problems. The problem has always been a hotspot in the field of computer science especially in artificial intelligence and has great success in the application fields such as transportation planning, network security. In recent years, though the solving algorithms of minimum weighted vertex cover problem has achieved initial progress, but the scale of the problem solvable and the quality of the solution still exist great shortage, so effective algorithms for dealing with large scale problems are lacking. This project will focus on the local search algorithms and branch and bound algorithms of the minimum weighted vertex cover problem. In the local search algorithms, we will design effective heuristic search strategies, effective jumping out of the local optimal strategies and decomposition methods of large-scale instances. In the branch and bound algorithms, we will propose effective reduction strategies, reasonable vertex selecting sequences and the computing methods of the high quality upper bound.

作为最早被证明为NP困难的问题之一，最小加权顶点覆盖问题一直以来都是计算机科学尤其是人工智能领域的研究热点，在交通规划、网络安全等领域有广泛应用。尽管近年来针对最小加权顶点覆盖问题的求解算法有了初步进展，但其求解规模和求解质量方面依然存在很大不足，缺乏处理大规模问题实例行之有效的算法。因此本项目将围绕设计最小加权顶点覆盖问题的局部搜索算法和分支限界算法展开。主要工作包括：在最小加权顶点覆盖问题的局部搜索算法方面，设计高效的启发式搜索策略，给出有效的跳出局部最优策略，提出针对大规模的分解方法；在最小加权顶点覆盖问题的分支限界算法方面，设计高效的化简规则，确定合理的分支选择顺序，提出高质量的上界计算方法。

最小加权顶点覆盖问题是经典的NP难组合优化问题，在交通规划、网络安全、设施选址等多个领域具有广泛的应用价值。尽管近年来针对最小加权顶点覆盖问题的求解算法有了初步进展，但其求解规模和求解质量方面依然存在很大不足，缺乏处理大规模问题实例行之有效的算法。本项目基于局部搜索算法对最小加权顶点覆盖问题展开了深入研究，项目组提出了高效的启发式策略，有效的跳出局部最优策略以及针对大规模实例的有效策略。项目组设计了基于动态打分策略，加权格局检测策略和顶点选择策略的局部搜索算法DLSWCC求解该问题。针对大规模问题实例，提出了基于化简规则，带有特赦准则的格局检测策略和自适应顶点删除策略的求解算法NuMWVC，突破了当前研究对大规模问题实例的局限和不足。多目标最小加权顶点覆盖问题和泛化顶点覆盖问题是最小顶点覆盖的变形问题，有着更强的建模能力和更广泛的实际应用，本项目设计了基于分解的多目标变邻域搜索算法MONSD求解多目标最小加权顶点覆盖问题，设计了基于进化搜索和迭代邻域搜索的模因算法MAGVCP求解泛化顶点覆盖问题。本项目的研究成果对局部搜索算法在顶点覆盖问题及其应用上起到了积极的推动作用，为大规模组合优化问题的求解方法提供了更广阔的思路。