中文摘要：

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

结论摘要：

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