大规模最大割问题的离散动态凸化算法研究

The max-cut problem is one of classical NP-hard problems in combinaorial optimization, and has a lot of applications. With the development of scinece and engineering technology, the scale of engineering problmes becomes more and more large. Existing algorithms can not solve the large scale max-cut problem in a reasonable time. This program studis multilevel partitioning algorithm for large scale max-cut problem. The multilevel partitioning paradigm consists of coarsening phase, initial partitioning phase, uncoarsening and refinement phase. In the coarsening phase, static clustering algorithm is studied for grouping the vertices by the analysis of the topological structure of graph, and an algorithm is studied to guide the clustering dynamicly. The initial partitioning phase and uncoarsening and refinement phase studies a FM-based iterative improvement local search algorithm to refine the partition. Based on the characteristic of the max-cut problem, a discrete dynamic convexized method is studied to improve the quality of the partition. The research achievements provide a feasible research way for other large scale combinaorial optimization problems, and has important scientific significance and application prospect.

最大割问题是组合优化中的一个典型的NP困难问题，它在工程中有着广泛的应用。随着科学和工程技术的发展，工程问题的规模越来越大。目前的算法难以在可接受的时间内求解大规模最大割问题。本项目研究大规模最大割问题的多级划分算法。多级划分框架由粗化阶段、初始划分阶段、细化及优化阶段组成。粗化阶段分析图的拓扑结构，研究静态聚类算法对图的顶点进行收缩，并研究动态指导聚类的算法。在初始划分和细化及优化阶段，研究基于FM的迭代改进局部搜索算法对划分进行优化。针对大规模最大割问题的特点，研究离散动态凸化算法提高划分质量。本项目的研究成果为其他大规模组合优化问题的研究提供了一种可行途径，具有重要的科学意义和工程应用前景。

大规模最大割问题是一类最基本的组合优化问题，有广泛的应用背景。本项目根据大规模最大割问题的特性，构造了基于ＦＭ的局部搜索搜索算法，该算法有效地提高了求解速度。然后，构造了最大割问题的全局聚类算法，动态找出先前局部最优解的共同结构，对图进行聚类，减少问题的规模。最后，本项目提出了一类快速求解大规模最大割问题的离散动态凸化算法。实验结果表明该算法是有效的。